후위식 계산프로그램은 피연산자를 스택에 push하고 연산자를 만났을 때 pop하여 연산 후 다시 push하는 과정이었지만
중위수식을 후위식으로 변환하는 프로그램은 반대로 연산자를 push하고 피연산자는 그대로 출력합니다.
중위 수식을 후위 수식으로 변환할 떄 중요한 것은 연산자의 우선순위입니다.
괄호와 숫자로 구성된 중위 수식을 후위 수식으로 변환 할 때 연산자의 순위는 다음과 같습니다.
괄호 < +, - 연산자 < *, / 연산자
가장 중요한 것은 현재 처리중인 연산자와 스택에 있는 연산자의 우선순위를 이용한 처리 입니다.
1. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 낮을 때
예를들어) 처리중인 연산자: + or - , 스택에있는 연산자: * or / 일 때
=> 스택에 있는 연산자를 pop 해서 출력 후 처리 중인 연산자를 push 합니다.
2. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 클 때
예를들어) 처리중인 연산자: * or / , 스택에 있는 연산자: +, - 일 때
=> 현재 처리 중인 연산자를 그냥 push합니다.
3. 현재 처리중인 연산자의 우선순위와 스택에 있는 연산자의 우선순위가 같을 때
예를들어) 처리중인 연산자: +, 스택에 있는 연산자: - 일 때
=> 1번 경우와 똑같이 처리한다.
이유는 간단한 예시를 들면 쉽게 알 수 있습니다.
ex) 5-4+3일 때, 5/4*3 일 때
=> 우선순위를 어떻게 하느냐에 따라 답이 달라집니다.
코드
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #pragma warning(disable:4996) #include<stdio.h> #include<stdlib.h> #include<string.h> #define max 100 typedef struct { char data[max]; int top; }stackType; int check(char* exp); void init(stackType* s); void push(stackType* s, char x); int pop(stackType* s); int is_full(stackType* s); int is_empty(stackType* s); char peek(stackType* s); void infix_to_postfix(const char* s); int prec(char op); int main() { infix_to_postfix("(2+3)*4+9"); return 0; } void init(stackType* s) { s->top = -1; } int is_full(stackType* s) { return s->top == max - 1; } int is_empty(stackType* s) { return s->top == -1; } void push(stackType* s, char x) { if (is_full(s)) { fprintf(stderr, "원소가 다 찼습니다.\n"); return; } s->data[++(s->top)] = x; } char peek(stackType* s) { if (is_empty(s)) { fprintf(stderr, "원소가 없습니다.\n"); exit(1); } return s->data[(s->top)]; } int pop(stackType* s) { if (is_empty(s)) { fprintf(stderr, "원소가 없습니다\n"); exit(1); } return s->data[(s->top)--]; } void infix_to_postfix(const char* s) { char ch,top_op; int n = strlen(s); stackType st; init(&st); for (int i = 0; i < n; i++) { ch = s[i]; switch (ch) { case '+': case '-':case '*':case '/': while (!is_empty(&st) && (prec(ch) <= prec(peek(&st)))) { printf("%c", pop(&st)); } push(&st, ch); break; case '(': push(&st, ch); break; case ')': top_op = pop(&st); while (top_op != '(') { printf("%c", top_op); top_op = pop(&st); } break; //숫자일 떈 그대로 출력 default: printf("%c", ch); break; } } //아직 스택에 남아있다면 다 뽑아냄 while (!is_empty(&st)) printf("%c", pop(&st)); } int prec(char op) { switch (op) { case '(':case ')': return 0; case '+':case '-': return 1; case '*':case '/':return 2; } return -1; } | cs |
결과
'자료구조 > 스택' 카테고리의 다른 글
스택을 이용한 후위 표기식 계산 프로그램 (0) | 2020.04.09 |
---|---|
스택을 이용한 괄호검사 프로그램 (0) | 2020.04.09 |
top변수와 스택배열을 구조체로묶은 스택 구현 (0) | 2020.04.09 |
구초체배열을 이용한 스택 구현 (2) | 2020.04.09 |
전역 변수를 이용한 간단한 스택 구현 (0) | 2020.04.09 |