中缀转前缀和后缀表达式

前言

我们把平时所用的标准四则运算表达式，即1 + (( 2 + 3)* 4 ) – 5这样的表达式叫做中缀表达式。因为所有运算符号都在两数字的中间。但是这样的表达式对于计算机来说是不好运算的，因为优先级的原因，在遍历这个式子时，不能将两个相邻的数字直接进行操作。20世纪50年代，波兰逻辑学家卢卡西维奇（Lukasiewicz)发明了一种不需要括号的表达式，我们把波兰式称为前缀表达式，把逆波兰式称为后缀表达式。接下来就介绍如何将中缀表达式转化为前缀、后缀表达式，这里介绍的方法是利用辅助栈。

中缀表达式转为后缀表达式

我们需要两个栈，一个用来存储运算符，一个用来输出，存储转化后的表达式。

操作方法：

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

1. 运算数：直接输出；
2. 左括号：压入堆栈；
3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
4. 运算符： • 若优先级大于栈顶运算符时，则把它压栈；

​ • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；

5. 若各对象处理完毕，则把堆栈中存留的运算符一并输出。

例子:

假定有中缀表达式1 + (( 2 + 3)* 4 ) – 5，请将它转化为后缀表达式，转换过程如下：

所得后缀表达式为1 2 3 + 4 * + 5 -

中缀表达式转为前缀表达式

操作方法：

从尾到头读取中缀表达式的每个对象，对不同对象按不同的情况处理。

1. 运算数：直接输出；
2. 左括号：压入堆栈；
3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
4. 运算符： • 若优先级大于等于栈顶运算符时，则把它压栈；

​ • 若优先级小于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于等于栈顶运算符优先级为止，然后将该运算符压栈；

5. 若各对象处理完毕，则把堆栈中存留的运算符一并输出。
6. 将得到的表达式翻转。

例子：

假定有中缀表达式1 + (( 2 + 3)* 4 ) – 5，请将它转化为前缀表达式，转化过程如下：