中缀转为后缀 栈实现
时间: 2023-09-10 18:13:32 浏览: 35
中缀表达式转后缀表达式可以使用栈来实现,具体步骤如下:
1. 从左至右遍历中缀表达式的每个元素;
2. 如果当前元素是数字或字母,则直接输出到后缀表达式中;
3. 如果当前元素是左括号“(”,则将其入栈;
4. 如果当前元素是右括号“)”,则将栈顶的元素依次出栈并输出,直到遇到左括号“(”,将左括号出栈(左右括号不输出到后缀表达式中);
5. 如果当前元素是运算符(加减乘除等),则判断其与栈顶运算符的优先级,如果当前运算符的优先级大于栈顶运算符的优先级,则将其入栈;否则将栈顶运算符出栈并输出,再次比较新的栈顶运算符和当前运算符的优先级,直到当前运算符的优先级大于栈顶运算符的优先级,然后将当前运算符入栈;
6. 如果中缀表达式遍历完毕,但栈中还有元素,则依次出栈并输出。
下面是一个简单的 Python 代码实现:
```python
def infix_to_postfix(infix):
stack = []
postfix = ""
for c in infix:
if c.isalpha() or c.isdigit():
postfix += c
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop()
else:
while stack and precedence(c) <= precedence(stack[-1]):
postfix += stack.pop()
stack.append(c)
while stack:
postfix += stack.pop()
return postfix
def precedence(operator):
if operator in "+-":
return 1
elif operator in "*/":
return 2
else:
return 0
```
其中,`infix` 是输入的中缀表达式,`stack` 是用来存储运算符的栈,`postfix` 是最终输出的后缀表达式。函数 `precedence` 用来判断运算符的优先级,优先级越高返回的值越大。