中缀表达式转后缀表达式 数据结构
时间: 2023-10-23 07:11:39 浏览: 57
中缀表达式转后缀表达式的算法可以使用栈来实现。具体步骤如下:
1. 初始化两个栈:运算符栈s1和储存中间结果的栈s2;
2. 从左至右扫描中缀表达式;
3. 遇到操作数时,将其压入s2;
4. 遇到运算符时,比较其与s1栈顶运算符的优先级:
1. 如果s1为空,或栈顶运算符为左括号"(",则直接将此运算符入栈;
2. 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入s1;
3. 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到4.1与s1中新的栈顶运算符相比较;
5. 遇到括号时:
1. 如果是左括号"(",则直接压入s1;
2. 如果是右括号")",则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃;
6. 重复步骤2至5,直到表达式的最右边;
7. 将s1中剩余的运算符依次弹出并压入s2;
8. 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式。
例如,将中缀表达式"3+5*4-2"转换为后缀表达式的过程如下:
| 步骤 | s1 | s2 |
| --- | --- | --- |
| 1 | | |
| 2 | | 3 |
| 3 | | 3 5|
| 4.2| * | 3 5|
| 5.1| * (| 3 5|
| 2 | * (| 3 5 4|
| 3 | * (| 3 5 4|
| 4.1| + *|(3 5 4)|
| 2 |- |+ * (3 5 4)|
| 3 |- |+ * (3 5 4) 2|
| 7 | |+ * (3 5 4) 2 -|
因此,中缀表达式"3+5*4-2"对应的后缀表达式为"354*+2-"
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)