Python实现逆波兰表达式
时间: 2024-08-15 18:09:17 浏览: 40
逆波兰表达式(Reverse Polish Notation, RPN)是一种数学运算符的表示方式,它的特点是操作数在前,运算符在后,不需要括号就能明确表达计算顺序。在Python中,我们可以使用栈来解析和计算逆波兰表达式。下面是一个简单的例子:
```python
def evaluate_rpn(expression):
# 定义两个空栈
operators = []
numbers = []
# 将输入的字符串分割成元素列表,并遍历
for token in expression.split():
if token.isdigit(): # 如果是数字,直接压入numbers栈
numbers.append(int(token))
else: # 如果是运算符,从numbers栈弹出操作数,直到遇到能匹配的运算符
while (operators and operators[-1] != '(' and
priority(operators[-1], token) <= priority(numbers[-1], operators[-1])):
numbers.append(operators.pop())
operators.append(token) # 将运算符压入
# 处理剩余的数字,因为最后的运算符可能是开括号
while operators:
numbers.append(operators.pop())
# 逐个从numbers栈中取出数字,计算结果,并压回栈
result = numbers.pop()
while numbers:
operator = numbers.pop()
result = apply_operator(result, operator, numbers.pop())
return result
def priority(operator1, operator2):
# 可以根据需要自定义运算符的优先级,这里假设'*'和'/'优先于'+'
if operator1 == '*' or operator1 == '/':
return 2
elif operator1 == '+' or operator1 == '-':
return 1
else:
return 0
def apply_operator(num1, operator, num2):
if operator == '+':
return num1 + num2
elif operator == '-':
return num1 - num2
elif operator == '*':
return num1 * num2
elif operator == '/':
return num1 / num2
# 示例
expression = "2 3 + 4 *"
print(evaluate_rpn(expression)) # 输出: 20
```
这个程序首先定义了两个栈(numbers和operators),然后遍历输入的RPN表达式,根据每个元素(数字或运算符)的特点分别处理。注意,这里的优先级函数可以根据实际需求调整。
阅读全文