第三章栈和队列.ppt

第三章栈和队列
栈的顺序存储
# define Maxsize 100+1
typedef struct {
elemtype ST[Maxsize]
int top;
} stack;
staS)//清栈
否则 入栈
Date
20
while (ch != EOF && ch != '\n') {
switch (ch) {
case '#' : Pop(S,e); break;
case '@': ClearStack(S); break;// 重置S为空栈
default : Push(S, ch); break;
}
ch = getchar(); // 从终端接收下一个字符
}
ClearStack(S); // 重置S为空栈
if (ch != EOF) ch = getchar();
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的
数据区；
i
l
h
w
Date
21
表达式 ::= (操作数1) + (运算符op) + (操作数2)
操作数 ::= 简单变量 | 表达式
简单变量 :: = 标识符 | 无符号整数
例2 表达式求值
-----利用算符优先级法则
Date
22
算符间的优先级关系
1 2
+
–
*
/
（
）
#
+







–







*







/







（





=
）






#





=
Date
23
例如: Exp = a  b + (c  d / e)  f
中缀式: #a  b + c  d / e  f#
使用两个栈：
栈OPTR寄存运算符OP  （包括（）和#）
栈OPND寄存操作数
Date
24
例如: #4+ 2  3  10 / 5 #
OPTR
OPND
#
4
+
Date
25
算符间的优先级关系
1 2
+
–
*
/
（
）
#
+







–







*







/







（





=
）






#





=
Date
26
例如: #4+ 2  3  10 / 5 #
OPTR
OPND
#
4
+
2
+
+

Date
27
算符间的优先级关系
1 2
+
–
*
/
（
）
#
+







–







*







/







（





=
）






#





=
Date
28
例如: #4+ 2  3  10 / 5 #
OPTR
OPND
#
4
+
2

3
–
Date
29
算符间的优先级关系
1 2
+
–
*
/
（
）
#
+







–







*







/







（





=
）






#





=
Date
30