用C语言写解释器(三)——中缀转后缀 redraiment, 2009-11-01 操作符排序 如果你忘记了后缀表达式的概念,赶紧翻回上一篇《 用C语言写解释器(二) 》回顾一下。简单地说,将中缀表达式转换成后缀表达式,就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。因此,所谓的中缀转后缀,其实就是给原表达式中的操作符排序。 比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。其中数字 5 10 1 3 仍然按照原先的顺序排列,而操作符的顺序变为 - / ×,这意味着减号最先计算、其次是除号、最后才是乘号。也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。其实不用担心,在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。 从中缀表达式 1+2×3+4 中逐个获取操作符,依次是 + × +。如果当前操作符的优先级 不大于 前面的操作符时,前面操作符就要先输出。比如例子中的第二个加号,它前面是乘号,因此乘号从这个队伍中跑到输出的队伍中当了“老大”;此时第二个加号再前面的加号比较,仍然没有比它大,因此第一个加号也排到新队伍中去了;最后队伍中只剩下加号自己了,所以它也走了。得到新队伍里的顺序 × + + 就是所求解。下面的表格中详细展示每一个步骤。 序号 输入 临时空间 输出 1 + 2 × + 3 + + × 4 + × + 5 + + × 6 + × + 7 * + + 相信你心里还是牵挂着那些操作数。很简单,如果碰到的是操作符就按上面的规则处理,如果是操作数就直接输出!下面的表格加上了操作数,将输出完整的后缀表达式。 序号 输入 临时空间 输出 1 1 2 + 1 3 2 + 1 4 × + 1 2 5 3 + × 1 2 6 + + × 1 2 3 7 + × + 1 2 3 8 + + 1 2 3 × 9 4 + 1 2 3 × + 10 + 1 2 3 × + 4 11 1 2 3 × + 4 + 得到最终结果 1 2 3 × + 4 + 就是所求的后缀表达式。下面是程序中的参考代码(有删减)。 操作符优先级 上一节介绍了中缀转后缀的方法。其中关键...