区别
前缀,中缀,后缀表达式是算数表达式的三种区分。前缀表达式和后缀表达式取消了表达式中的符号,前缀表达式又称为波兰表达式,后缀表达式来自于波兰表达式,所以又称为逆波兰表达式。我们接下来分别考虑这些表达式。
中缀表达式
中缀表达式实际上就是我们所使用的四则运算式。
(9+3)*2+5 就是中缀表达式(四则运算式)
后缀表达式
后缀表达式
先看一个例子
对上面的前缀表达式改成后缀表达式
9 3 +2 * 5 +
后缀表达式的形式和数据结构中的栈有很大的关系。
后缀表达式的理论实现
栈:
后缀表达式的实现依赖于栈。
-
回顾一下栈的规则,栈的基本规则是先进后出。
后缀表达式的规则
后缀表达式的实现规则
-
遇到数字直接进栈
-
遇到计算符号后将先进栈的两个数从其中取出,做相应的计算后再进栈。
前缀表达式
前缀表达式相对使用的频率更低(因为确实很反人类),和后缀表达式互为逆序。
前缀表达式和后缀表达式使用的规则相类似,唯一的区别在于前缀表达式从右到左遍历中缀表达式,后缀表达式从左到右遍历中缀表达式。
前缀表达式的例子:
+ * + 3 9 2 5