表达式计算
表达式计算 是对表达式按照预定规则进行计算求值的过程，因此，表达式计算也称作表达式求值。我们使用表达式表示方法的一般有三种。
下令一个数、一个操作符或一个括号都是一个单位。
前缀表达式
本节只考虑加减乘除四种运算。
一种操作符写在操作数前的表达式表示法，不需要考虑计算顺序。
例子
中缀表达式（见下文）\(a \times (b + c) \div d\) 可变为前缀表达式 \(\div \times a + b \ c \ d\)。
一般用递归计算。令表达式字符串为 \(s\)，\(s(i)\) 是 \(s\) 的第 \(i\) 个单位，\(q\) 为当前应处理到的单位编号，初始 \(q = 1\)。
每次进入递归函数，若 \(s(q)\) 是数字，返回数字；否则 \(q \gets q + 1\)，从 \(q\) 递归一次；再 \(q \gets q + 1\)，从 \(q\) 递归一次（第一次递归后的 \(q\) 已经改变了），得到两个数字进行计算，返回。
后缀表达式
本节只考虑加减乘除四种运算。
一种操作符写在操作数后的表达式表示法，不需要考虑计算顺序。
例子
中缀表达式（见下文）\(a \times (b + c) \div d\) 可变为前缀表达式 \(a \ b \ c + \times \ d \ \div\)。
一般用栈计算。令表达式字符串为 \(s\)，\(s(i)\) 是 \(s\) 的第 \(i\) 个单位，\(i\) 为当前处理到的单位编号。
从 \(i = 1\) 开始正序遍历 \(s\)。若 \(s(i)\) 是数字，直接压入栈中；否则取出栈中两个数字进行计算，然后压入栈中，注意先取出的是在后面的操作数。
中缀表达式
本节只考虑加减乘除四种运算。
这是我们最常用的表达式表示法，操作符写在操作数中间。计算时先算括号，内侧括号优先，再算乘除法，最后算加减法，同级操作从左到右计算。这里的括号只有小括号 ( 和 )。
例子
\(a \times (b + c) \div d\)
\(3 \times (5 + 7) \div 2 = 18\)
递归计算
令当前表达式字符串为 \(s\)，\(s(i)\) 是 \(s\) 的第 \(i\) 个单位。
- 若 \(s\) 首尾有多余的括号，去除；
- 找到优先级最低的一个运算符 \(s(x)\)，即在以 \(s(x)\) 为界分开后计算再拼接的答案不会发生改变；
- 递归计算以 \(s(x)\) 为界分开的两个表达式；
- 合并计算完的两个表达式，让 \(s(x)\) 为操作符对这两个数进行计算，返回。
得到的答案就是表达式计算后的结果。
转为后缀表达式
令当前表达式字符串为 \(s\)，\(s(i)\) 是 \(s\) 的第 \(i\) 个单位，\(t\) 是处理出的后缀表达式，\(i\) 为当前处理到的单位编号。
维护一个符号栈。
从 \(i = 1\) 开始正序遍历 \(s\)。若 \(s(i)\) 为数字，直接加入 \(t\) 中；若 \(s(i)\) 为左括号，压入栈中；
若 \(s(i)\) 是右括号，则一直让栈弹出直到第一个左括号被弹出，弹出的数字按弹出顺序加入 \(t\)；
若 \(s(i)\) 是符号，则一直让栈弹出直到栈顶的符号优先级小于 \(s(i)\) 或为左括号，弹出的符号入栈，左括号不弹出。
以上（前中后缀表达式）的计算方法若要加入新的符号则只需考虑优先级即可。