中缀和后缀表达式之间的转换
举例:
(3 + 4) × 5 - 6 就是中缀表达式
- × + 3 4 5 6 前缀表达式
3 4 + 5 × 6 - 后缀表达式
前缀表达式(前缀记法、波兰式)
前缀表达式的运算符位于操作数之前。
中缀表达式(中缀记法)
中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。
后缀表达式(后缀记法、逆波兰式)
后缀表达式与前缀表达式类似,只是运算符位于操作数之后。
转换
中缀转后缀:先将中缀表达式表示成根树形式:
根树与表达式的关系:前序遍历根树即得到前缀表达式(波兰式
),中序遍历根树即得到中缀表达式,后序遍历根树即得到后缀表达式.
根树的例子:
因此对上一步形成的根树后序遍历,就完成了中缀转后缀.
后缀转中缀:操作数从左到右依次入栈,遇到计算符号就将栈顶和次栈顶的两个数取出计算,结果放入栈顶
参考:离散数学及其应用(第六版)
http://blog.csdn.net/antineutrino/article/details/6763722/