使用python语言实现中缀表达式求值
时间: 2023-09-09 11:06:25 浏览: 80
可以通过以下步骤使用 Python 实现中缀表达式求值:
1. 定义一个函数 `infix_eval(expr)`,其中 `expr` 是中缀表达式的字符串形式。
2. 创建两个空栈,一个用于存储操作数,一个用于存储操作符。
3. 定义一个函数 `priority(op)`,用于返回操作符的优先级。例如,`priority('+')` 返回 1,`priority('*')` 返回 2。
4. 遍历中缀表达式的每个字符,如果是数字则将其作为操作数入栈,如果是操作符则将其与操作符栈顶元素比较优先级,如果优先级较高则入栈,否则将操作符栈中的操作符弹出并计算,直到当前操作符可以入栈。
5. 当遍历完中缀表达式后,将操作符栈中的所有操作符依次弹出并计算。
下面是 Python 代码实现:
```python
def infix_eval(expr):
operands = []
operators = []
i = 0
while i < len(expr):
if expr[i].isdigit():
num = ""
while i < len(expr) and expr[i].isdigit():
num += expr[i]
i += 1
operands.append(int(num))
elif expr[i] in "+-*/":
while operators and priority(operators[-1]) >= priority(expr[i]):
op = operators.pop()
b = operands.pop()
a = operands.pop()
operands.append(eval_expr(a, b, op))
operators.append(expr[i])
i += 1
else:
i += 1
while operators:
op = operators.pop()
b = operands.pop()
a = operands.pop()
operands.append(eval_expr(a, b, op))
return operands[0]
def priority(op):
if op in "+-":
return 1
elif op in "*/":
return 2
else:
return 0
def eval_expr(a, b, op):
if op == "+":
return a + b
elif op == "-":
return a - b
elif op == "*":
return a * b
elif op == "/":
return a / b
# 测试
print(infix_eval('1+2*3')) # 输出 7
print(infix_eval('(1+2)*3')) # 输出 9
```
注意,上述代码只适用于整数运算,如果要支持小数运算,可以将 `int(num)` 改为 `float(num)`。