postfix... 이거 어떤책에 나오는 소스인가요?
글쓴이: hyunuck / 작성시간: 일, 2003/04/13 - 1:02오전
자료구조시간에, 피곤해서 잠깐 자고있어났더니..
postfix 라는걸 했더군요...
책에도 없는 소스를 주석 달아오라네요..^^
뒤적이다보니 외국사이트에도 올라가있고,.. 꽤 알려진 책에서 나온 소스같던데, 어떤 책인지 좀 알려주시면 감사~ ^^;
#include <stdio.h> #include <stdlib.h> #define MAXCOLS 60 #define TRUE 1 #define FALSE 0 #define PLUS 1 #define MINUS 1 #define MUL 2 #define DIV 2 struct stack { int top; char items[MAXCOLS]; }; int empty(struct stack *ps) { if(ps->top == -1) return TRUE; else return FALSE; } char pop(struct stack *ps) { if(empty(ps)) { printf("%s", "stack underflow"); exit(1); } return (ps->items[ps->top--]); } void popandtest(struct stack *ps, char *px, int *pund) { if(empty(ps)) { *pund = TRUE; return; } *pund = FALSE; *px = ps->items[ps->top--]; return; } void push(struct stack *ps, char x) { ps->items[++(ps->top)] = x; return; } int isoperand(char ch) { if((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) return TRUE; return FALSE; } int prcd(char op1, char op2) { switch(op1) { case '+' : op1 = PLUS; break; case '-' : op1 = MINUS; break; case '*' : op1 = MUL; break; case '/' : op1 = DIV; break; } switch(op2) { case '+' : op2 = PLUS; break; case '-' : op2 = MINUS; break; case '*' : op2 = MUL; break; case '/' : op2 = DIV; break; } if(op1 == '(') return FALSE; if(op2 == '(') return FALSE; if(op2 == ')') return TRUE; if(op1 >= op2) return TRUE; else return FALSE; } void postfix(char in[], char po[]) { int position, und; int outpos = 0; char topsymb = '+'; char symb; struct stack opstk; opstk.top = -1; for(position = 0; (symb = in[position]) != '\0'; position++) if(isoperand(symb)) po[outpos++] = symb; else { popandtest(&opstk, &topsymb, &und); while(!und && prcd(topsymb, symb)) { po[outpos++] = topsymb; popandtest(&opstk, &topsymb, &und); } if(!und) push(&opstk, topsymb); if(und || (symb != ')')) push(&opstk, symb); else topsymb = pop(&opstk); } while(!empty(&opstk)) po[outpos++] = pop(&opstk); po[outpos] = '\0'; return; } void main(void) { char infix[MAXCOLS]; char postr[MAXCOLS]; int pos = 0; while((infix[pos++] = getchar()) != '\n'); infix[--pos] = '\0'; printf("%s%s", "the original infix expression is ", infix); postfix(infix, postr); printf("\n%s\n", postr); }
Forums:
웬만한 자료구조 알고리즘 책에는 다 나옵니다.전위, 후위, 중위.
웬만한 자료구조 알고리즘 책에는 다 나옵니다.
전위, 후위, 중위... 연산 계산기 만들기 -_-;
댓글 달기