逆波兰表达式.doc

逆波兰表达式表达式一般由操作数(Operand)、运算符(Operator)组成，例如算术表达式中，通常把运算符放在两个操作数的中间，这称为中缀表达式(Infix Expression)，如A+B。波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+；其中，逆波兰表达式在编译技术中有着普遍的应用。算法：一、 将中缀表达式转换成后缀表达式算法：1、从左至右扫描一中缀表达式。2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈3、若读取的是运算符(1) 该运算符为左括号(，则直接存入运算符堆栈。(2) 该运算符为右括号)，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。(3) 该运算符为非括号运算符： (a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。 (b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。 (c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。二、逆波兰表达式求值算法：1、循环扫描语法单元的项目。2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。5、将运算结果重新压入堆栈。6、重复步骤2-5，堆栈中即为结果值。 C语言讲解【复合复制运算符】时会提到，复合运算简练并且产生机器码的效率高。为什么效率高呢，这就必须要了解：【编译原理】中提到的【逆波兰式】。逆波兰表达式又叫做【后缀表达式】。推而广之必然还存在【前缀表达式】、【中缀表达式。】（有时也成为，前序式，中序式，后序式）。中缀表达式就是我们常用的所谓的标准的表达式如A+B，它在数学上学名叫中缀表达式（Infix Notation），原因是：运算符号在两个运算对象的中间。其优势:在于只：用两种简单操作，入栈和出栈就可以搞定任何普通表达式（仅包含：+-*/和（）的表达式）的运算。其基本运算方式：如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。为什么说逆波兰式产生机器码的效率高：因为逆波兰式非常易于计算机的处理。原因是这样的。举例： 3 32 + 5 3 * -12 34 2 - * 8 /乍一看上面两个式子很奇怪，是吗？它们就是一种表达式的记法逆波兰表达式。现在，准备一个很窄的圆筒，筒是有底的，像一个细长的杯子，粗细刚好和一枚硬币相当。再做几个和硬币一样大的小圆纸片，在纸片上依次写上“3”“32”“+”“5”“3”“*”“-”，记住，每个纸片上要么只写一个数，要么只写一个运算符号，把它们按上面的顺序排好。好，现在仔细听我说，按顺序一个接一个地拿起小圆纸片，反复执行以下几个规则：1. 如果你拿着的是一个数，不多说，直接把它放进圆筒；2. 如果你拿着的是一个运算符号，不要把它放进去。先从圆筒里取出两个数（当然是先取最上而的啦，筒很细的），然后处这两个数作运算符号指定的运算，并把结果写在一张新的纸片上，然后放进筒里。比如你拿着的是“+”，你要依次取出“32”和“3”，让它们相加，得“35”，把“35”写在一张新纸片上（现在“34”和“12”可以扔掉了），并把这张新纸片放进圆筒。当圆筒里只有一个数时，你就可以停下来了，我猜这个数是20，没错，这就是这个表达式的值！我们刚才操作的，其实就是一个“栈”，栈是一种数据结构，具有一个性质后进先出（LIFOLast Input First Output），你已经深有体会了，就像一摞盘子，你只能从最上面的开始取，放的时候也只能放在最上面。放进去的动作叫做“入栈”，取出来叫做“弹出”。以后你就可以把栈想像成一摞盘子，或是上面说的小圆筒和小纸片，栈就是这么简单！逆波兰表达式虽然看起来比较繁琐，其实在计算机中很有用。计算机可不知道先乘除后加减，先括号内后括号外，它要把你输入的式子变成逆波兰表达式，它就可以不断地执行上面两个固定的规则，直至把结果算出来告诉你。，编译器在处理时候按照从左至右的顺序读取逆波兰表达式，遇到运算对象直接压入堆栈，遇到运算符就从堆栈提取后进的两个对象进行计算，这个过程正好符合了计算机计算的原理。所以，逆波兰式非常适宜计算机的处理。 那么，接下来的问题就是：将一个中缀表达式 转换成 逆波兰式的算法：结合一个具体例子分析如下：a)给出一个中缀表达式1*(2+3)b)系统先定义两个先进后出的堆栈：运算符号栈（简称入栈in），后缀表达式输出符号栈（简称出栈out）c)系统按从左至右的顺序读取中缀表达式d)读入数字直接压入出栈（out）e)读入第一个运算符直接压入入栈（in）f)读入（直接压入入栈（in）。按上述规则读取若干次后，若，此时两栈的数据为： in 【*,( 】 ； out 【1,2】，开始读取的第二个的运算符+，并将之与入栈（in）中的栈顶运算符(进行比较，g)高于栈顶运算符级别的算符直接进栈，低于或等于栈顶级别的要将入栈(in)解栈（即出栈），按次压入出栈（out）中。比如现在入栈的运算顺序为(,*,/，此时若系统读取的运算符为+，级别比/要低，此时要按/,*的顺序压入出栈out中，并在入栈中释放/和*符号，最后得到 in ( ; out /,*的结果。f)最后读取）时要找到入栈in中最近的（，将其前面所有符号全部按后进先出的顺序压入出栈，并解压，（与）抵消。此时两栈的数据为：in 1,2,3,+ ; out *g)系统读取中缀表达式结束后将入栈in中的所有符号按后进先出的顺序全部解压，并依次压入出栈out中，最后出栈的结果就应该为1,2,3,+,*h)按先进先出的顺序将出栈out解压得到后缀标准表达式1,2,3,+,*两个堆栈先后数据情况：Inout1*1*,(1*,(1,2*,(,+1,2*,(,+1,2,3*1,2,3,+1,2,3,+,*将中缀表达式转换成逆波兰表达式过程中，特别要注意对于中缀标到式中括号的处理。1、要注意的，如果算符是（，无论入栈中栈顶级别（只看栈顶）为何直接入栈，所以，“(”的等级 只用于对其后入栈的算符进行优先级比较，在“（”入栈时是无视优先级的。 注： 逆波兰用的优先级有以下几种： 等级从高-低 是：1、* 2、+ - 3、( 4、)2、在遇到）时候找到最后进入的（，并把（前面所有的符号都压入出栈。不能仅凭运算符的级别来判断。将一个 逆波兰式 倒转回 中缀表达式 的算法： 这个就相当简单了，就是一个机械的入堆栈出堆栈的操作，1）设置一个堆栈，将逆波兰式从左到右开始进行出入堆栈操作，还以上例为例：1,2,3,+,*2）遇到数字直接压栈；例如，上例逆波兰先进行三次入栈操作，堆栈的格局是： 1，2，3（栈顶）；3）遇到算符，将堆栈中的两个数字出栈。 如，读到+号后，2，3出栈，进行运算。注意，出栈时先出栈的元素是右算子，后出栈的是左算子，上例是2+3，不是3+2；4）将运算的结果作为新的算子，压入堆栈中。如运算结果(2+3)入栈，堆栈格局：1,(2+3)；5）反复1-4的操作，得到的中序表达式就是： 1*（2+3）；中序表式生成的逆波兰式唯