题目大意：给一个中缀表达式，转换成后缀表达式。
这类题一直不太会，让我想就是建一棵表达式树，然后后续遍历算了，可是建树的过程实在太麻烦了。今天才看到有中缀表达式转换成后缀表达式的算法，可以用栈进行实现，我现在才知道...
算法如下：
这里假定操作数均为一位数字，操作符只有（、）、+、-、*和/，结果保存到postfix数组里，还要用到一个栈来保存运算符。
从左向右扫描表达式，如果当前字符为：
（1）数字，将该数字添加到postfix末尾。
（2）（，将（压入栈中。
（3）），如果当前栈顶元算不是（，将栈中的运算符逐个弹出并追加到postfix末尾，知道栈顶为（，弹出但不追加。
（4）+、-、*、/。这里假定（优先级为0，+、-优先级为1，*和/优先级为2。如果栈为空 或者 当前字符的优先级高于栈顶元素的优先级时，将当前字符压栈；否则将栈中大于等于当前字符优先级的元素弹出并追加到postfix末尾，然后将当前字符压栈。
当扫描完成后，如果栈非空，逐个弹出栈中元素并追加到postfix尾部。
#include <cstdio>
#include <cctype>
#include <stack>
using namespace std; int priority(char ch)
{
if (ch == '+' || ch == '-') return ;
else if (ch == '*' || ch == '/') return ;
return ;
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int T;
scanf("%d", &T);
getchar();
char tmp[], infix[], postfix[];
gets(tmp);
while (T--)
{
int n = ;
while (gets(tmp))
{
if (tmp[] == '\0') break;
infix[n++] = tmp[];
}
infix[n] = ;
stack<char> op;
int k = ;
for (int i = ; i < n; i++)
{
if (isdigit(infix[i])) postfix[k++] = infix[i];
else if (infix[i] == '(') op.push('(');
else if (infix[i] == ')')
{
while (op.top() != '(')
{
postfix[k++] = op.top();
op.pop();
}
op.pop();
}
else
{
if (op.empty() || priority(infix[i]) > priority(op.top())) op.push(infix[i]);
else
{
while (!op.empty() && priority(op.top()) >= priority(infix[i]))
{
postfix[k++] = op.top();
op.pop();
}
op.push(infix[i]);
}
}
}
while (!op.empty())
{
postfix[k++] = op.top();
op.pop();
}
postfix[k] = ;
printf("%s\n", postfix);
if (T) printf("\n");
}
return ;
}