算术表达式求值算法解析.ppt
文本预览下载声明
算术表达式求值算法解析; 栈的应用——算术表达式求值;算术表达式的表示方法
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
显示全部