兼济天下则达 独善其身则穷
最近在看《C语言名题精选百则--技巧篇 冼镜光》问题6.2是有关逆波兰式的,一下介绍一下逆波兰式。所谓逆波兰式是用来表示一道表达式的常见写法，是由波兰学派的逻辑学家发展出来表示逻辑式子用的。它有一个很重要的特性，就是不会用到括号。在普通的算术式中，运算符在操作数之间，而在逆波兰式中，运算符在操作数后面。例如普通式子a+b,如果写成逆波兰式则是ab+;普通式子a+bc,写成逆波兰式则是abc+;式子ab+c,写成abc+.现在解释这是为什么。对于a+b,+的操作数是a和b,把运算符写在操作数后面，很明显写成ab+;对于a+bc,要先算bc,得到bc,这时+的操作数是a和bc,所以是abc+;同理可得到ab+c的逆波兰式。
如果算术式子中有括号，括号中的部分对运算而言就是一个完整的操作数。例如在(a+b)(c+d)中，a+b写成ab+,c+d写成cd+,最终整个式子写成ab+cd+.对于式子a(b+c)-(e+f)/g,a与bc+是的操作数，这一部分写成abc+;ef+与g是/的操作数,这一部分写成ef+g/,最终式子写成abc+ef+g/-.
可以看出，一旦写成逆波兰式，括号就没有了。这是它方便的地方，那么如何将算术式转变成逆波兰式呢？冼同学给出了提示。对于a+bc，读入+就无法知道这个加法能不能计算，一直到出现才能做出决定。同样，对于a+b(x+y)，读入也无法知道这个乘法能不能计算，要等到x+y算出之后才能算*。其实就是在下个运算出现之前，并不知大目前这个运算可不可以算。如此，用栈是个好方法，把不能算的运算先压在栈中，于是现在的这一个就在栈顶，当下一个运算出现了，就看看顶上这个与下一个运算的关系，如果栈顶上的这个可以算，也就是栈顶上的运算的优先级大于等于下一个运算的优先级，就把它输出，如果不行，将下一个运算入栈。这里很关键要处理左右括号。
冼同学还说，其实，可以在其他书上找到答案，但建议不要这样做，因为在计算机刚问世是这是个难题，如果能够独立解决它而不求助外力的话，是很值得自豪的。正因为后面这句话，我没有立刻去找答案。折腾了一个上午，总算有点眉目，但我竟会想到用递归。还算我有点常识，递归程序一般都可以用栈实现的，既然在程序中已经用了栈了，就不应该再用递归了。困惑之际，上网查了一下逆波兰式，可恶，我看了算法，最终还是借助了外力。
与《C名题精选百则--技巧篇》相识，是在大一时，也就是四年前了。那时只会写求素数等基本程序，看了序言就知道这是本好书，做了序曲中最长平台这一题，被这本书折服了，之后就没有再看这本书。时隔四年，再次拿起这本书，总算可以坦然面对。看来算法水平有所提高了。这本书是台湾人写的，于1989年出版，中国大陆于2005年出版。差距。想到《计算机程序的构造和解释》作为MIT计算机科学的入门教材，而我国计算机科学的入门教材是什么呢？我也不知道，反正我是《C语言程序设计》。差距啊。