中缀表达式转换为后缀表达式
目录
中缀表达式转换后缀表达式
3.1 规则
-
1、初始化栈和集合：运算符号栈s1和存储空间集合s2
-
2、从左到右扫描中缀表达式
-
3、遇到操作数时，将其加入s2
-
4、遇到运算符时，比较其与s1栈顶运算符的优先级
-
4.1、如果s1为空，或栈顶运算符为左括号‘(’，则直接将此运算符入栈
-
4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1
-
4.3、否则，将s1栈顶的运算符弹出并加入到s2中，再次转到 流程4
-
5、遇到括号时：
-
5.1、如果是左括号‘(’，则直接压入s1
-
5.2、如果是右括号‘)’，则依次弹出s1栈顶的运算符，并且加入s2，直到遇到左括号为止，此时将这一对括号丢弃
-
6、重复步骤 2-5，直到表达式的最右边
-
7、将s1中剩余的运算符依次弹出并加入s2
-
8、s2结果即为中缀表达式对应的后缀表达式
3.2 实例
以上面的转换为实例，比如输入 1 + ( ( 2 + 3 ) * 4 ) - 5，那么怎么转换成后缀表达式呢？
| 扫描到的元素 | s2集合中元素 | s1(栈底->栈顶) | 说明 |
|---|---|---|---|
| 1 | 1 | 空 | 数字 直接加入到集合中 |
| + | 1 | + | s1为空，直接入栈 |
| ( | 1 | +( | 左括号 直接入栈 |
| ( | 1 | +( ( | 同上 |
| 2 | 12 | +( ( | 数字 |
| + | 12 | +( (+ | s1栈顶是左括号，运算符直接入栈 |
| 3 | 123 | +( (+ | 数字 |
| ) | 123+ | +( | 右括号，弹出运算符直至遇到左括号 |
| * | 123+ | +( * | s1栈顶是左括号，运算符直接入栈 |
| 4 | 123+4 | +( * | 数字 |
| ) | 123+4 * | + | 右括号，弹出运算符直至遇到左括号 |
| - | 123+4 *+ | - | -与+优先级相同，因此弹出+号，在压入- |
| 5 | 123+4 *+ 5 | - | 数字 |
| 到达最右端 | 123+4 *+ 5 - | 空 | s1中剩余的运算符 |
至此整个过程转换完毕
即中缀表达式1 + ( ( 2 + 3 ) * 4 ) - 5 的后缀表达式为1 2 3 + 4 * + 5 -
非原创原文链接：https://blog.csdn.net/qq_36144258/article/details/95075064