中缀转为后缀 栈实现
时间: 2023-09-10 14:13:32 浏览: 54
中缀表达式转后缀表达式的算法又称为“逆波兰式”,其基本思想是:
1. 从左到右扫描中缀表达式。
2. 如果是操作数,直接输出。
3. 如果是运算符,则判断其与栈顶运算符的优先级:
1. 如果栈为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈。
2. 否则,若优先级比栈顶运算符的低或相等,则将栈顶运算符弹出并输出,再次转到(3)与新的栈顶运算符比较。
3. 否则,将此运算符入栈。
4. 如果是括号,则:
1. 如果是左括号“(”,则直接入栈
2. 如果是右括号“)”,则依次弹出栈顶运算符,并输出,直到遇到左括号为止,左括号不输出。
5. 重复步骤2至4,直到表达式的最右边。
6. 将栈中剩余的运算符依次弹出并输出。
以下是一个基于栈实现的中缀转后缀的示例代码:
```python
def infix_to_postfix(infix_expr):
prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
op_stack = []
postfix_list = []
token_list = infix_expr.split()
for token in token_list:
if token.isdigit() or token.isalpha():
postfix_list.append(token)
elif token == '(':
op_stack.append(token)
elif token == ')':
top_token = op_stack.pop()
while top_token != '(':
postfix_list.append(top_token)
top_token = op_stack.pop()
else:
while (len(op_stack) > 0) and (prec[op_stack[-1]] >= prec[token]):
postfix_list.append(op_stack.pop())
op_stack.append(token)
while len(op_stack) > 0:
postfix_list.append(op_stack.pop())
return ' '.join(postfix_list)
```
示例输入:
```python
infix_expr = "A + B * C + D / E"
print(infix_to_postfix(infix_expr))
```
示例输出:
```
A B C * + D E / +
```
上述代码中,prec字典用于保存运算符的优先级,op_stack用于保存运算符,postfix_list用于保存后缀表达式。在处理中缀表达式的过程中,遇到操作数则直接加入后缀表达式中,遇到左括号则入栈,遇到右括号则弹出栈顶的运算符并加入后缀表达式中,遇到运算符则比较其与栈顶运算符的优先级,如果栈顶的优先级高,则弹出栈顶运算符并加入后缀表达式中,直到栈顶运算符的优先级低于当前运算符,最后将当前运算符入栈。最后,将栈中剩余的运算符全部弹出并加入后缀表达式中。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)