四则表达式求值—中缀表达式先转变成后缀表达式再求值python实现

文章目录

1.中缀表达式转变成后缀表达式

参考python【栈】中缀表达式转后缀表达式

思路：

代码实现：

# 中缀表达式转为后缀表达式def infixToPostfix(infixexpr):prec = {} # 定义一个字典，保存优先级prec["*"] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec["("] = 1opStack = Stack() # 栈是用来存括号和运算符的postfixList = [] # 保存要输出的后缀表达式tokenList = infixexpr.split() # 把中缀表达式转换成列表for token in tokenList:if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":postfixList.append(token)elif token == '(': # 如果是左括号，就压入栈opStack.push(token)elif token == ')': # 遇到右括号，循环判断栈顶元素是否为（，如果不是（，就都加到后缀列表中topToken = opStack.pop()while topToken != '(':postfixList.append(topToken)topToken = opStack.pop()print(opStack.isEmpty()) # True False Falseelse: # 如果是运算符，当栈不为空并且栈顶元素的等级比token的等级高时，栈顶元素加入到后缀列表中while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):postfixList.append(opStack.pop())opStack.push(token) # 把token压入栈while not opStack.isEmpty(): # 当opStack中不为空时，依次弹出栈中的元素，加到后缀列表后面postfixList.append(opStack.pop())return ''.join(postfixList)print(infixToPostfix("A * B + C * D"))print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

2.后缀表达式计算

思路：

后缀表达式中，如果碰到数字就进栈。如果碰到符号[’+’,’-’,’*’,’/’]，就弹出两个数字，做符号运算，再进栈

#四则运算表达式class Solution:def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []for s in tokens:if s in ['+','-','*','/']:b = stack.pop()a = stack.pop()if s == '+':stack.append(a+b)elif s == '-':stack.append(a-b)elif s == '*':stack.append(a*b)else:stack.append(int(a/b))else:stack.append(int(s))ans = int(stack.pop())return ans

如果对您有帮助，麻烦点赞关注，这真的对我很重要！！！如果需要互关，请评论或者私信！