（
top
*
top
+
top
#
top
空栈
21
栈的应用：表达式求值
步 输入 类型
动作
栈内容
0
#进栈
#
1 A 操作数
#
2 + 操作符 isp(#) < icp(+), 进栈 # +
3 B 操作数
#+
4 * 操作符 isp(+) < icp(*), 进栈 # + *
5 ( 操作符 isp(*) < icp( ( ), 进栈 # + * (
isp(( ) == icp( )), 退栈
栈内容 # # #+ #+ #+* #+*( #+*( #+*(#+*(#+*( #+*
后缀输出
A A AB AB AB ABC ABC ABCD ABCD– ABCD-
中缀表示转换为后缀表示过程：
A+B* (C-D)-E/F
后缀输出： ABC
top
-
top
9 E 操作数 进栈
R3 E
10 F 操作数 进栈
R3 E F
11 / 操作符 F、E退栈，计算R4=E / F进栈
R3 R4
12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5
后缀表达式求值过程： ABCD- * +EF / -
top
F
top
E
top
R3=A+R2
16
栈的应用：表达式求值
9 E 操作数 进栈
R3 E
10 F 操作数 进栈
R3 E F
11 / 操作符 F、E退栈，计算R4=E / F进栈
R3 R4
12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5
后缀表达式求值过程： ABCD- * +EF / -
R3=A+R2
top
R2=B*R1
top
A
top
空栈
15
栈的应用：表达式求值
步 输入 类型
动作
栈中内容
1
置空栈
2 A 操作数 进栈
A
3 B 操作数 进栈
AB
4 C 操作数 进栈
ABC
5 D 操作数 进栈
ABCD
6 - 操作符 D、C退栈，计算R1=C-D进栈
A B R1
7 * 操作符 R1、B退栈，计算R2=B*R1进栈 A R2
8 + 操作符 R2、A退栈，计算R3=A+R2进栈 R3
各个算术操作符的优先级
操作符
#
isp(栈内优先级)
0
icp(栈外优先级)
0
(
*/%
+-
1
5
3
6
4
2
)
6
1
19
栈的应用：表达式求值
中缀表达式转换为后缀表达式算法
操作符栈初始化，结束符#进栈，读入中缀表达式 的首字符ch
重复执行以下步骤，直到ch=#，同时栈顶操作符 也是#，停止循环
若ch是操作数直接输出，读入下一字符ch 若ch是操作符，比较ch和栈顶操作符op优先级：
中缀表示转换为后缀表示过程：
A+B* (C-D)-E/F
后缀输出： ABCD-
top
-
top
（
top
*
+
#
22
栈的应用：表达式求值
步 输入 类型
动作
10 - 操作符 isp(*) > icp(-), 退栈
isp(+) > icp(-), 退栈
isp(#) > icp(-), 进栈
11 E 操作数
栈内容 后缀输出
9 E 操作数 进栈
R3 E
10 F 操作数 进栈
R3 E F
11 / 操作符 F、E退栈，计算R4=E / F进栈
R3 R4
12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5
后缀表达式求值过程： ABCD- * +EF / -
top
D
top
C
top
B
top
A
top
空栈
12
栈的应用：表达式求值
步 输入 类型
动作
栈中内容
1
置空栈
2 A 操作数 进栈
A
3 B 操作数 进栈
AB
4 C 操作数 进栈
ABC
5 D 操作数 进栈
ABCD
6 - 操作符 D、C退栈，计算R1=C-D进栈
A B R1
7 * 操作符 R1、B退栈，计算R2=B*R1进栈 A R2
8 + 操作符 R2、A退栈，计算R3=A+R2进栈 R3
6 C 操作数
#+*(
7 - 操作符 isp( ( ) < icp(-), 进栈 # + * ( -
8 D 操作数
#+*(-
9 ) 操作符 isp(-) > icp( ) ), 退栈 # + * (
isp( ( ) == icp( ) ), 退栈 # + *
后缀输出
A A AB AB AB ABC ABC ABCD ABCD– ABCD-
ห้องสมุดไป่ตู้
#+
ABCD-*
#
ABCD-*+
#-
ABCD-*+
#-
ABCD-*+E
中缀表示转换为后缀表示过程：
A+B* (C-D)-E/F
后缀输出： ABCD- * +
12 / 操作符 isp(-) < icp(/), 进栈 # - / ABCD-*+E
13 F 操作数
# - / ABCD-*+EF
10
栈的应用：表达式求值
后缀表达式求值过程
顺序扫描后缀表达式每一项 若该项是操作数，则进栈 若该项是操作符<op>，
若是单目运算符，则出栈一个操作数X，并将计算结 果<op>X进栈
若是双目运算符，则连续出栈两个操作数X和Y，并将 计算结果X <op> Y进栈
当表达式的所有项都扫描并处理完后，栈顶存放的 就是最后的计算结果。
步 输入 类型
动作
栈中内容
1
置空栈
2 A 操作数 进栈
A
3 B 操作数 进栈
AB
4 C 操作数 进栈
ABC
5 D 操作数 进栈
ABCD
6 - 操作符 D、C退栈，计算R1=C-D进栈
A B R1
7 * 操作符 R1、B退栈，计算R2=B*R1进栈 A R2
8 + 操作符 R2、A退栈，计算R3=A+R2进栈 R3
#进栈
1 A 操作数
2 + 操作符 isp(#) < icp(+), 进栈
3 B 操作数
4 * 操作符 isp(+) < icp(*), 进栈
5 ( 操作符 isp(*) < icp( ( ), 进栈 6 C 操作数 7 - 操作符 isp( ( ) < icp(-), 进栈
8 D 操作数 9 ) 操作符 isp(-) > icp( ) ), 退栈
9 E 操作数 进栈
R3 E
10 F 操作数 进栈
R3 E F
11 / 操作符 F、E退栈，计算R4=E / F进栈
R3 R4
12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5
后缀表达式求值过程： ABCD- * +EF / -
R2=B*R1
top
R1=C-D
top
B
top
A
14
栈的应用：表达式求值
9 E 操作数 进栈
R3 E
10 F 操作数 进栈
R3 E F
11 / 操作符 F、E退栈，计算R4=E / F进栈
R3 R4
12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5
后缀表达式求值过程： ABCD- * +EF / -
R5=R3-R4
top
R4=E/F
top
R3=A+R2
top
若icp(ch) > isp(op)，令ch进栈，读入下一字符ch 若icp(ch) < isp(op)，退栈，并输出 若icp(ch)==isp(op)，退栈不输出；若退出的是(，则读入
下一个字符ch
算法结束，输出序列即为所得后缀表达式
20
栈的应用：表达式求值
步 输入 类型
动作
0
6
栈的应用：表达式求值
一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。
算术表达式三种表示
中缀(infix)表示
<操作数> <操作符> <操作数>，如 A+B；
前缀(prefix)表示
<操作符> <操作数> <操作数>，如 +AB；
后缀(postfix)表示
第三章 栈与队列
东南大学计算机学院 方效林
本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件
本章主要内容
栈 栈的应用：表达式求值 栈与递归 队列 队列的应用：电路布线