中缀表达式exp1转为后缀表达式exp2
作者/cherryqi　时间/2006-8-2 17:44:00　类别/数据结构 查看/
　发表评论　以论坛方式查看
标签：数据结构
中缀表达式exp1转为后缀表达式exp2的规则如下：
设操作符栈s，初始为空栈后，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。
（1）w为一般操作符（'+'，'-'，'*'，'/'等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。
（2）w为左括号（'（'），w入栈。
（3）w为右括号（'）'），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。
（4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。
这里，再介绍一种简单方法。中缀表达式转为后缀表达式有三步：首先，将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来；接着，顺序将每对括号中的运算符移到相应括号的后面；最后，删除所有括号。
例如，将中缀表达式8-(3+5)*(5-6/2）转为后缀表达式。按如上步骤：
执行完上面第一步后为：(8-((3+5)*(5-(6/2))))；
执行完上面第二步后为：(8((35)+(5(62)/)-)*)- ；
执行完上面第三步后为：8 3 5 + 5 6 2 / - * -  。
可用类似方法将中缀表达式转为前缀表达式。
查看该用户更多文章>>