题目大意：给一个中缀表达式，转换成后缀表达式。
这类题一直不太会，让我想就是建一棵表达式树，然后后续遍历算了，可是建树的过程实在太麻烦了。今天才看到有中缀表达式转换成后缀表达式的算法，可以用栈进行实现，我现在才知道...
算法如下：
这里假定操作数均为一位数字，操作符只有（、）、+、-、*和/，结果保存到postfix数组里，还要用到一个栈来保存运算符。
从左向右扫描表达式，如果当前字符为：
（1）数字，将该数字添加到postfix末尾。
（2）（，将（压入栈中。
（3）），如果当前栈顶元算不是（，将栈中的运算符逐个弹出并追加到postfix末尾，知道栈顶为（，弹出但不追加。
（4）+、-、*、/。这里假定（优先级为0，+、-优先级为1，*和/优先级为2。如果栈为空 或者 当前字符的优先级高于栈顶元素的优先级时，将当前字符压栈；否则将栈中大于等于当前字符优先级的元素弹出并追加到postfix末尾，然后将当前字符压栈。
当扫描完成后，如果栈非空，逐个弹出栈中元素并追加到postfix尾部。
1 #include <cstdio> 2 #include <cctype> 3 #include <stack> 4 using namespace std; 5 6 int priority(char ch) 7 { 8 if (ch == '+' || ch == '-') return 1; 9 else if (ch == '*' || ch == '/') return 2; 10 return 0; 11 } 12 13 int main() 14 { 15 #ifdef LOCAL 16 freopen("in", "r", stdin); 17 #endif 18 int T; 19 scanf("%d", &T); 20 getchar(); 21 char tmp[20], infix[60], postfix[60]; 22 gets(tmp); 23 while (T--) 24 { 25 int n = 0; 26 while (gets(tmp)) 27 { 28 if (tmp[0] == ' ') break; 29 infix[n++] = tmp[0]; 30 } 31 infix[n] = 0; 32 stack<char> op; 33 int k = 0; 34 for (int i = 0; i < n; i++) 35 { 36 if (isdigit(infix[i])) postfix[k++] = infix[i]; 37 else if (infix[i] == '(') op.push('('); 38 else if (infix[i] == ')') 39 { 40 while (op.top() != '(') 41 { 42 postfix[k++] = op.top(); 43 op.pop(); 44 } 45 op.pop(); 46 } 47 else 48 { 49 if (op.empty() || priority(infix[i]) > priority(op.top())) op.push(infix[i]); 50 else 51 { 52 while (!op.empty() && priority(op.top()) >= priority(infix[i])) 53 { 54 postfix[k++] = op.top(); 55 op.pop(); 56 } 57 op.push(infix[i]); 58 } 59 } 60 } 61 while (!op.empty()) 62 { 63 postfix[k++] = op.top(); 64 op.pop(); 65 } 66 postfix[k] = 0; 67 printf("%s ", postfix); 68 if (T) printf(" "); 69 } 70 return 0; 71 }