江小南

V1

2023/02/14阅读:30主题:萌绿

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

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. 从左到右处理各个元素,直到末尾,可能遇到三种情况:
  • 若遇到操作数。直接加入后缀表达式。
  • 若遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式,直到弹出“(”为止。

注意:“(”不能加入后缀表达式。

  • 若遇到运算符。依次弹出栈内优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,碰到“(”或栈为空则停止。之后把当前运算符入栈。
  1. 按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式。

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

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

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

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

5. 中缀表达式的计算

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

中缀表达式的计算规则:

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

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

6. 小结

分类:

后端

标签:

数据结构与算法

作者介绍

江小南
V1