逆波兰表达式.doc

逆波兰表达式.doc逆波兰表达式 表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,这称为中缀表达式(InfixExpression),如A+B。波兰数学家JanLukasiewicz提出了另一种数学表示法,它有两种表示形式:把运算符写在操作数之前,称为波兰表达式(PolishExpression)或前缀表达式(PrefixExpression),如+AB;把运算符写在操作数之后,称为逆波兰表达式(ReversePolishExpression)或后缀表达式(SuffixExpression),如AB+;其中,逆波兰表达式在编译技术中有着普遍的应用。 算法:一、将中缀表达式转换成后缀表达式算法:1、从左至右扫描一中缀表达式。2、若读取的是操作数,则判断该操作数的类型,并将该操作数存入操作数堆栈3、若读取的是运算符  (1)该运算符为左括号"(",则直接存入运算符堆栈。  (2)该运算符为右括号")",则输出运算符堆栈中的运算符到操作数堆栈,直到遇到左括号为止。  (3)该运算符为非括号运算符:    (a)若运算符堆栈栈顶的运算符为括号,则直接存入运算符堆栈。    (b)若比运算符堆栈栈顶的运算符优先级高或相等,则直接存入运算符堆栈。    (c)若比运算符堆栈栈顶的运算符优先级低,则输出栈顶运算符到操作数堆栈,并将当前运算符压入运算符堆栈。4、当表达式读取完成后运算符堆栈中尚有运算符时,则依序取出运算符到操作数堆栈,直到运算符堆栈为空。 二、逆波兰表达式求值算法:1、循环扫描语法单元的项目。2、如果扫描的项目是操作数,则将其压入操作数堆栈,并扫描下一个项目。3、如果扫描的项目是一个二元运算符,则对栈的顶上两个操作数执行该运算。4、如果扫描的项目是一个一元运算符,则对栈的最顶上操作数执行该运算。5、将运算结果重新压入堆栈。6、重复步骤2-5,堆栈中即为结果值。    C语言讲解【复合复制运算符】时会提到,复合运算简练并且产生机器码的效率高。为什么效率高呢,这就必须要了解:【编译原理】中提到的【逆波兰式】。逆波兰表达式又叫做【后缀表达式】。推而广之必然还存在【前缀表达式】、【中缀表达式。】(有时也成为,前序式,中序式,后序式)。中缀表达式就是我们常用的所谓的标准的表达式如"A+B",它在数学上学名叫中缀表达式(InfixNotation),原因是:运算符号在两个运算对象的中间。      其优势: 在于只:用两种简单操作,入栈和出栈就可以搞定任何普通表达式(仅包含:+-*/和()的表达式)的运算。      其基本运算方式 :如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。      为什么说逆波兰式产生机器码的效率高:因为逆波兰式非常易于计算机的处理。原因是这样的。举例:    3  32  +53  *  - 12342  -  *  8/ 乍一看上面两个式子很奇怪,是吗?它们就是一种表达式的记法——逆波兰表达式。现在,准备一个很窄的圆筒,筒是有底的,像一个细长的杯子,粗细刚好和一枚硬币相当。再做几个和硬币一样大的小圆纸片,在纸片上依次写上“3”“32”“+”“5”“3”“*”“-”,记住,每个纸片上要么只写一