讓我想到當年的作業了……
雖然當時要寫判斷合法、中序轉後續跟算值。
不過括號問題還傻傻的暴力解,兩個禮拜才把東西生出來,真是寫到快起肖。
用stack不就輕鬆多了嗎 -.-
結果現在1hr就完成中序轉後序,囧。
operand直接output,
operator要判斷優先度。
當吃進來的operator優先度比stack[top]優先度高,
就直接push;
低或相等的話,pop到stack[top]比operator高或stack為空為止。
所以(最高,直接丟到stack。
/、*次高,若top是*、/就要先pop,再push。
+、-最低,遇到其他+、-、*、/都要pop,再push。
遇到)要無條件pop到(為止。
(算是特例,吃進來時最高,但是在top時最低。
所以+、-、*、/遇到top為(時,就可以直接push。
最後當吃進來的token為'\0'時,pop到stack為空為止即可。
最後就是output格式問題。
/* ACM 727 Equation * mythnc * 2012/01/13 09:44:34 * run time: 0.136 */ #include <stdio.h> #include <string.h> #define LINEMAX 10 #define MAXSTACK 50 void postfix(void); void pop(void); void push(char *); char stack[LINEMAX][MAXSTACK]; int count; int main(void) { scanf("%*d"); getchar(); getchar(); postfix(); return 0; } /* postfix: infix to postfix */ void postfix(void) { char line[LINEMAX]; count = 0; while (fgets(line, LINEMAX, stdin)) { line[strlen(line) - 1] = '\0'; /* operator */ if (line[0] == '+' || line[0] == '-' && strlen(line) == 1) { while (count > 0 && stack[count - 1][0] != '(') pop(); push(line); } else if (line[0] == '*' || line[0] == '/') { while (count > 0 && stack[count - 1][0] != '(' && stack[count - 1][0] != '+' && stack[count - 1][0] != '-') pop(); push(line); } else if (line[0] == '(') push(line); else if (line[0] == ')') { while (stack[count - 1][0] != '(') pop(); count--; } /* terminal condition */ else if (line[0] == '\0') { while (count != 0) pop(); printf("\n\n"); } /* operand */ else printf("%s", line); } while (count != 0) pop(); putchar('\n'); } /* pop: print out the top element */ void pop(void) { printf("%s", stack[--count]); } /* push: push line to stack */ void push(char *line) { strcpy(stack[count++], line); }
沒有留言:
張貼留言