文档介绍：1/59
第八讲****题课
本讲知识点:
(1)复****表、栈、队列的操作
(2)掌握三种数据结构的各种应用
(3)多项式运算、大整数问题、表达式求值的理解
(4)提高分析问题、处理问题的能力
2
一、表达式求值问题
算术表达式有三种表示:
中缀表示: A+B
<操作数> <操作符> <操作数>
前缀表示:+AB
后缀表示: AB+
3
表达式中相邻两个操作符的计算次序为:
优先级高的先计算;
优先级相同的自左向右计算;
当使用括号时从最内层括号开始计算。
一、表达式求值问题
4
C++中操作符的优先级
优先级操作符
1 单目+ 、-、!
2 *、/、%
3 +、-
4 <、<=、>、>=
5 ==、!=
6 &&
7 ||
5
例如:
P=( a+b )* ( c- d/e ) – f * ( g+h )
①
②
③
④
⑤
⑥
⑦
Q= –*+ab-c/de*f+gh
W=ab+cde/–*fgh+*–
练****请写出其前缀、后缀表达式。
一、表达式求值问题
6
例如:3*(7- 2)=
OPTR
OPND
=
压=入操作符号栈
求值过程演示
7
例如:3*(7- 2)=
OPTR
OPND
=
3
遇到数字3
直接压数据栈
求值过程演示
8
例如:3*(7- 2)=
OPTR
OPND
=
3
遇到符号*
比较栈顶‘=’< ‘*’
小于则压符号栈
*
求值过程演示
9
例如:3*(7- 2)=
OPTR
OPND
=
3
遇到左括号(
比较栈顶‘*’< ‘(’
小于则压符号栈
(
*
求值过程演示
10