算术表达式求值-朱亮.ppt

算术表达式求值算法解析 吉林大学计算机科学与技术学院2007级4班 朱亮 2009年11月25日 栈的应用——算术表达式求值 表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。 表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符是算术运算符（ + , - , * , / ）；界限符为左右括号和标识表达式结束的结束符。 算术表达式的表示方法 1. 中缀表达式－－运算符在操作数之间 如： A * B / C 运算规则： (1) 先计算括号内，后计算括号外； (2) 在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级； (3) 同一优先级运算，从左向右依次进行。 用计算机来处理中缀表达式比较复杂。一个中缀表达式中有多少个运算符，原则上就得对表达式扫描多少遍，才能完成计算。 在编译系统中，把中缀表达式转换成另外一种表示方法，即后缀表达式，然后对后缀式表达式进行处理，后缀表达式也称为逆波兰式。 2. 后缀表达式： 1929 年，由波兰逻辑学家（Lukasiewicz）提出。 [例] A * B / C; A B * C / ; ● 定义：运算符紧跟在两个操作数之后的表达式叫后缀 表达式。 ● 优点：① 后缀表达式没有括号 ② 不存在优先级的差别 ③ 计算过程完全按照运算符出现的先后次序  进行 ● 后缀表达式求值的方法： ① 从左到右读入后缀表达式，若读到的是操作 数，将它压入堆栈。 若读到的是运算符，就从堆栈中连续弹出两 个元素，进行相应的运算，并将结果压入栈 中。 ③ 读入结束符时，栈顶元素就是计算结果。 ② 中缀表达式 后缀表达式 a+b a b+ a+b*c a b c *+ a*b*c+c*d a b * c * c d * + (a+b)*((c-d)*e+f) a b + c d – e * f + * [例] 计算后缀表达式ABC*/DE*+AC*-; 操作 后缀表达式 栈 T2 =A/T1 T2 DE*+AC*- =; T2 DE T3 =D*E T2T3 +AC*- =; T2 T3 T4=T2+T3 T4AC*- =; T4AC T5 =A*C T4 T5 - =; T4 T5 T6 =T4- T5 =; T6 T1=B*C AT1/DE*+AC*- =; AT1 —— ABC*/DE*+AC*- =; ABC 后缀表达式求值的ADL算法： 算法EPE ( p, n ) EPE1 [初始化] CREATS ( S ) . EPE2 [表达式求值] FOR i=1 TO n DO IF NOT ( ISOPTOR( P[ i ] )) THEN S ? P[ i ] ELSE ( y ? S . x ? S. S ? APPLIED(P[ i ], x , y) ) ▌ 中缀表达式转换成后缀表达式 首先设定一个运算符栈，用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符。 基本思想：从左到右依次读出中缀表达式中的各个符号（操作数或运算符），每读出一个符号后，根据如下运算规则进行处理： 1. 假如是操作数，将其放入后缀表达式中； 2. 如果是运算符，则： （1） 栈