前缀表达式

Sun, Dec 7, 2014

前缀表达式又称为波兰表达式，将运算符提前，就成了前缀表达式。前缀表达式是不需要括号的。

一个例子：(2 + 3) * 4 就是 * + 2 3 4

程序的任务就是，写一个前缀表达式的解析器。

看到题目我想到的先是设置数值栈和运算符栈，然后依次弹栈计算，结果压回数值栈。后来又想到一个更加简洁的方法：不要一口气读入整个式子，而是在递归函数中一次次读。递归函数 calc() 先读入一节表达式，如果是加号运算符，就返回 calc() + calc()，其他运算符类推。如果是数值，那直接返回就行。这样一来就避免了复杂的数据结构。

由此联想到前段时间看的《布尔表达式》问题。题目就是要求写一个布尔表达式的解析器。由于这道题目帮老师录制了讲解视频，之前看了三种解法，有一种就是设置数值栈和运算符栈，然后逐个弹栈计算。

需要考虑的问题是：为什么在波兰表达式中，可以轻松避免堆栈的运用呢？我认为，这是由于波兰表达式实在是很简洁，主要是运算顺序就是运算符出现的顺序，可以直接开始递归，而且不存在括号之类，所以计算它的步骤相当简单。相对的，布尔表达式有括号，而且存在运算优先级问题（先出现的运算符不一定能够先去计算），所以用堆栈进行存放是很好的方法。