后缀表达式,又称逆波兰式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行。请编程实现后缀表达式求值,运算符仅有+、-、*、/ 四种,运算符和操作数之间用空格分隔,例如:12 8 5 - /,后缀表达式总长度不超过300000。
时间: 2024-04-09 18:33:51 浏览: 80
您好,我可以帮助您实现后缀表达式的求值。下面是一个使用堆栈的简单算法来实现后缀表达式求值的示例代码:
```python
def evaluate_postfix(expression):
stack = []
operators = {'+': lambda x, y: x + y, '-': lambda x, y: x - y, '*': lambda x, y: x * y, '/': lambda x, y: x / y}
for token in expression.split():
if token.isdigit():
stack.append(int(token))
elif token in operators:
if len(stack) < 2:
raise ValueError("Invalid expression")
operand2 = stack.pop()
operand1 = stack.pop()
result = operators[token](operand1, operand2)
stack.append(result)
else:
raise ValueError("Invalid token: " + token)
if len(stack) != 1:
raise ValueError("Invalid expression")
return stack.pop()
# 测试
expression = "12 8 5 - /"
result = evaluate_postfix(expression)
print(result)
```
这个代码使用一个堆栈来保存操作数,并依次处理后缀表达式中的每个标记。如果遇到数字,则将其入栈;如果遇到运算符,则从堆栈中弹出两个操作数进行计算,并将结果入栈。最后,堆栈中剩下的唯一元素就是表达式的结果。
请注意,这段代码假设输入的后缀表达式是合法的。如果表达式无效,例如缺少操作数或出现无效的标记,它会引发 ValueError 异常。您可以根据需要进行错误处理。
阅读全文