[C] 사칙연산 계산 (후위표기법)

[C] 사칙연산 계산 (후위표기법)

우리는 흔히 연산을 표현할 때 중위 표기법을 사용한다.

중위 표기법을 사용하여 우선순위를 판단하여 연산 순서를 정한다.

하지만, 컴퓨터는 순차적으로 처리하기 때문에 중위 표기법으로는 정확한 순서로 연산에 어려움이 있다.

따라서, 컴퓨터가 연산할 때는 후위표기법을 사용한다.

후위표기법으로 변환하고, 후위표기법을 연산하는데 스택을 사용한다.

(1) 중위표기법 -> 후위표기법

1. '(' 를 만나면 스택에 푸시한다.

2. ')' 를 만나면 스택에서 '('가 나올 때까지 팝하여 출력하고 '(' 는 팝하여 버린다.

3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 푸시한다.

4. 피연산자는 그냥 출력한다.

5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 팝하여 출력한다.

(2) 후위표기법을 연산

1. 숫자를 만나면 숫자는 스택에 푸시한다.

2. 연산자를 만나면 스택에서 팝을 두 번하여 그 두 데이터를 가지고 연산한 다음 그 결과를 스택에 다시 푸시한다.

#include <stdio.h> #define MAX 100 int stack[MAX];        // 스택의 긴  통 int top;            // 스택의 상단 void init_stack(void){     top = -1; } int push(int t){     if (top >= MAX - 1){         printf("\n    Stack overflow.");         return -1;     }     stack[++top] = t;     return t; } int pop(void){     if (top < 0){         printf("\n   Stack underflow.");         return -1;     }     return stack[top--]; } void print_stack(void){     int i;     printf("\n Stack contents : TOP ----> Bottom\n");     for (i = top; i >= 0; i--){         printf("%-6d", stack[i]);     } } // 스택의 TOP의 값을 가져온다. int get_stack_top(void){     return (top < 0) ? -1 : stack[top]; } // 스택이 비어있는지 검사 int is_stack_empty(void){     return (top < 0); } // k 가 연산자인지 판단한다. int is_operator(int k){     return (k == '+' || k == '-' || k == '*' || k == '/'); } // 후위표기법 수식이 적접한가 체크 int is_legal(char *s){     int f = 0;     while (*s){         // 처음 공백 넘어가기         while (*s == ' '){             s++;         }         if (is_operator(*s)){             f--;         }         else{             f++;             while (*s != ' '){                 s++;             }         }         if (f < 1) break;         s++;     }     return (f == 1); } // 연산자의 우선순위를 수치로 변환해준다. int precedence(int op){     if (op == '(') return 0;     if (op == '+' || op == '-') return 1;     if (op == '*' || op == '/') return 2;     else return 3; } // 중위표기법을 후위표기법으로 변환 void postfix(char *dst, char *src){     char c;     init_stack();     while (*src){         if (*src == '('){             push(*src);             src++;         }         else if (*src == ')'){             while (get_stack_top() != '('){                 *dst++ = pop();                 *dst++ = ' ';             }             pop();             src++;         }         else if (is_operator(*src)){             while (!is_stack_empty() &&                 precedence(get_stack_top()) >= precedence(*src)){                 *dst++ = pop();                 *dst++ = ' ';             }             push(*src);             src++;         }         else if (*src >= '0' && *src <= '9'){             do{                 *dst++ = *src++;             } while (*src >= '0' && *src <= '9');             *dst++ = ' ';         }         else{             src++;         }     }     while (!is_stack_empty()){         *dst++ = pop();         *dst++ = ' ';     }     dst--;     *dst = 0; } // 후위표기법을 계산한다. int calc(char *p){     int i;     init_stack();     while (*p){         if (*p >= '0' && *p <= '9'){             i = 0;             do{                 i = i * 10 + *p - '0';                 p++;             } while (*p >= '0' && *p <= '9');             push(i);         }         else if (*p == '+'){             push(pop() + pop());             p++;         }         else if (*p == '*'){             push(pop() * pop());             p++;         }         else if (*p == '-'){             i = pop();             push(pop() - i);             p++;         }         else if (*p == '/'){             i = pop();             push(pop() / i);             p++;         }         else{             p++;         }     }     return pop(); } void main(void){     int r;     char exp[256] = "2*3+6/2-4";     char pf[256];     postfix(pf, exp);     printf("\nPostfix : %s", pf);     if (!is_legal(pf)){         printf("\n Exprssion is legal!");         exit(1);     }     r = calc(pf);     printf("\nAnswer : %d", r);     return 0; }

출처: https://hyeonstorage.tistory.com/348?category=622873 [개발이 하고 싶어요]