之前我们介绍过了什么是后缀表达式,以及它如何通过中缀表达式进行转换,以及关于后缀表达式的求值问题,如有遗忘👉🔗http://t.csdnimg.cn/Hl4Y9
今天我们拓展一下,前缀表达式的转换和求值问题
💫中缀转后缀表达式的思路: 从左到右扫描逐个字符扫描中缀表达式的过程中,采用一个栈来暂存未处理的操作符 这样,栈顶的操作符就是最近暂存进去的,当遇到一个新的操作符,就需要跟栈顶的操作符比较下优先级,再行处理--->新符号和栈顶对比,新的高,就入栈(因为取时也先取); 新的低,就把栈顶出栈,让栈顶的先运算 想要了解具题后缀的相关知识点点击👉🔗http://t.csdnimg.cn/9100K
中缀转前缀思路也类似,不过 中缀表达式中运算符的优先级和结合性需要考虑,从左往右扫描的话,需要对每个运算符的优先级和结合性进行判断,才能决定是否需要先进行计算。这样会增加算法的复杂度。 而从右往左扫描,则可以利用栈的特性,遇到运算符时先将其压入栈中,再比较栈顶运算符的优先级和结合性,来决定是否需要先进行计算。这样可以简化算法,提高效率。另外,从右往左扫描还可以处理右结合性的运算符。
参考后缀表达式代码思路: 我们利用一个栈来进行中缀表达式转前缀表达式的操作。其中prec{}是一个字典,用于记录操作符的优先级,优先级由低到高依次为1~3。opStack是我们初始化的操作符栈,prefixList是用于储存前缀表达式的空列表。 我们首先将中缀表达式解析为一个tokenList列表,并反转该列表,这样我们就可以正向扫描这个列表。 在扫描过程中,对于每个操作数token,我们需要分别处理三种情况:
对于第4种情况---操作符, 我们需要通过while循环语句比较操作符的优先级。 如果当前操作符的优先级小于等于栈顶操作符的优先级,我们就将栈顶操作符弹出并添加到前缀表达式列表prefixList中。然后将当前操作符压入操作符栈opStack中
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~3
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec[")"] = 1
opStack = 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中弹出并返回顶部元素topToken
elif 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 "))
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 * op2
elif op == "/":
return op1 / op2
elif op == "+":
return op1 + op2
else:
return op1 - op2
print(doMath("*", 11, 11))
定义两个函数:
postfix_eval()
和doMath()
。postfix_eval()
函数接受一个前缀表达式,将其转换为后缀表达式并计算结果。 在计算过程中,它先将操作数入栈,然后遇到运算符就弹出栈顶的两个元素进行计算,并将计算结果重新入栈。最终,栈中仅剩下一个元素,即表达式的计算结果。doMath()
函数用于执行基本的数学运算,包括加、减、乘、除。 程序的最后一行在调用doMath()
函数,并输出结果。用于计算11乘以11的结果。