文档详情

算术表达式求值算法解析.ppt

发布:2017-04-14约2.18千字共15页下载文档
文本预览下载声明
算术表达式求值算法解析; 栈的应用——算术表达式求值;算术表达式的表示方法 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*-; ; ;后缀表达式求值的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) 栈空:运算符放入栈中, (2) 栈不空:比较当前读到的运算符与栈顶运算符的优先级; 1)假如读出的运算符的优先级大于栈顶运算符的优先级,则将其压入运算符栈,读中缀表达式的下一个符号。 2)若栈顶运算符的优先级比读到的运算符的优先级高或二者相等,弹出栈顶运算符放入后缀表达式中,当前读到的运算符入栈; 3)遇到“(”,压入堆栈; 4)遇到“)”,把“(”上面的操作符依次弹出加到后缀表达式中,“(”出栈; 3. 假如读出的是表达式结束符“#”,栈中剩余的运算符依次出栈并写入到后缀表达式中,转换完成。;将(A+B)*((C-D)*E+F)转换成后缀表达式 AB+CD-E*F+*;(A+B)*((C-D)*E+F) 栈 输出序列 ( A (+ A B A B + *(( A B +C *((- A B +CD *( A B +CD- *(* A B +CD- E *(+ A B +CD- E* *(+ A B +CD- E*F
显示全部
相似文档