python 中缀表达式求值
时间: 2023-11-08 15:03:49 浏览: 38
在 Python 中,可以通过使用栈来实现中缀表达式求值。具体步骤如下:
1. 定义一个操作符优先级字典,用于判断两个操作符的优先级,方便后续比较。
2. 定义一个数字栈和操作符栈。
3. 从左到右遍历中缀表达式中的每一个元素。
4. 如果当前元素是数字,则将该数字入栈。
5. 如果当前元素是左括号,则将左括号入操作符栈。
6. 如果当前元素是右括号,则执行以下操作:
a. 将操作符栈中的元素弹出,直到遇到左括号为止。弹出的操作符依次与数字栈中的两个数字进行计算,并将计算结果入栈。
b. 将左括号弹出。
7. 如果当前元素是操作符,则执行以下操作:
a. 如果当前操作符的优先级小于或等于栈顶操作符的优先级,则将栈顶操作符弹出,并将其与数字栈中的两个数字进行计算,并将计算结果入栈。
b. 否则将当前操作符入操作符栈。
8. 最终,数字栈中剩余的唯一元素即为表达式的计算结果。
以下是 Python 的代码实现:
```
def infix_eval(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '**': 3}
num_stack = []
op_stack = []
tokens = expression.split()
for token in tokens:
if token.isdigit():
num_stack.append(int(token))
elif token == '(':
op_stack.append(token)
elif token == ')':
while op_stack[-1] != '(':
op = op_stack.pop()
num2 = num_stack.pop()
num1 = num_stack.pop()
result = apply_op(op, num1, num2)
num_stack.append(result)
op_stack.pop()
elif token in precedence:
while op_stack and op_stack[-1] != '(' and precedence[token] <= precedence[op_stack[-1]]:
op = op_stack.pop()
num2 = num_stack.pop()
num1 = num_stack.pop()
result = apply_op(op, num1, num2)
num_stack.append(result)
op_stack.append(token)
while op_stack:
op = op_stack.pop()
num2 = num_stack.pop()
num1 = num_stack.pop()
result = apply_op(op, num1, num2)
num_stack.append(result)
return num_stack[0]
def apply_op(op, num1, num2):
if op == '+':
return num1 + num2
elif op == '-':
return num1 - num2
elif op == '*':
return num1 * num2
elif op == '/':
return num1 / num2
elif op == '**':
return num1 ** num2
```