C언어를 이용한 스택 전위 표기식 변환

이전에 후위 표기식 연산을 했는데 이번엔 전위 표기식 연산입니다.

* 전위 표기법(postfix) : 연산자를 피연산자의 뒷쪽에 표시하는 방법

ex)  (a+b)*c / d - e

---> ( (a+b)*c / d ) - e

---> - ( (a+b)*c / d ) e

---> - / ( (a+b)*c ) d e

---> - / * (a+b) c d e

---> - / * + a b c d e

후위연산에 대해서는 많이 있는데 전위는 잘 없더라구요. 컴퓨터는 전위표기보단 후위표기법을 더 좋아하나봐요...

1. 2개의 스택을 선언

2. 피연산자(숫자)일 때 스택2에 삽입

3. 연산자일 떄 스택 1에 삽입

4. 괄호가 있는 경우 괄호 앞에서 스택 1 pop

찾아보니 이 식을 이용해서 계산하는 건 다시 중위표기식으로 변환하여 연산하였다. 

이건 좀 더 생각해봐야겠다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <stdio.h> #include <malloc.h> typedef struct node{ char data; struct node *pre; }NODE; NODE* addNode(char data) { NODE* temp = (NODE*)malloc(sizeof(NODE)); temp->data = data; temp->pre = NULL; return temp; } char pop(NODE** top) { NODE* temp = *top; char t; if (*top == NULL) return 0; *top = (*top)->pre; t = temp->data; free(temp); return t; } void push(NODE** top, char data) { NODE* temp = addNode(data); if (*top == NULL) { *top = temp; return; } temp->pre = *top; *top = temp; } void translate(NODE** first, NODE** second, char* input) { int i = 0; for (i = strlen(input) - 1; i >= 0; i--) { switch (input[i]) { case '*': case '-': case '/': case '+': push(first, input[i]); break; case '(': push(second, ' '); push(second, pop(first)); break; default: push(second, input[i]); } } } void show(NODE* top) { while (top != NULL) { if(top->data == ')') printf(" "); else printf("%c", top->data); top = top->pre; } } int main(void) { NODE* FIRST = NULL; NODE* SECOND = NULL; char input[100] = "((((a+b)*c)/d)-e)"; translate(&FIRST, &SECOND, input); show(SECOND); return 0; }