缀表达式： a op b 形式的表达式。当运算符位于每对操作数之间时。
后缀表达式： ab op 形式的表达式。当每对操作数都跟随一个运算符时。
为什么表达式的后缀表示？
编译器从左到右或从右到左扫描表达式。
考虑下面的表达式： a op1 b op2 c op3 d
如果 op1 = +, op2 = *, op3 = +
编译器首先扫描表达式以计算表达式 b * c，然后再次扫描表达式以将 a 添加到它。然后在另一次扫描后将结果添加到 d。
重复扫描使其效率非常低。求值前最好将表达式转换为后缀（或前缀）形式。
后缀形式的对应表达式为abc*+d+。可以使用堆栈轻松评估后缀表达式。我们将在单独的帖子中介绍后缀表达式评估。
算法
1. 从左到右扫描中缀表达式。
2. 如果扫描的字符是操作数，则输出它。
3. Else,
3.1. 如果扫描的运算符的优先级大于堆栈中运算符的优先级（或堆栈为空或堆栈中包含 '(' )，则压入它
3.2. 否则，从堆栈中弹出所有优先级大于或等于扫描运算符的运算符。这样做之后，将扫描的操作符推入堆栈。（如果在弹出时遇到括号，则停在那里并将扫描的运算符压入堆栈。）
4. 如果扫描的字符是 '('，则将其压入堆栈。
5. 如果扫描的字符是 ')'，弹出堆栈和输出它，直到一个“（”遇到，并丢弃两个括号。
6. 重复步骤2-6，直到缀表达式被扫描。
7. 打印输出
8. 从栈中弹出并且输出，直到它不是空的。
下面是上述算法的实现
#include<bits/stdc++.h> using namespace std; int prec(char c) { if(c == '^') return 3; else if(c == '/' || c=='*') return 2; else if(c == '+' || c == '-') return 1; else return -1; } void infixToPostfix(string s) { stack<char> st; string result; for(int i = 0; i < s.length(); i++) { char c = s[i]; if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) result += c; else if(c == '(') st.push('('); else if(c == ')') { while(st.top() != '(') { result += st.top(); st.pop(); } st.pop(); } else { while(!st.empty() && prec(s[i]) <= prec(st.top())) { result += st.top(); st.pop(); } st.push(c); } } while(!st.empty()) { result += st.top(); st.pop(); } cout << result << endl; } int main() { string exp = "a+b*(c^d-e)^(f+g*h)-i"; infixToPostfix(exp); return 0; }
输出
abcd^e-fgh*+^*+i-
