자자... 이번엔 스택을 이용하여 계산기를 만들어 보겠습니다~
무려 사칙연산과 ( ) << 인식까지-ㅅ-;;
일단 계산기에서 스택을 이용하기 위해서는 중위표기법(ex>1+1)를 후위표기법(ex>11+)로
전환해야 합니다. 그 후에 계산을 하지요~
자일단 후위표기에대해서 한번 알아봅시다.
<< 후위 표기 계산 연산 >>
1) 중위 표기 : 연산을 중간에 써준다 ex) a+b
2) 후위 표기 : 연산을 맨뒤에 써준다 ex )ab+
>>장점 : 괄호가 사라진다.
ex ) 중위표시 : (2+3)*3-1
후위표시 : 23+3*1-
후위표시는 각각의 숫자를 push하여 스텍에 쌓은뒤 연산자가 나오면 숫자들을 pop하면서 연산을 실행해준다.
연산한 결과를 return하여 스택에 쌓고 다음 숫자를 받아들여 스텍에 쌓은 뒤 연산자가 나호면 숫자들을
pop하여 연산을 실행한다. 이를 반복하여 값을 구한다.
※스택을 이용하여 치리하는 후위 표시방식을 사용하는 이유
: 중위 표기를 사용한다면 *트리구조(tree struct)가 되어 처리가 복잡호고 느려진다.
// 예전 포스팅한것을 가져다썻습니다.
먼저 그 1단계인 중위표기를 후위표기로 전환해보겠습니다.
이 단계에서는 다음의 알고리즘을 따르지요~
ⓐ 피연산자를 만나면 바로 출력
ⓑ 연산자를 만날시 우선순위에 의거해 출력. 보관 작업 실시
→ 저장된 연산자 > 새로운 연산자 : 저장된 연산자를 출력후 새로운 연산자를 보관
→ 저장된 연산자 < 새로운 연산자 : 새로운 연산자를 보관
※ 같을 때는 자기 소신 것... 아무데너 넣어주면 됩니다.
ⓒ 만약, 괄호가 온다면 여는 괄호는 저장 / 닫는 괄호가 나올시 여는 괄호가 나올때까지 연산자 출력
ⓓ 계산 수식이 끝나면 보관 된 모든 연산자를 출력
음.. 먼가 복잡해보이지만, 중위와 후위 표기를 확실히 이해한다면.. 몇번 손으로 변화시키다보면 감이 올것입니다.
(필자도 처음에 한 10개정도 손으로 변화해가면서 생각했내요''/)
하나 간단히 예를 들어보면...
<<A+B>>
ⓐ 피연산자 A를 출력
ⓑ "+"를 보관
ⓒ 피연산자 B를 출력
ⓓ 저장되었던 "+" 출력
자 본격 적으로 소스를 본다면
------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct nodetype{
char data;
struct nodetype *next_ptr;
}node;
typedef struct stacktype{
int count;
node *head_ptr;
}stack;
stack *makestack(){
stack *returnstack;
returnstack = (stack *)malloc(sizeof(stack));
if( returnstack != NULL ){
memset(returnstack,0,sizeof(stack));
return returnstack;
}else{
printf("Error!! Memory\n");
return 0;
}
return 0;
}
char Peek(stack *Pstack){
if ( Pstack -> count > 0 ){
return Pstack -> head_ptr -> data;
}
}
void Pop(stack *Pstack){
if ( Pstack -> count > 0 ){
node *freenode;
freenode = Pstack -> head_ptr;
Pstack -> head_ptr = Pstack -> head_ptr -> next_ptr;
if( freenode -> data != '(' ){
printf("%c",freenode -> data);
}
if ( freenode != NULL ){
free(freenode);
}
Pstack -> count--;
return ;
}else{
printf("Error!! Empty\n");
return ;
}
}
void Push(stack *Pstack, node d){
node *newnode = (node *)malloc(sizeof(node));
if ( Pstack -> count != 0 ){
if ( d.data == ')' ){
while ( Peek(Pstack) != '(' ){
Pop(Pstack);
}
Pop(Pstack);
return;
}else{
if ( d.data != '(' ){
while (Peek(Pstack) == '/' || Peek(Pstack) == '*'){
Pop(Pstack);
}
}
}
}
*newnode = d;
newnode -> next_ptr = Pstack -> head_ptr;
Pstack -> head_ptr = newnode;
Pstack -> count++;
}
void main(){
stack *Lstack;
Lstack = makestack();
printf("Calculate Program\n");
printf("Input : ");
while (1){
node datanode;
scanf("%c",&datanode.data);
if ( datanode.data == '\n' ) break;
if ( datanode.data == '+' || datanode.data == '-' || datanode.data == '*' || datanode.data == '/' || datanode.data == '(' || datanode.data == ')'){
Push(Lstack,datanode);
}else{
printf("%c",datanode.data);
}
}
while( Lstack -> count > 0 ){
Pop(Lstack);
}
printf("\n\nEnd\n");
}
-----------------------------------------------------------------------------------------------
자자 빨간 부분이 3곳있습니다...
맨위의 빨간 부분은 중위에서 후위로 변환후에는 괄호가 필요가 없기때문에 출력을 조절해주는 것입니다.
중간의 빨간 부분은 필자의 알고리즘으로 구연한 초간단 연산저장 코드입니다.
> 이것에 의해서 사칙연산의 우선순위와 여는괄호와 닫는괄호를 적재적소에 사용하지요.
마지막 부분은 숫자냐 기호냐를 나느는 곳이라고 생각하면됩니다.
------------------------------------------------------------------------------------------------
다른 소스에 비해-_- 필자는 간단하면서도 몇개 체크만하면 되겠지하는 식으로 생각하면서
코드를 작성하게되어 무지 짧으면서도 강력한(?) 코드를 만들었습니다.
뭐... 프로그래밍의 답은 없으니... 필자 것도 하나의 답이라고 생각하며...
이만 설명을 마치겠습니당~