如何将中缀式转换成后缀式
时间: 2024-05-23 22:11:37 浏览: 8
中缀表达式转换成后缀表达式的一般步骤:
1. 创建一个空栈和一个空的输出字符串。
2. 从左到右扫描中缀表达式。
3. 如果当前符号是操作数,则将其添加到输出字符串中。
4. 如果当前符号是左括号,则将其压入栈中。
5. 如果当前符号是右括号,则将栈顶元素弹出并添加到输出字符串,直到遇到左括号。注意:左括号只弹出,不添加到输出字符串中。
6. 如果当前符号是运算符:
- 弹出栈顶元素直到遇到优先级小于或等于该运算符的元素。将这些元素添加到输出字符串中。
- 将该运算符压入栈中。
7. 重复步骤 2-6,直到表达式的最右边。
8. 将栈中所有元素依次弹出并添加到输出字符串中。
最终输出的字符串即为后缀表达式。
例如,将中缀表达式 "3+4*2/(1-5)^2" 转换成后缀表达式:
1. 输入字符串:3+4*2/(1-5)^2
2. 输出字符串:
3. 栈:空
4. 读入 3,添加到输出字符串:3
5. 读入 +,将其压入栈中:+
6. 读入 4,添加到输出字符串:3 4
7. 读入 *,栈顶是 +,优先级低于 *,将其压入栈中:+ *
8. 读入 2,添加到输出字符串:3 4 2
9. 读入 /,栈顶是 *,优先级等于 /,弹出 * 并添加到输出字符串:3 4 2 * /
10. 读入 (,将其压入栈中:( /
11. 读入 1,添加到输出字符串:3 4 2 * / 1
12. 读入 -,栈顶是 (,优先级低于 -,将其压入栈中:( / -
13. 读入 5,添加到输出字符串:3 4 2 * / 1 5
14. 读入 ),栈顶是 -,弹出 - 并添加到输出字符串;栈顶是 /,弹出 / 并添加到输出字符串;栈顶是 (,弹出 ( 并忽略:3 4 2 * / 1 5 - ^ /
15. 输入字符串扫描完毕,弹出栈中所有元素并添加到输出字符串:3 4 2 * / 1 5 - ^ /
相关推荐
![](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)