对上面代码进行优化,任意输入一个算数表达式转化为逆波兰式
时间: 2023-06-11 09:10:17 浏览: 94
好的,这里给出一个实现算法,使用栈来进行中缀表达式到后缀表达式(逆波兰式)的转换:
```python
# 定义操作符的优先级
priority = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'(': 0
}
# 将中缀表达式转换为后缀表达式(逆波兰式)
def infix_to_postfix(expression):
# 初始化栈和结果列表
stack = []
result = []
# 遍历表达式中的每个字符
for char in expression:
# 如果是数字,直接加入结果列表
if char.isdigit():
result.append(char)
# 如果是左括号,入栈
elif char == '(':
stack.append(char)
# 如果是右括号,将栈中的操作符弹出,加入结果列表,直到遇到左括号
elif char == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop() # 弹出左括号
# 如果是操作符,将栈中优先级较高的操作符弹出,加入结果列表,直到栈顶操作符优先级小于等于该操作符
else:
while stack and priority[stack[-1]] >= priority[char]:
result.append(stack.pop())
stack.append(char) # 将该操作符入栈
# 将栈中剩余的操作符弹出,加入结果列表
while stack:
result.append(stack.pop())
# 返回后缀表达式
return ' '.join(result)
# 测试代码
expression = input('请输入算数表达式:')
postfix_expression = infix_to_postfix(expression)
print('逆波兰式:', postfix_expression)
```
这个算法的时间复杂度为 $O(n)$,其中 $n$ 是表达式中的字符数。
阅读全文