【数据结构】栈在求值中的应用-前缀、中缀、后缀表达式

1. 前缀、中缀、后缀表达式

中缀表达式：运算符在两个操作数中间。

后缀表达式：运算符在两个操作数后面。

前缀表达式：运算符在两个操作数前面。

波兰表达式=前缀表达式。

逆波兰表达式=后缀表达式。

在中缀表达式中，经常需要界限符来反映运算顺序，而前缀表达式和后缀表达式则不需要。计算机中经常使用前缀或后缀表达式来处理此类求值问题。

2. 后缀表达式的计算

“左优先”原则：只要左边的运算符能先计算，就优先算“左边”的。

用栈实现后缀表达式的计算规则：

1. 从左往右扫描下一个元素，直到处理完所有元素。
2. 若扫描到操作数则压入栈，并回到1；否则执行3。
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到1。

说明：如果中缀表达式转后缀表达式正确，按照“左优先”原则，他们的运算顺序是不会改变的。

解析：根据后缀表达式的计算规则，从左往右扫描，A和B先入栈，当遇到运算符时，B先出栈作为右操作数，A紧接着出栈作为左操作数，运算结果得到一个值，重新压入栈中。然后继续扫描，后面的过程依次类推。

若表达式合法，则最后栈中只会留下一个元素，就是最终结果。

3. 前缀表达式的计算

“右优先”原则：只要右边的运算符能先机身，就优先算“右边”的。

用栈实现前缀表达式的计算规则：

1. 从右往左扫描下一个元素，直到处理完所有元素。
2. 若扫描到操作数则压入栈，并回到1；否则执行3。
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1。

说明：如果中缀表达式转前缀表达式正确，按照“右优先”原则，他们的运算顺序是不会改变的。

解析：根据前缀表达式的计算规则，从右往左扫描，F和E先入栈，当遇到运算符时，E先出栈作为左操作数，F紧接着出栈作为右操作数，运算结果得到一个值，重新压入栈中。然后继续扫描，后面的过程依次类推。

若表达式合法，则最后栈中只会留下一个元素，就是最终结果。

重点说明：一个中缀表达式可以对应多个后缀、前缀表达式，我们这里强调“左优先”和“右优先”原则，是让一个中缀表达式只对应一个后缀或前缀表达式，确保算法的“确定性”。

4. 中缀表达式转后缀表达式的计算

“左优先”原则:只要左边的运算符能先计算，就优先算左边的。

中缀表达式转后缀表达式的计算规则：

1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
2. 从左到右处理各个元素，直到末尾，可能遇到三种情况：

• 若遇到操作数。直接加入后缀表达式。
• 若遇到界限符。遇到“（”直接入栈；遇到“）”则依次弹出栈内运算符并加入后缀表达式，直到弹出“（”为止。

注意：“（”不能加入后缀表达式。

• 若遇到运算符。依次弹出栈内优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，碰到“（”或栈为空则停止。之后把当前运算符入栈。

3. 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

说明：* / 优先级高于 * - 。

解析：从左往右扫描，当扫描到箭头所示位置时，遇到“）”，那么依次弹出栈中的运算符“-”（蓝色），直到遇到“（”停止，再往后扫描到“-”，由于栈中剩余了“*”和“+”，优先级高于或等于“-”，那么依次弹出（黄色），将“-”入栈（红色）。处理结束，最终表达式为：

重点说明：在处理这种问题的时候要关注栈是否溢出的问题。

从以上我们也可以看出：后缀和前缀表达式用于存放不能确定运算次序的操作数。而中缀表达式转后缀表达式用于存放不能确定运算次序的操作符。

5. 中缀表达式的计算

中缀表达式是“”中缀转后缀”和“后缀表达式”两个算法的结合。

中缀表达式的计算规则：

1. 初始化两个栈，“操作数栈”和“运算符栈”。
2. 从左往右扫描，若扫描到操作数，压入操作数栈。
3. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果压回操作数栈）。

解析：从左往右扫描，扫描到操作数压入到操作数栈，扫描到运算符压入到运算符栈。如图当扫描到箭头位置时，操作数栈中已经有了A和B两个元素，“-”本来进入运算符栈，但“-”的运算符等于“+”的，那么“+”就要弹出，运算符弹出，就要相应弹出操作数栈栈顶的两个元素A和B，并做运算，把它们结果再压入操作数栈中。而后“-”压入运算符栈。依次往后，最终得到后缀表达式。。

6. 小结