Chapter5 栈-栈的应用(2).ppt

Chapter5 栈(Stack)(续)
本章教学内容
栈的结构特点
栈的抽象数据类型
栈的公式化描述(顺序栈)
栈的链表描述(链式栈)
栈的应用
应用栈结构求解实际问题
1、数制转换
2、括号匹配
3、函数嵌套调用
4、栈与递归
5、汉诺塔问题
6、火车车厢重排
7、表达式计算
8、迷宫问题
表达式
操作数:
运算符
界限符:
算术运算符:+,-,*,/,%等
逻辑运算符:&&,||,!
关系运算符:<,>,==,!=,>=,<=等
既可以是常数,也可以是被说明为常量或变量的标识符;
如左右括号和表达式结束符(#)等
操作数:
算术运算符:+,-,*,/,%等
既可以是常数,也可以是被说明为常量或变量的标识符;
7、表达式计算
在计算机中,表达式可以有三种不同的表示方法:
设:Exp=S1+OP+S2
称 OP +S1+S2 为表达式的前缀表示法;
称 S1+ OP + S2 为表达式的中缀表示法;
称 S1+S2 + OP 为表达式的后缀表示法。
限于讨论只含二元运算符的算术表达式:
(操作数)+(运算符)+(操作数)
例表达式 Exp=a*b+(c-d/e)*f
前缀式:+*ab*-c/def
中缀式:a*b+c-d/e*f
后缀式:ab*cde/-f*+
结论:
(1)操作数之间的相对次序不变;
(2)运算符的相对次序不同;
(3)中缀式丢失了括号信息,致使运算的次序不确定,无意义。
例表达式 Exp=a*b+(c-d/e)*f
前缀式:+*ab*-c/def
(4)前缀式的运算规则为:连续出现的两个操作数和它们之前紧靠它们的运算符构成一个最小表达式;
后缀式:ab*cde/-f*+
(5)后缀式的运算规则为:运算符在式中的顺序恰好为表达式的运算顺序;
每个运算符和它之前出现且紧靠它的两个操作数构成一个最小表达式。
后缀表达式的特点:
后缀表达式与表达式的操作数的先后次序相同,只是运算符的先后次序有所改变;
后缀表达式的运算符次序就是其执行次序;
后缀表达式中没有括号(因为括号的作用就是改变运算次序,既然后缀表达式中已经考虑了运算规则,所以就不需要括号了)。
- 如何从后缀式求值?——后缀式的特点
后缀表达式的计算方法:
从左自右依次扫描表达式的各单词:
(1)如果是操作数,存入栈中;
(2)如果是运算符,就取其前面的两个操作数(从栈中弹出的两个数)进行运算,中间结果同样存入栈中,作为下一个运算的操作数;
如此反复直到表达式处理完毕。
【注意】第一次退栈得到的操作数为运算符后的操作数;
第二次退栈得到的操作数为运算符前的操作数。
- 如何从后缀式求值?——后缀式的计算方法
例计算表达式A/(B+C*D)-E的后缀式 ABCD*+/E-
top
top
T1
B
A
top
T2
A
读入*
C*D->T1
读入+
B+T1->T2
top
T3
top
E
T3
top
T4
读入E
读入-
T3-E->T4
读入/
A/T2->T3
B
C
D
A