数据结构与算法-(7)---栈的应用-(4)后缀表达式求值

🌈write in front🌈
🧸大家好，我是Aileen🧸.希望你看完之后，能对你有所帮助，不足请指正！共同学习交流.
🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如需转载还请通知⚠️
📝个人主页：Aileen_0v0🧸—CSDN博客
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​
📣系列专栏：Aileen_0v0🧸的PYTHON学习系列专栏——CSDN博客
🗼我的格言:"没有罗马,那就自己创造罗马~" 

目录

 回顾

后缀表达式运算过程

后缀表达式求值思路及代码流程

---

 回顾💫

之前我们学习了栈的应用之前,后缀表达式的转换,如有遗忘,点击👉🔗http://t.csdnimg.cn/PodbC

今天我们来学习-后缀表达式求值 问题

跟中缀转换为后缀问题不同

对后缀表达式来说 ,从左到右扫描的过程中,

由于操作符在操作数后面,

所以要暂存操作数,在碰到操作符时,再将两个暂存操作数进行实际计算

这个过程利用的就是栈的特性:操作符只作用于离他最近的两个操作数.

---

后缀表达式运算过程🍁

后缀表达式，又称逆波兰式，不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则），非常方便计算机的计算。

后缀表达式的计算过程如下：
1️⃣从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈
2️⃣重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

计算后缀表达式的动态流程如下,以1+2-3*2的后缀表达式为例:

最后得到的结果 - 3 还要 push 回栈顶

---

后缀表达式求值思路及代码流程🍂

1.首先创建空栈operandStack 用于 暂存操作数

2.将后缀表达式 用split方法解析为单词(token) 的列表

3.从左到右扫描单词列表

   如果单词是一个操作数,将单词转换为整型int,压入operandStack 栈顶

   如果单词是一个操作符 (* / + - ) , 就开始求值, 从 栈顶弹出2个操作数,先弹出的是右操作数,     后弹出的是左操作数,计算后将值重新压入栈顶.

4.单词列表扫描结束后,表达式的值就在栈顶

5.弹出栈顶的值,返回.

class Stack:#Stack---->ADTdef __init__(self):self.items =[]def isEmpty(self):return self.items == []# 满足这些属性(行为)的是栈def push(self,item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[len(self.items)-1]#def size(self):return len(self.items)def postfixEval(postfixExpr):operandStack = Stack()tokenList = postfixExpr.split()for token in tokenList:if token in "0123456789":operandStack.push(int(token))else:operand2 = operandStack.pop()operand1 = operandStack.pop()result = doMath(token,operand1,operand2)operandStack.push(result)return operandStack.pop()def doMath(op, op1, op2):if op == "*":return op1 * op2elif op == "/":return op1 / op2elif op == "+":return op1 + op2else:return op1 - op2

通过调用得到的运行结果: