波兰式与逆波兰式【1】
三种算术表达式
中缀表达式：就是类似于数学里手写的式子。例子： 4 + 2 × 3 − 10 / 5 4+2\times3-10/5 4+2×3−10/5 、 a + b ∗ c − d / e a+b*c-d/e a+b∗c−d/e 等
后缀表达式：运算符在前，其运算符的两个操作数相对在后的表达式（“运算数 运算数 运算符”），也称“逆波兰式”
中缀表达式 后缀表达式
a+b ab+
a+b*c-d/e abc*+de/-
10/(7-(1+2))*3 10712+-/3*
10/(7-(1+2))*3-(2+(1+1)) 10712+-/3*211++-
转换步骤：（中–>后)，注：括号不计入后缀表达式，
① 确定表达式的各个运算符的转换次序（先转换哪个后转换哪个），对于同级
例如： 15 / ( 7 − ( 1 + 2 ) ⏟ 1 ⏟ 2 ) ⏟ 3 ∗ 3 ⏟ 4 \underbrace{\underbrace{15/(\underbrace{7-\underbrace{(1+2)}_{1}}_{2})}_{3}*3}_{4} 4 3 15/(2 7−1 (1+2))∗3
②按照确定好的次序以及黄字部分的规则，依次把子中缀表达式变为子后缀表达式并组合成一个新的操作数
第一步：括号优先级最高，先转换括号里的，（1+2） —> 12+ ，表达式12+看作一个新的运算数，我用一个[ ]括起来视为整体，原表达式变为： 15 / ( 7 − [ 12 + ] ) ∗ 3 15/(7-[12+])*3 15/(7−[12+])∗3
第二步：(7-[12+])—> 7[12+]-，去掉 [ ] 变为：712+ - 然后又把它视为一个新运算数，用[ ]括起来，则原表达式变为： 15 / [ 712 + − ] ∗ 3 15/[712+-]*3 15/[712+−]∗3
第三步：15/[712+ -]—>15[712+ -] 去掉 [ ] 变为：15712+ -/ 然后又把它视为一个新运算数…
…
③重复②的操作，直到每个运算次序对应的表达式都转换，最后剩下一个表达式-----后缀表达式
注意：由于有些表达式之间的运算符优先级相同，因此可能导致后缀表达式的结果不一致，例如：
a + b ∗ c − d / e a+b*c-d/e a+b∗c−d/e的次序可能是： a + b ∗ c ⏟ 1 − d / e ⏟ 2 ⏟ 3 ⏟ 4 \underbrace{a+\underbrace{\underbrace{b*c}_{1}-\underbrace{d/e}_{2}}_{3}}_{4} 4 a+3 1 b∗c−2 d/e或 a + b ∗ c ⏟ 1 ⏟ 2 − d / e ⏟ 3 ⏟ 4 \underbrace{\underbrace{a+\underbrace{b*c}_{1}}_{2}-\underbrace{d/e}_{3}}_{4} 4 2 a+1 b∗c−3 d/e，这就导致对于同一个中缀表达式转换后的后缀表达式结果不一样，因此规定一种顺序----优先转换左边的表达式（"尽量"先左），例如①中，对于2次序到3次序
前缀表达式：和后缀表达式恰好反过来，运算符在后，其对应的操作数相对在前的表达式（“运算符 运算数 运算数”）。
转换步骤：和中转“后”的步骤相似：①②③，区别：中转”前“的步骤③中确定表达式的运算符转换次序不是左右先而是右边优先—即优先转换右边的表达式（”尽量先右“)