前缀中缀后缀表达式

hwhwh · 2018-10-08 19:45:47 · 个人记录

前缀中缀后缀表达式

前缀表达式(Prefix Notation)

• 指将运算符写在前面操作数写在后面的不包含括号的表达式，而且为了纪念其发明者波兰数学家Jan Lukasiewicz所以前缀表达式也叫做“波兰表达式”。比如- 1 + 2 3

后缀表达式(Postfix Notation)

• 与之相反，是指运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。比如1 2 3 + -

中缀表达式(Infix Notation)

• 就是常用的将操作符放在操作数中间的算术表达式。前缀表达式和后缀表达式相对于中缀表达式最大的不同就是去掉了表示运算优先级的括号，比如1-2+3

现在让我们先回想一下小学数学中关于中缀表达式求值的相关的规则：

• 有括号的情况下，先计算括号内，再计算括号外

• 在无括号的情况下，考虑运算的优先级，先乘除，后加减

• 同样优先级的情况下，从左至右进行计算

在中缀表达式的情况下求值，既要考虑括号，优先级，还要考虑操作出现的先后顺序。

但是，作为计算机，其计算过程就显的比较复杂，对于一个中缀表达式，需要不停地对表达式进行多次遍历，来查找相应的计算的信息。这样从算法复杂度上来说，是不可取的。

前缀表达式和后缀表达式相对于人们常用的中缀表达式最大的不同就在于表达式中的运算符是按照一定的顺序出现（接下来会具体讲解），所以求值过程中并不需要在表达式中使用括号来指定运算顺序，也不需要在计算过程中其中考虑运算符号的优先级。在采用辅助数据结构的情况下，只需要对表达式进行一次遍历即可计算出结果，大大降低了算法复杂度，也更加符合传统计算机的工作方式。

表达式的转换

在对前缀中缀和后缀表达式进行了简单的介绍以后，接下来对表达式之间的转换进行一个简单的阐述，在这里首先以中缀表达式转换后缀表达式为例进行较详细的讲解。

方法一 人工转换法

• 假设有一个中缀表达式a+b*c-(d+e)

  1. 首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))

  2. 然后将所有运算符放到括号后面，这样就变成了((a(bc)* )+ (de)+ )-

  3. 把所有括号去掉abc*+de+-，最后得出的结果就是后缀表达式

• 上面这个方法可以在比如做题分析的时候用人脑的时候使用，接下来介绍用程序实现将中缀转换成后缀表达式的思路

方法二 建栈求解法

中缀转后缀

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
   3. 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是左括号“(”，则直接压入S1；
   2. 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
6. 重复步骤(2)至(5)，直到表达式的最右边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。

   中缀转前缀

遵循以下步骤：

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
   3. 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是右括号“)”，则直接压入S1；
   2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
6. 重复步骤(2)至(5)，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

方法三 建树求解法

与二叉树关系

• 前缀表达式对应于二叉树的前序遍历

• 中缀表达式对应于二叉树的中序遍历

• 后缀表达式对应于二叉树的后序遍历

• 例题：表达式“X=A+B*(C-D)/E”的后缀表示形式可以为？

按照操作符的优先级，其二叉树的生成过程：

1. 括号的优先级最高，根为-,左孩子为C,右孩子为D

2. 接下来是乘法，根为*,左孩子为B，右孩子为1的树

3. 接下来是除法，跟为/，左孩子为2的树，右孩子为E

4. 接下来是加法，根为+，左孩子为A,右孩子为3的树

5. 接下来是=号，左孩子是X，右孩子是4的树

• 剩下的就是前序和后序遍历二叉树即可