将中缀表达式转换为后缀表达式
2017-06-28 本文已影响335人
tingshuo123
中缀表达式(infix)：
数学里面的公式就是中缀表达式，是我们生活中里面常用的表达式，比如说 a*(b+c)， 中缀表达式可以用括号来调整优先级。
后缀表达式(postfix)：
运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不用考虑运算符的优先级），如 a*(b+c)，转化为后缀表达式 即a b + 3 *。
转换规则：
从头到尾读取中缀表达式中的每个对象， 对不同对象按不同情况处理。
- 运算数： 直接输出；
- 左括号： 压入堆栈；
- 右括号： 将栈顶的运算符弹出并输出， 直到遇到左括号，
(出栈不输出； - 运算符：
- 若优先级大于栈顶运算符时， 则把它压入栈；
- 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出； 再比较新的栈顶运算符， 直到该运算符大于栈顶运算符优先级为止，然后将该运算符压入栈；
- 若将个对象处理完毕， 则把堆栈中存留的运算符一并输出；
例如将中缀表达式2 * (9 + 6 / 3 - 5) + 4 转化为后缀表达式2 9 6 3 / + 5 - * 4 + 转换步骤如下:
- 遇到数字
2， 直接输出
表达式：2
符号栈：
- 遇到符号
*，栈顶没有符号，直接入栈
表达式： 2
符号栈： *
- 遇到符号
(， 压入栈
表达式：2
符号栈：* （
- 遇到数字
9， 直接输出
表达式：2 9
符号栈：* （
- 遇到符号
+，( )里面的+， 比外面的*优先级高， 压入栈
表达式：2 9
符号栈：* ( +
- 遇到数字
6, 直接输出
表达式：2 9 6
符号栈：* （ +
- 遇到符号 \ ，优先级大于
+，压入栈
表达式：2 9 6
符号栈：* ( + \
- 遇到数字
3， 直接输出
表达式：2 9 6 3
符号栈：* ( + \
- 遇到符号
-， 优先级小于 \ ， \ 弹出栈
表达式：2 9 6 3
符号栈：* （ +
- 继续比较，
+优先级等于-，+弹出栈
表达式：2 9 6 3 \ +
符号栈：* (
- 继续比较，
-优先级大于(， 压入栈
表达式：2 9 6 3 \ +
符号栈：* ( -
- 遇到数字
5, 直接输出
表达式：2 9 6 3 \ + 5
符号栈：* ( -
- 遇到符号
)，将(和(之前的的符号弹出栈
表达式：2 9 6 3 \ + 5 -
符号栈：*
- 遇到符号
+， 小于*,*弹出栈
表达式：2 9 6 3 \ + 5 - *
符号栈：
- 再比较，栈顶没有符号，直接压入栈
表达式：2 9 6 3 \ + 5 - *
符号栈：+
- 遇到数字
4直接输出
表达式：2 9 6 3 \ + 5 - * 4
符号栈：+
- 处理完毕， 一并输出
表达式：2 9 6 3 \ + 5 - * 4 +
符号栈：
