前缀中缀与后缀表达式(基本理论信息)

区别

前缀,中缀,后缀表达式是算数表达式的三种区分。前缀表达式和后缀表达式取消了表达式中的符号,前缀表达式又称为波兰表达式,后缀表达式来自于波兰表达式,所以又称为逆波兰表达式。我们接下来分别考虑这些表达式。

中缀表达式

中缀表达式实际上就是我们所使用的四则运算式。

(9+3)*2+5 就是中缀表达式(四则运算式)

后缀表达式

后缀表达式

先看一个例子

对上面的前缀表达式改成后缀表达式

9 3 +2 * 5 +

后缀表达式的形式和数据结构中的栈有很大的关系。

后缀表达式的理论实现

栈:

后缀表达式的实现依赖于栈。

  1. 回顾一下栈的规则,栈的基本规则是先进后出。

后缀表达式的规则

后缀表达式的实现规则

  1. 遇到数字直接进栈

  1. 遇到计算符号后将先进栈的两个数从其中取出,做相应的计算后再进栈。

前缀表达式

前缀表达式相对使用的频率更低(因为确实很反人类),和后缀表达式互为逆序。

前缀表达式和后缀表达式使用的规则相类似,唯一的区别在于前缀表达式从右到左遍历中缀表达式,后缀表达式从左到右遍历中缀表达式。

前缀表达式的例子:

+ * + 3 9 2 5