前缀、中缀、后缀表达式（逆波兰表达式）

[Zakariyya]

eg: 
( 3 + 4 ) * 5 - 6 

前缀表达式
- * + 3 4 5 6 

中缀表达式
( 3 + 4 ) * 5 - 6 

后缀表达式
3 4 + 5 * 6 -

前缀表达式（波兰表达式）

运算符位于操作数之前，从右至左扫描

( 3 + 4 ) * 5 - 6 

1. 依次将 6、5、4、3 压入栈中
2. 遇到 + 运算符，弹出3和4（栈顶和次栈顶 元素），计算出 3 + 4 = 7 的值，再将7入栈
3. 接下来是 运算符，弹出7和5，计算出 7 5 = 35，将35入栈
4. 最后是 - 运算符，计算出 35-6 （栈顶 减去 次栈顶）的值，29，结束

中缀表达式

就是我们日常看到的表达式，对计算机来说却不友好

因此在计算结果时，往往会将中缀表达式转成其他表达式，一般为后缀表达式

后缀表达式（逆波兰表达式）

运算符位于操作数之后，从左至右扫描表达式

( 3 + 4 ) * 5 - 6 

1. 从左至右扫描表达式，将3和4压入栈
2. 遇到 + 运算符，弹出4和3（栈顶和次栈顶 元素），计算出 4 + 3 = 7 的值，再将7放入栈
3. 将5入栈
4. 接下来是 运算符，弹出5和7，计算出 7 5 = 35 ，将35入栈
5. 将6入栈
6. 最后是 - 运算符，计算出 35-6 的值（次栈顶 减去 栈顶），29，结束

应用

中缀表达式 转成 后缀表达式

1 + ( ( 2 + 3 ) * 4 ) - 5

扫描到的元素	s2（栈底 -> 栈顶）	s1（栈底 -> 栈顶）	说明
1	1	null	数字，直接入栈
+	1	+	s1维空，运算符直接入栈
(	1	+(	左括号，直接入栈
(	1	+((	同上
2	12	+((	数字
+	12	+((+	s1栈顶为左括号，运算符直接入栈
3	123	+((+	数字
)	123+	+(	右括号，弹出运算符直到遇到左括号
*	123+	+(*	s1栈顶为左括号，运算符直接入栈
4	123+4	+(*	数字
)	123+4*	+	右括号，弹出运算符直到遇到左括号
-	123+4*+	-	-与+优先级相同，因此弹出 + ，再压入 -
5	123+4*+5	-	数字
到达最右端	123+4*+5-	空	s1中剩余的运算符

• 取出：- 5 + * 4 + 3 2 1
• 然后逆向：1 2 3 + 4 * + 5 -

注意

上表的 s2 ，在整个转换过程中，没有pop操作，全程一直在压栈，没有出栈操作，而且后面还需要逆序输出

因此这里的 s2 使用 数组或List 更适合