遍写一个程序,读入一道正确的算术式, 把它转译成反向波兰形式(Reversed Polish), 为了方便起见, 假设整道算术式在同一列上, 并且变量只有一个英文字母,不含常数(换言之,所有运算都是一个字母的变量). 目前,只需要处理+, -, *, /, (, )即可, 没有正负号.

说明: 反向波兰形式是用来表示一道表达式的常见写法, 是由波兰学派的逻辑学家发展出来表示逻辑式子用的。它有一个很重要的特性,就是不会用到括号, 在寻常的算术式子中, 运算是写在两个操作数之间, 但反向波兰形式则是把运写在对应的操作数后方。例如a+b写成ab+, a+bc 写成abc+, ab+c写成abc+。对a+b而言, +的操作数是a与b, 所以写成ab+是很明显的; 再看a+bc, 最先算的是bc, 因而写成bc, +的两个操数是a与bc,因此就写成abc+; 同理,ab+c写成abc+就不必解说了

如果算术式子中有括号, 括号中的部分对某个运算而言就是一个完整的操作数。在(a+b)(c+d)中, a+b的写法是ab+, c+d的写法是cd+, 但ab+与cd+又是的操作数, 因此得到ab+cd+, 再看一例, a(b+c)-(e+f)/g, a与bc+是的操作数, 所以这一部分可以写成abc, 同理(c+f)/g可以写成ef+g/, 因此整个式子就是abc+*ef+g/-

从上面的说明可以看到, 一旦写成反向波兰形式, 括号就没有了, 这是它方便的地方. 但是如何把算术式转变成反波兰式呢? 如果仔细研究上述的结果可以有下面的结论:

1. 反向波兰形式中变量的顺序与原来算术式中的顺序相同
2. 运算永远出现在它的两个操作数后方

因为上述的第一点理由, 当读到一个操作数的时候, 就可以把它输出, 因为操作数在输入与输出中顺序相同。运算又如何呢? 运算是比较麻烦的, 先不管左、右括号, 因为在自左向右地读取输入时, 看到了一个+号, 此时不但还没有见到它的右边操作数, 更看不到下一个运算, 于是无法决定这个+号是不是可以计算。例如a+bc, 如果现在才读入+,就没有办法知道这个加法能不能计算, 一直到出现才能作决定(也就是不能算); 同样, 看到了也不表示它能够算, 为什么呢? 如果输入是a+b(x+y), 把x+y算出来之后才能算法。换句话说, 在下一个运算出现之前, 并不知道目前这个运算可不可以算; 回想一下先乘除后加减的规则, 如果下一个运算(例如+)的优先级比现在的(例如)低, 那么就可以算现在的这个。正因为如此, 用堆栈是个好方法, 把不能算的运算先推到堆栈中, 于是现在的这一个就在顶上, 当下一个运算出现了, 就看看顶上那一个与下一个的关系, 如果顶上(现在)的这一个可以算, 就把它输出。如果碰到左、右括号又怎么办呢?

以上就是个简单的提示。其实, 可以在其他的书中找到解答,但建议不要这样做,因为在计算机刚问世时这是个难题, 如果能够独立解决它而不求助外力的话, 是很值得自豪的, 但如果学过了这方面的知识, 就不妨跳过去, 做一做后面的习题。注意,以上的方法与提示并不是最好的,可以参看有关编译程序的专业书籍来寻求更好、更普遍性的解法

解答见polish.py