第三章栈和队列(1)

1、第三章 栈和队列主要内容主要内容n3.1 栈栈n3.2 栈与递归栈与递归n3.3 队列队列n3.4 优先队列优先队列n3.5 双端队列双端队列描述描述 现在，有一行括号序列，请你检查这行括号是否配对。现在，有一行括号序列，请你检查这行括号是否配对。输入输入 第一行输入一个数第一行输入一个数N（0N=100）,表示有表示有N组测试数据。后面的组测试数据。后面的N行输行输入多组输入数据，每组输入数据都是一个字符串入多组输入数据，每组输入数据都是一个字符串S(S的长度小于的长度小于10000，且，且S不是空串），测试数据组数少于不是空串），测试数据组数少于5组。数据保证组。数据保证S中只含有中只含有

2、“”,“”,“(”,“)”四种四种字符。字符。输出输出 每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出输出Yes,如果不配对则输出如果不配对则输出No。样例输入样例输入 3 () () ()样例输出样例输出 No No Yes问题一：括号匹配问题一：括号匹配问题二：问题二：火车进出栈问题火车进出栈问题 判断火车的出栈顺序是否合法u/problem?id=1363编号为1,2,n的n辆火车依次进站，给定一个n的排列， 判断是否是合法的出站顺序？车站BA1, 2, 3, 4, 55, 4,

3、3, 2, 1进站进站出站出站问题三：计算表达式的值问题三：计算表达式的值求形如：A+B*(C-D)-E/F 表达式的值。78+99*56*(100-66)/3-100=?问题四：迷宫问题问题四：迷宫问题入口入口出口出口 从路口找一条路到出口。从路口找一条路到出口。 从路口找一条最短路到出口。从路口找一条最短路到出口。问题四：问题四：n后问题后问题在在 n n 行行 n n 列的列的国际象棋棋盘上，若两个皇后位于同一行、国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。同一列、同一对角线上，则称为它们为互相攻击。n n 皇后皇后问题是指问题是指找到这找到这 n

4、n 个皇后的互不攻击的布局个皇后的互不攻击的布局。0 1 2 3 01233.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端topbottom将将a a0 0放入栈放入栈3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一

5、端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端将将a a1 1放入栈放入栈topbottoma03.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端将将a a2 2放入栈放入栈a1topbottoma03.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插

6、入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端将将a a3 3放入栈放入栈a1a2topbottoma03.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端a1a3a2topbottoma03.1 栈栈n栈（栈（stack）可以定义为只允许在表

7、的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端a1a3a2topbottoma0将将a a4 4放到元素放到元素a2a2的下面的下面只能在栈顶（只能在栈顶（top所示所示位置后面）添加元素。位置后面）添加元素。3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端

8、u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端a1a3a2topbottoma0将将a a2 2从栈中删除从栈中删除只能删除栈顶元素，只能删除栈顶元素，即即top所示位置的元素。所示位置的元素。3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端a1a3a2topbottoma0将将a a3 3从栈中删除从栈中删除3.1 栈栈n

9、栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端a1a2topbottoma0将将a a2 2从栈中删除从栈中删除3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删

10、除的另一端和删除的另一端a1topbottoma0将将a a1 1从栈中删除从栈中删除3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端topbottoma0将将a a0 0从栈中删除从栈中删除3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和

11、删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端topbottom进栈：进栈：将元素加到栈顶。将元素加到栈顶。退栈：退栈：将栈顶元素删除。将栈顶元素删除。退栈进栈3.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端topbottom回顾添加，删除元素的顺序：回顾添加，删除元素的顺序：添加：添加：a

12、0，a1，a2，a3删除：删除：a3，a2，a1，a03.1 栈栈n栈（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端topbottom回顾添加，删除元素的顺序回顾添加，删除元素的顺序发现：将元素按照发现：将元素按照a0，a1，a2，a3的顺序进栈，让所有元素的顺序进栈，让所有元素出栈时出栈时a3最先出栈，其次时最先出栈，其次时a2，a1，最后是，最后是a0。3.1 栈栈n栈

13、（栈（stack）可以定义为只允许在表的末端）可以定义为只允许在表的末端进行插入和删除的线性表。进行插入和删除的线性表。u栈顶（栈顶（top）：允许插入和删）：允许插入和删除的一端除的一端u栈底（栈底（bottom）：不允许插入）：不允许插入和删除的另一端和删除的另一端topbottom栈的典型特点是：后进先出栈的典型特点是：后进先出（LIFO，Last In First Out）3.2 栈的实现方式栈的实现方式n顺序栈 (Array-based Stack)n链式栈（Linked Stack）u使用向量实现，本质上是顺序表的简化版u用单链表方式存储，其中指针的方向是从栈顶向下链接3.2.1

14、顺序栈顺序栈n顺序栈 (Array-based Stack)u使用向量实现，本质上是顺序表的简化版0 1 2 3 4 5 6 7 8 9 maxSize-1top ()data:0 1 2 3 4 5 6 7 8 9 maxSize-1top =data:0 1 2 3 4 5 6 7 8 9 maxSize-1top =0data:a1a1进栈进栈0 1 2 3 4 5 6 7 8 9 maxSize-1top =1data:a1a2进栈进栈a2a3进栈进栈0 1 2 3 4 5 6 7 8 9 maxSize-1top =2data:a1a2a3退栈退栈a30 1 2 3 4 5 6 7

15、8 9 maxSize-1top =1data:a1a2a2退栈退栈a30 1 2 3 4 5 6 7 8 9 maxSize-1top =0data:a1a2a1退栈退栈a30 1 2 3 4 5 6 7 8 9 maxSize-1top =-1data:a1a2a33.2.1 顺序栈顺序栈template class SeqStackprivate: T *elements; int top; int maxSize; void overflowProcess();public: SeqStack(int sz =50); SeqStack(const SeqStack& s);

16、SeqStack& operator=(const SeqStack& s); SeqStack(); void Push(const T &x); bool Pop(T &x); bool getTop(T &x)const; bool IsEmpty()const; bool IsFull()const; int getSize()const; void MakeEmpty(); friend ostream& operator (ostream &out, SeqStack &s;3.2.2 链式栈n链式栈（Linked S

17、tack）u用单链表方式存储，其中指针的方向是从栈顶向下链接top栈顶栈顶链式栈的栈顶在链表的表头链式栈的栈顶在链表的表头。因此，新结点的插入和栈。因此，新结点的插入和栈顶结点的删除都在链表的表头，即栈顶进行。顶结点的删除都在链表的表头，即栈顶进行。top栈空栈空topa1topa1topa1a3a2a2a1进栈进栈a2进栈进栈a3进栈进栈a3退栈退栈topa1a2a2退栈退栈topa1a2退栈退栈top基于不带头结点的单链表实现栈基于不带头结点的单链表实现栈top栈空栈空topa1a1a1a3a2a2a1进栈进栈a2进栈进栈a3进栈进栈toptopa3退栈退栈a1a2topa2退栈退栈top

18、a1a1退栈退栈top基于带头结点的单链表实现栈基于带头结点的单链表实现栈3.2.2链式栈链式栈template struct StackNode T data; StackNode *next; StackNode(T d = 0, StackNode *suc = NULL):next(suc),data(d) ;结点定义：结点定义：3.2.2 链式栈链式栈template class LinkedStackprivate: StackNode *top;public: LinkedStack(); LinkedStack(const LinkedStrack& s); Linke

19、dStack& operator=(const LinkedStack& s); LinkedStack(); void Push(const T &x); bool Pop(T &x); bool GetTop(T &x)const; int GetSize()const; bool IsEmpty()const; bool IsFull()const; void MakeEmpty(); friend ostream& operator (ostream &os, LinkedStack &s);3.3 栈的应用：括号匹配栈的

20、应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。(a*(b-c)-d)-e/(f+g)-h)*i*j-(k+m)/n对于一个括号正确匹配的式子对于一个括号正确匹配的式子，从左向右扫描它时，每一，从左向右扫描它时，每一个右括号与最近遇到的一个相同类型的左括号相匹配。个右括号与最近遇到的一个相同类型的左括号相匹配。简单的例子：简单的例子：()左右括号配对次序不正确左右括号配对次序不正确()右括号多于左括号右括号多于左括号(左括号多于右括号左括号多于右括号()左右括号匹配正确左右括号匹配正确3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否

21、匹配。编程检查下面式子中的括号是否匹配。简单的例子：简单的例子：()左右括号配对次序不正确左右括号配对次序不正确()右括号多于左括号右括号多于左括号(左括号多于右括号左括号多于右括号()左右括号匹配正确左右括号匹配正确)( () )( () 3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到左括号（左括号（”(”，“”,”），让它们进栈，让它们进栈。3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号

22、是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到左括号（左括号（”(”，“”,”），让它们进栈，让它们进栈。(3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到左括号（左括号（”(”，“”,”），让它们进栈，让它们进栈。(3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇

23、到右括号（右括号（”)”，“”,”）判断它与栈顶括号是否匹配，判断它与栈顶括号是否匹配，如果匹配，栈顶元素退栈，否如果匹配，栈顶元素退栈，否则，匹配失败，退出则，匹配失败，退出。( 3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top(从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到左括号（左括号（”(”，“”,”），让它们进栈，让它们进栈。3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列

24、，从左到右扫描括号序列，遇到遇到右括号（右括号（”)”，“”,”）判断它与栈顶括号是否匹配，判断它与栈顶括号是否匹配，如果匹配，栈顶元素退栈，否如果匹配，栈顶元素退栈，否则，匹配失败，退出则，匹配失败，退出。(3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到右括号（右括号（”)”，“”,”）判断它与栈顶括号是否匹配，判断它与栈顶括号是否匹配，如果匹配，栈顶元素退栈，否如果匹配，栈顶元素退栈，否则，匹配失败，退出则，匹配失败，退出。(3.3 栈的应用：

25、括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到右括号（右括号（”)”，“”,”）判断它与栈顶括号是否匹配，判断它与栈顶括号是否匹配，如果匹配，栈顶元素退栈，否如果匹配，栈顶元素退栈，否则，匹配失败，退出则，匹配失败，退出。(3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )( ()top从左到右扫描括号序列，从左到右扫描括号序列，遇到遇到右括号（右括号（”)”，“”,”）判断它与栈顶括号是

26、否匹配，判断它与栈顶括号是否匹配，如果匹配，栈顶元素退栈，否如果匹配，栈顶元素退栈，否则，匹配失败，退出则，匹配失败，退出。(3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) )上面括号的展示的括号匹配过程，考虑了情况上面括号的展示的括号匹配过程，考虑了情况，在括号匹配的过程中如何体现出来呢？在括号匹配的过程中如何体现出来呢？()左右括号配对次序不正确左右括号配对次序不正确()右括号多于左括号右括号多于左括号(左括号多于右括号左括号多于右括号()左右括号匹配正确左右括号匹配正确3.3 栈的应用：括号匹配栈的应用：括号匹

27、配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。( ( ) ) (右括号多于左括号右括号多于左括号( ()top( 右括号多于左括号：右括号多于左括号：扫描到扫描到多余的右括号时，栈已经空。多余的右括号时，栈已经空。3.3 栈的应用：括号匹配栈的应用：括号匹配n编程检查下面式子中的括号是否匹配。编程检查下面式子中的括号是否匹配。 ( ( ) ) ()左括号多于右括号左括号多于右括号( ()top(左括号多于右括号：左括号多于右括号：扫描到扫描到串末尾时，栈非空。串末尾时，栈非空。 3.3 栈的应用：括号匹配栈的应用：括号匹配n解决思路解决思路1.顺序扫描算数表达式（表现

28、为一个字符串），当遇到顺序扫描算数表达式（表现为一个字符串），当遇到三种三种类型的左括号时候让该括号进栈类型的左括号时候让该括号进栈；2.当扫描到某一种类型的右括号时，当扫描到某一种类型的右括号时，比较当前栈顶元素是否比较当前栈顶元素是否与之匹配，若匹配，退栈继续判断与之匹配，若匹配，退栈继续判断；3.若当前栈顶元素与当前扫描的括号不匹配，则左右括号配若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确，匹配失败，直接退出；对次序不正确，匹配失败，直接退出；4.若字符串当前为某种类型的右括号而堆栈已经空，则右括若字符串当前为某种类型的右括号而堆栈已经空，则右括号多于左括号，匹配失败，

29、直接退出号多于左括号，匹配失败，直接退出；5.字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号，匹配失败型的左括号），则说明左括号多于右括号，匹配失败；6.正常结束则括号匹配正确。正常结束则括号匹配正确。3.3 栈的应用：括号匹配栈的应用：括号匹配class BracketMatcherprivate: const char* exp; / 括号串括号串 char terminator; /括号串的结束标记括号串的结束标记public: BracketMatcher(const char* ep,char

30、term):exp(ep),terminator(term) bool BracketMatching();括号匹配类括号匹配类bool BracketMatcher:BracketMatching() Stack s; char elem; const char* it=exp; while(*it!=terminator) if(=*it|=*it|=*it) s.Push(*it); it+; else if(!s.IsEmpty() else return false; return s.IsEmpty();s.GetTop(elem);if()=*it&(=elem) it+

31、; s.Pop();else if(=*it&=elem) it+; s.Pop();else if(=*it&=elem) it+; s.Pop();else return false;执行括号匹配执行括号匹配3.3栈的应用：表达式求值栈的应用：表达式求值表达式是由操作数（亦称运算对象）、操作表达式是由操作数（亦称运算对象）、操作符（亦称运算符）和分界符组成的。符（亦称运算符）和分界符组成的。u算术表达式有算术表达式有3中表示方法：中表示方法：u中缀中缀(infix)(infix)表示表示 ，如如 A+BA+B；u前缀前缀(prefix)(prefix)表示表示 ，如如 +A

32、B+AB；u后缀后缀(postfix)(postfix)表示表示 ，如如 AB+AB+；3.3 栈的应用：表达式求值栈的应用：表达式求值n平时常见的表达式均为表达式的中缀形式平时常见的表达式均为表达式的中缀形式23 + 2 * 3 ( 2* 3)0!+1-(2-(3!-4)5)*67-8+9可以将表达式的中缀形式转换为表达式的前缀和后缀形式。可以将表达式的中缀形式转换为表达式的前缀和后缀形式。3.3 栈的应用：表达式求值栈的应用：表达式求值n中缀形式转换为前缀形式中缀形式转换为前缀形式( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )u先对中缀表达式按运算优先次序通统加上括号，再把

33、操先对中缀表达式按运算优先次序通统加上括号，再把操作符前移到左括号前并以就近移动为原则，最后将所有括作符前移到左括号前并以就近移动为原则，最后将所有括号消去。号消去。 +23 * 2 3 * 2 323 + 2 * 3 ( 2* 3)( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )23 2 3 2 3*+ u先对中缀表达式按运算优先次序加上括号，再把操作符后先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消移到右括号的后面并以就近移动为原则，最后将所有括号消去。去。3.3 栈的应用：表达式求值栈的应用：表达式求值n中缀形式转换为

34、后缀形式中缀形式转换为后缀形式23 + 2 * 3 ( 2* 3)3.3 栈的应用：表达式求值栈的应用：表达式求值n基于前缀形式计算表达式的值基于前缀形式计算表达式的值n基于中缀形式计算表达式的值基于中缀形式计算表达式的值n基于后缀形式计算表达式的值基于后缀形式计算表达式的值3.3 栈的应用：表达式求值栈的应用：表达式求值n基于后缀形式计算表达式的值基于后缀形式计算表达式的值23 2 3 2 3*+ 23 2 3 2 3*+ 23 2 3 6*+ 计算计算2*323 2 729*+ 计算计算3623 1458+ 计算计算2*7291481 计算计算23+1458思路：扫描表达思路：扫描表达式后

35、缀表示，遇式后缀表示，遇到运算符，使用到运算符，使用它前面的两个操它前面的两个操作数做运算。作数做运算。基于后缀形式计算表达式的值基于后缀形式计算表达式的值如何避免重复扫如何避免重复扫描表达式？描表达式？记录扫描过的操记录扫描过的操作数作数23 2323*+ 遇到遇到*运算符，取出保存的最后两个操作数运算符，取出保存的最后两个操作数2和和3，计算，计算2*3 并将结果保存。并将结果保存。23 2 3 6遇到遇到运算符，取出保存的最后两个操作数运算符，取出保存的最后两个操作数3和和6，计算，计算36 并将结果保存。并将结果保存。23 2323*+ 23 2 729遇到遇到*运算符，取出保存的最后

36、两个操作数运算符，取出保存的最后两个操作数2和和729，计算，计算2*729并将结果保存。并将结果保存。23 2323*+ 23 1458遇到遇到+运算符，取出保存的最后两个操作数运算符，取出保存的最后两个操作数23和和1458，计算，计算23+1458并将结果保存。并将结果保存。23 2323*+ 1481表达式遍历完毕，保存记录中的数即为表达式计算结果。表达式遍历完毕，保存记录中的数即为表达式计算结果。23 2323*+ 回顾上述过程可知：回顾上述过程可知：u用于记录扫描操作数的结构可以用栈来实现。用于记录扫描操作数的结构可以用栈来实现。u为了算法书写方便需要用一个表达式结束的标记，扫为了

37、算法书写方便需要用一个表达式结束的标记，扫描到结束标记时，表达式计算过程结束。描到结束标记时，表达式计算过程结束。RpnEvaluate(expr) / 假定假定RPN表达式表达式expr语法正确语法正确 定义用于存放操作数的栈定义用于存放操作数的栈S; while (expr 尚未扫描完毕尚未扫描完毕) 读入读入expr的下一个元素的下一个元素x; if(x是操作数是操作数) 将将x压入栈压入栈S; else 从栈从栈S中弹出运算符中弹出运算符x所需数目操作数所需数目操作数 对弹出的操作数实施对弹出的操作数实施x运算，并将运算运算，并将运算 结果压入结果压入S; 返回栈顶返回栈顶后缀表达式求

38、值算法后缀表达式求值算法3.3 栈的应用：表达式求值栈的应用：表达式求值n基于中缀形式计算表达式的值基于中缀形式计算表达式的值23 + 2 * 3 ( 2* 3)-1中缀表达式：中缀表达式： 23 + 2 * 3 ( 2* 3)-1值的计算过程值的计算过程23 + 2 *3 ( 2*3 ) -123 + 2 *3 6-123 + 2 *729-123 + 1458 -11481-11480u优先级高的先计算；优先级高的先计算；u优先级相同的自左优先级相同的自左向右计算；向右计算；u当使用括号时从最当使用括号时从最内层括号开始计算。内层括号开始计算。表达式计算遵循规则：表达式计算遵循规则：中缀表

39、达式：中缀表达式： 23 + 2 * 3 ( 2* 3)-1值的计算过程值的计算过程23 + 2 *3 ( 2*3 ) -123 + 2 *3 6-123 + 2 *729-123 + 1458 -11481-11480从左向右扫描表达式，从左向右扫描表达式，依次判断每个运算符的依次判断每个运算符的优先级优先级是否大于它右边是否大于它右边运算符的运算符的优先级优先级，如果，如果大于则计算。大于则计算。扫描一次表达式，做扫描一次表达式，做一个运算，一个运算，如何避免如何避免多次扫描表达式？多次扫描表达式？n运算符优先级表运算符优先级表+-*/!()+-*/!(-*/!(=)0P(#)+进栈进栈0

40、0进栈进栈P(*)P(+)*进栈进栈进栈进栈P()P(*)进栈进栈P()P()(进栈进栈进栈进栈P(*)P()*进栈进栈进栈进栈P()P(-)从操作符从操作符栈弹出栈栈弹出栈顶的顶的；从；从操作数栈操作数栈弹出两个弹出两个操作数操作数6和和3；运算后；运算后将结果将结果729压入操作压入操作数栈。数栈。操操作作数数栈栈操操作作符符栈栈使用双栈计算表达式：使用双栈计算表达式： 23 + 2 * 3 ( 2* 3)-1值的过程值的过程23 + 2 *729-100P(*)P(-)从操作符从操作符栈弹出栈栈弹出栈顶的顶的*；从；从操作数栈操作数栈弹出两个弹出两个操作数操作数729和和2；运算；运算后

41、将结果后将结果1458压入压入操作数栈。操作数栈。操操作作数数栈栈操操作作符符栈栈使用双栈计算表达式：使用双栈计算表达式： 23 + 2 * 3 ( 2* 3)-1值的过程值的过程23 + 1458 -100P(+)P(-)从操作符从操作符栈弹出栈栈弹出栈顶的顶的*；从；从操作数栈操作数栈弹出两个弹出两个操作数操作数1458和和23；运算后将运算后将结果结果1481压入操作压入操作数栈。数栈。操操作作数数栈栈操操作作符符栈栈使用双栈计算表达式：使用双栈计算表达式： 23 + 2 * 3 ( 2* 3)-1值的过程值的过程1481-100P(-)P(0)-入栈入栈入栈入栈P(-)P(0)从操作符

42、从操作符栈弹出栈栈弹出栈顶的顶的-；从；从操作数栈操作数栈弹出两个弹出两个操作数操作数1481和和1；运算后将运算后将结果结果1480压入操作压入操作数栈。数栈。操操作作数数栈栈操操作作符符栈栈使用双栈计算表达式：使用双栈计算表达式： 23 + 2 * 3 ( 2* 3)-1值的过程值的过程148000P(0)=P(0)从操作符从操作符栈弹出栈栈弹出栈顶的顶的0；操操作符栈为作符栈为空空；操作；操作数栈中的数栈中的元素即为元素即为计算结果。计算结果。操操作作数数栈栈操操作作符符栈栈使用双栈计算表达式：使用双栈计算表达式： 23 + 2 * 3 ( 2* 3)-1值的过程值的过程14800P(0

43、)=P(0)从操作符从操作符栈弹出栈栈弹出栈顶的顶的#；操操作符栈为作符栈为空空；操作操作数栈顶元数栈顶元素即为计素即为计算结果算结果。操操作作数数栈栈操操作作符符栈栈注意：表达式正确计算完毕，操作符栈为空；注意：表达式正确计算完毕，操作符栈为空；使用双栈计算表达式：使用双栈计算表达式： 23 + 2 * 3 ( 2* 3)-1值的过程值的过程double Evaluate(char *s) Stack opnd;/ 操作数栈操作数栈 Stackoptr;/运算符栈运算符栈 optr.Push(0);/ 头哨兵入栈头哨兵入栈 while(!optr.Empty() if(当前当前*s为数字为数

44、字) /若当前字符为操作数若当前字符为操作数 ReadNumber(s,opnd);/操作数进栈操作数进栈 else / 当前当前*s为操作符为操作符 switch(比较操作符栈顶元素与比较操作符栈顶元素与*s的优先级的优先级) case : / 操作符栈顶元素优先级大操作符栈顶元素优先级大 计算表达式的值计算表达式的值,并将计算结果压入操作数栈并将计算结果压入操作数栈; 中缀形式表达式求值算法中缀形式表达式求值算法3.3 栈的应用：表达式求值栈的应用：表达式求值n比较后缀形式和中缀形式求解表达式值的比较后缀形式和中缀形式求解表达式值的算法可知，后缀形式求值算法比较简单。算法可知，后缀形式求值

45、算法比较简单。不过现实中，我们往往遇到的是表达式的不过现实中，我们往往遇到的是表达式的中缀形式，如何用算法将表达式的中缀形中缀形式，如何用算法将表达式的中缀形式转换为后缀形式呢？式转换为后缀形式呢？( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)23 2 3 2 3*+1- 中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示23 + 2 *3 ( 2*3) -1进栈进栈P(+)P(#)+进栈进栈00进栈进栈P(*)P(+)*进栈进栈进栈进栈P()P(*)进栈进栈P()P()(进栈进栈进栈进栈P(*)P()*进栈进栈进栈进栈P()P(-), 入操作数入操作数退栈。退栈。操操

46、作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *23 + 2 *3 2-100P(*)P(-), *入操作数入操作数退栈。退栈。操操作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)红圈中的操作数和操作符看做一个红圈中的操作数和操作符看做一个数（利用后缀表示算）。此时将数（利用后缀表示算）。此时将3(2*3)转变成后缀形式转变成后缀形式: 3 2 3 * 23 + 2 *3 2-100P(+)P(-), +入操作数入操作数退栈。退栈。操操作作数数栈栈

47、操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)红圈中的操作数和操作符看做一个红圈中的操作数和操作符看做一个数（利用后缀表示算）。此时将数（利用后缀表示算）。此时将2*3(2*3)转变成后缀形式转变成后缀形式:2 3 2 3 * *23 + 2 *3 2-100P(0)P(-), -入操作符入操作符栈。栈。操操作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)红圈中的操作数和操作符看做一个红圈中

48、的操作数和操作符看做一个数（利用后缀表示算）。此时将数（利用后缀表示算）。此时将23+2*3(2*3)转变成后缀形式转变成后缀形式:23 2 3 2 3 * * +23 + 2 *3 2-1001入操作数入操作数栈。栈。操操作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)红圈中的操作数和操作符看做一个红圈中的操作数和操作符看做一个数（利用后缀表示算）。此时将数（利用后缀表示算）。此时将23+2*3(2*3)转变成后缀形式转变成后缀形式:23 2 3 2 3 * * +23 + 2 *3

49、2-100操操作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)红圈中的操作数和操作符看做一个红圈中的操作数和操作符看做一个数（利用后缀表示算）。此时将数（利用后缀表示算）。此时将23+2*3(2*3)转变成后缀形式转变成后缀形式:23 2 3 2 3 * * +P(-)P(0), -入操作数入操作数栈。栈。23 + 2 *3 2-100操操作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )

50、 1)红圈中的操作数和操作符看做一个红圈中的操作数和操作符看做一个数（利用后缀表示算）。此时将数（利用后缀表示算）。此时将23+2*3(2*3)-1转变成后缀形式转变成后缀形式:23 2 3 2 3 * * + 1 -P(0)=P(0), 0出栈，出栈，算法结束，操作数算法结束，操作数栈中即为后缀形式。栈中即为后缀形式。23 + 2 *3 2-100操操作作数数栈栈操操作作符符栈栈中缀形式转后缀形式过程演示中缀形式转后缀形式过程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)P(0)=P(0), 0出栈，出栈，算法结束，操作数算法结束，操作数栈中即为后缀形式。栈

51、中即为后缀形式。思考问题：算法过程中操作数栈只思考问题：算法过程中操作数栈只是在记录信息（操作数和操作符），是在记录信息（操作数和操作符），并没有信息出栈，那么需要操作数并没有信息出栈，那么需要操作数栈吗？栈吗？double Evaluate(char *s) Stack opnd;/ 操作数栈操作数栈 Stackoptr;/运算符栈运算符栈 optr.Push(0);/ 头哨兵入栈头哨兵入栈 while(!optr.Empty() if(当前当前*s为数字为数字) /若当前字符为操作数若当前字符为操作数 ReadNumber(s,opnd);/操作数进栈操作数进栈 else / 当前当前*s为操作符为操作符 switch(比较操作符栈顶元素与比较操作符栈顶元素与*s的优先级的优先级) case : / 操作符栈顶元素优先级大操作符栈顶元素优先级大 计算表达式的值计算表达式的值,并将计算结果压入操作数栈并将计算结果压入操作数栈; 中缀形式转后缀形式算法中缀形式转后缀形式算法直接输出此数字直接输出此数字; /注意