자료구조 중위표기식을 후위표기식 나타낸 예제

수식의 계산

수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)의 3가지 방법이 존재합니다

중위는 연산자가 피연산자 사이에 있는 방식으로 흔히 보는 방식을 뜻하며

연산자가 피연산자 뒤에 있으면 후위, 연산자가 연산자 앞에 있으면 전위라고 합니다

프로그래머가 수식을 중위 표기법으로 작성하면 컴파일러는

이것을 후위표기법으로 변환한 다음 이를 스택을 이용해 계산합니다

중위표기식을 후위표기식으로 구현한 예제

#include<stdio.h> #include<string.h> typedef struct StackType{ int stack[10]; int top; } Stack; void init(Stack *s){ s->top=-1; } void push(Stack *s, char item){ s->stack[++(s->top)]=item; } char pop(Stack *s){ return s->stack[ (s->top)-- ]; } char peek(Stack *s){ return s->stack[s->top]; } int prec(char op){ //precedence 우선순위반환 switch(op){ case '(': case ')' : return 0; case '+': case '-' : return 1; case '*': case '/' : return 2; } return 999; } int isEmpty(Stack *s){ return s->top == -1; } void infix2postfix( char expr[]){ Stack s; int i, ln = strlen(expr); char ch, returned_op; init(&s); for(i=0;i<ln;i++){ ch = expr[i]; switch(ch){ case '(': push(&s, ch); break; case '+': case '-': case '*': case '/': while( !isEmpty(&s) &&   ( prec(ch) <= prec(peek(&s)) )   ) printf("%c",pop(&s)); push(&s,ch); break; case ')': returned_op = pop(&s); while(returned_op != '('){ printf("%c", returned_op); returned_op = pop(&s); } break; default: printf("%c",ch); break; } //switch }//for while(!isEmpty(&s)) printf("%c",pop(&s)); printf("\n"); } void main(){ printf("(2+3)*4+9 = "); infix2postfix( "(2+3)*4+9" ); printf("(3*4)-74/2+(3-2) = "); infix2postfix("(3*4)-74/2+(3-2) = "); printf("3+4="); infix2postfix("3+4"); }

실행화면

읽어주셔서 감사합니다