数据结构与算法-(7)---栈的应用拓展-前缀表达式转换+求值

 

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

目录

回顾＋思路讲解

(1)中缀表达式转前缀 

(2) 前缀表达式求值

---

 

回顾＋思路讲解

之前我们介绍过了什么是后缀表达式,以及它如何通过中缀表达式进行转换,以及关于后缀表达式的求值问题,如有遗忘👉🔗http://t.csdnimg.cn/Hl4Y9

今天我们拓展一下,前缀表达式的转换和求值问题

💫中缀转后缀表达式的思路:

从左到右扫描逐个字符扫描中缀表达式的过程中，采用一个栈来暂存未处理的操作符
这样，栈顶的操作符就是最近暂存进去的，当遇到一个新的操作符，就需要跟栈顶的操作符比较下优先级，再行处理--->新符号和栈顶对比，新的高，就入栈（因为取时也先取）;       新的低，就把栈顶出栈，让栈顶的先运算

想要了解具题后缀的相关知识点点击👉🔗http://t.csdnimg.cn/9100K

中缀转前缀思路也类似,不过 

中缀表达式中运算符的优先级和结合性需要考虑，从左往右扫描的话，需要对每个运算符的优先级和结合性进行判断，才能决定是否需要先进行计算。这样会增加算法的复杂度。

而从右往左扫描，则可以利用栈的特性，遇到运算符时先将其压入栈中，再比较栈顶运算符的优先级和结合性，来决定是否需要先进行计算。这样可以简化算法，提高效率。另外，从右往左扫描还可以处理右结合性的运算符。

 参考后缀表达式代码思路:

我们利用一个栈来进行中缀表达式转前缀表达式的操作。其中prec{}是一个字典，用于记录操作符的优先级，优先级由低到高依次为1~3。opStack是我们初始化的操作符栈，prefixList是用于储存前缀表达式的空列表。

我们首先将中缀表达式解析为一个tokenList列表，并反转该列表，这样我们就可以正向扫描这个列表。

在扫描过程中，对于每个操作数token，我们需要分别处理三种情况：

1. 操作数--将其添加到前缀表达式列表prefixList中。
2. 右括号--将其压入操作符栈opStack中。
3. 左括号--从操作符栈opStack中弹出并返回顶部元素topToken，直到遇到右括号为止。期间，将所有弹出的操作符添加到前缀表达式列表prefixList中。

对于第4种情况---操作符，

我们需要通过while循环语句比较操作符的优先级。

如果当前操作符的优先级小于等于栈顶操作符的优先级，我们就将栈顶操作符弹出并添加到前缀表达式列表prefixList中。然后将当前操作符压入操作符栈opStack中

(1)中缀表达式转前缀 

class Stack :def __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 infix_to_prefix(infix_expr):# 定义一个空字典prec{}--记录操作符优先级  -- 优先级由低到高是1~3prec = {}prec["*"] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec[")"] = 1opStack = Stack()#初始化操作符栈#初始化列表用于储存前缀表达式prefixList = []#将中缀表达式解析为一个 tokenList 列表,并反转该列表tokenList = infix_expr.split()[::-1]#利用split切割成一个一个,然后通过切片转置到列表里#列表的元素为:c +  ) B + A (  遇到右括号入栈,左计算for token in tokenList:#若token是操作数---添加到列表if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":prefixList.append(token)# )---压入操作符栈elif token == ")":opStack.push(token)# (---从操作符栈opStack中弹出并返回顶部元素topTokenelif token == "(":topToken = opStack.pop()#当topToken不是")"while topToken != ")":prefixList.append(topToken)topToken = opStack.pop()# 若token是操作符,通过while循环语句比较他们的优先级,大的操作符添加到式子末端else:while (not opStack.isEmpty()) and \(prec[opStack.peek()] > prec[token]):#opStack.pop()会直接把栈顶元素弹出并返回prefixList.append(opStack.pop())opStack.push(token)#扫描完后将栈中的元素弹出while not opStack.isEmpty():#  操作符prefixList.append(opStack.pop())#  将后缀表达式通过切片转置合成前缀表达式字符串return " ".join(prefixList[::-1])
print(infix_to_prefix("A + B * C "))

(2) 前缀表达式求值

def postfix_eval(prefix_expr):operandStack = Stack()tokenList = prefix_expr.split()for token in reversed(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 - op2print(doMath("*", 11, 11))

定义两个函数：postfix_eval()和doMath()。

postfix_eval()函数接受一个前缀表达式，将其转换为后缀表达式并计算结果。

在计算过程中，它先将操作数入栈，然后遇到运算符就弹出栈顶的两个元素进行计算，并将计算结果重新入栈。最终，栈中仅剩下一个元素，即表达式的计算结果。

doMath()函数用于执行基本的数学运算，包括加、减、乘、除。

程序的最后一行在调用doMath()函数，并输出结果。用于计算11乘以11的结果。