算术表达式 §

前/中/后缀表达式 §

• 前缀表达式（波兰式）：操作符在操作数的前面，比如 +-543；
• 中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式 3+4-5；
• 后缀表达式（逆波兰式）：操作符在操作数的后面，比如 34+5-。

前缀表达式的计算机求值 §

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

例如前缀表达式- × + 3 4 5 6：

1. 从右至左扫描，将 6、5、4、3 压入堆栈；
2. 遇到+运算符，因此弹出 3 和 4（3 为栈顶元素，4 为次顶元素，注意与后缀表达式做比较），计算出 3 + 4 的值，得 7，再将 7 入栈；
3. 接下来是×运算符，因此弹出 7 和 5，计算出 7 × 5 = 35，将 35 入栈；
4. 最后是-运算符，计算出 35 - 6 的值，即 29，由此得出最终结果。

中缀表达式转后缀表达式 §

1. 初始化两个栈：运算符栈 S1 和储存中间结果的栈 S2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压入 S2；
4. 遇到运算符时，比较其与 S1 栈顶运算符的优先级；
   1. 如果 S1 为空，或栈顶运算符为左括号(，则直接将此运算符入栈 S1；
   2. 若优先级比栈顶运算符的高，也将运算符压入S1（注意必须高于，相同和低于都不行）；
   3. 否则，将 S1 栈顶的运算符弹出并压入到 S2 中，再次转到 4.a。
5. 遇到括号时：
   1. 如果是左括号(，则直接压入 S1；
   2. 如果是右括号)，则依次弹出 S1 栈顶的运算符，并压入 S2，直到遇到左括号位置，然后将这一对括号丢弃。
6. 重复步骤2到5，直到来到表达式的最右边；
7. 将 S1 中剩余的运算符依次弹出并压入 S2；
8. 依次弹出 S2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

中缀表达式转前缀表达式 §

• 首先构造一个运算符栈，然后从右至左扫描中缀表达式。
• 如果是操作数，则直接输出，作为前缀表达式的一个直接转换表达式Temp（最后，前缀表达式由该表达式翻转得到）；
• 如果是运算符，则比较优先级：若该运算符优先级大于等于栈顶元素，则将该运算符入栈，否则栈内元素出栈并加到Temp表达式尾端，直到该运算符大于等于栈顶元素的优先级时，再将该运算符压入栈中。
• 遇到右括号直接压入栈中，
• 如果遇到一个左括号，那么就将栈元素弹出并加到Temp表达式尾端，但左右括号并不输出。
• 最后，若运算符栈中还有元素，则将元素一次弹出并加到Temp表达式尾端，最后一步是将Temp表达式翻转。