第三章棧和隊列(1)

1、第三章 棧和隊列主要內容主要內容n3.1 棧棧n3.2 棧與遞歸棧與遞歸n3.3 隊列隊列n3.4 優(yōu)先隊列優(yōu)先隊列n3.5 雙端隊列雙端隊列描述描述 現(xiàn)在，有一行括號序列，請你檢查這行括號是否配對?，F(xiàn)在，有一行括號序列，請你檢查這行括號是否配對。輸入輸入 第一行輸入一個數(shù)第一行輸入一個數(shù)N（0N=100）,表示有表示有N組測試數(shù)據(jù)。后面的組測試數(shù)據(jù)。后面的N行輸行輸入多組輸入數(shù)據(jù)，每組輸入數(shù)據(jù)都是一個字符串入多組輸入數(shù)據(jù)，每組輸入數(shù)據(jù)都是一個字符串S(S的長度小于的長度小于10000，且，且S不是空串），測試數(shù)據(jù)組數(shù)少于不是空串），測試數(shù)據(jù)組數(shù)少于5組。數(shù)據(jù)保證組。數(shù)據(jù)保證S中只含有中只含有

2、“”,“”,“(”,“)”四種四種字符。字符。輸出輸出 每組輸入數(shù)據(jù)的輸出占一行，如果該字符串中所含的括號是配對的，則每組輸入數(shù)據(jù)的輸出占一行，如果該字符串中所含的括號是配對的，則輸出輸出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 列的列的國際象棋棋盤上，若兩個皇后位于同一行、國際象棋棋盤上，若兩個皇后位于同一行、同一列、同一對角線上，則稱為它們?yōu)榛ハ喙?。同一列、同一對角線上，則稱為它們?yōu)榛ハ喙簟 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回顧添加，刪除元素的順序回顧添加，刪除元素的順序發(fā)現(xiàn)：將元素按照發(fā)現(xiàn)：將元素按照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 棧的實現(xiàn)方式棧的實現(xiàn)方式n順序棧 (Array-based Stack)n鏈式棧（Linked Stack）u使用向量實現(xiàn)，本質上是順序表的簡化版u用單鏈表方式存儲，其中指針的方向是從棧頂向下鏈接3.2.1

14、順序棧順序棧n順序棧 (Array-based Stack)u使用向量實現(xiàn)，本質上是順序表的簡化版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?？諚？誸opa1topa1topa1a3a2a2a1進棧進棧a2進棧進棧a3進棧進棧a3退棧退棧topa1a2a2退棧退棧topa1a2退棧退棧top基于不帶頭結點的單鏈表實現(xiàn)?；诓粠ь^結點的單鏈表實現(xiàn)棧top?？諚？誸opa1a1a1a3a2a2a1進棧進棧a2進棧進棧a3進棧進棧toptopa3退棧退棧a1a2topa2退棧退棧top

18、a1a1退棧退棧top基于帶頭結點的單鏈表實現(xiàn)?；趲ь^結點的單鏈表實現(xiàn)棧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編程檢查下面式子中的括號是否匹配。編程檢查下面式子中的括號是否匹配。( ( ) )上面括號的展示的括號匹配過程，考慮了情況上面括號的展示的括號匹配過程，考慮了情況，在括號匹配的過程中如何體現(xiàn)出來呢？在括號匹配的過程中如何體現(xiàn)出來呢？()左右括號配對次序不正確左右括號配對次序不正確()右括號多于左括號右括號多于左括號(左括號多于右括號左括號多于右括號()左右括號匹配正確左右括號匹配正確3.3 棧的應用：括號匹配棧的應用：括號匹

27、配n編程檢查下面式子中的括號是否匹配。編程檢查下面式子中的括號是否匹配。( ( ) ) (右括號多于左括號右括號多于左括號( ()top( 右括號多于左括號：右括號多于左括號：掃描到掃描到多余的右括號時，棧已經空。多余的右括號時，棧已經空。3.3 棧的應用：括號匹配棧的應用：括號匹配n編程檢查下面式子中的括號是否匹配。編程檢查下面式子中的括號是否匹配。 ( ( ) ) ()左括號多于右括號左括號多于右括號( ()top(左括號多于右括號：左括號多于右括號：掃描到掃描到串末尾時，棧非空。串末尾時，棧非空。 3.3 棧的應用：括號匹配棧的應用：括號匹配n解決思路解決思路1.順序掃描算數(shù)表達式（表現(xiàn)

28、為一個字符串），當遇到順序掃描算數(shù)表達式（表現(xiàn)為一個字符串），當遇到三種三種類型的左括號時候讓該括號進棧類型的左括號時候讓該括號進棧；2.當掃描到某一種類型的右括號時，當掃描到某一種類型的右括號時，比較當前棧頂元素是否比較當前棧頂元素是否與之匹配，若匹配，退棧繼續(xù)判斷與之匹配，若匹配，退棧繼續(xù)判斷；3.若當前棧頂元素與當前掃描的括號不匹配，則左右括號配若當前棧頂元素與當前掃描的括號不匹配，則左右括號配對次序不正確，匹配失敗，直接退出；對次序不正確，匹配失敗，直接退出；4.若字符串當前為某種類型的右括號而堆棧已經空，則右括若字符串當前為某種類型的右括號而堆棧已經空，則右括號多于左括號，匹配失敗，

29、直接退出號多于左括號，匹配失敗，直接退出；5.字符串循環(huán)掃描結束時，若堆棧非空（即堆棧尚有某種類字符串循環(huán)掃描結束時，若堆棧非空（即堆棧尚有某種類型的左括號），則說明左括號多于右括號，匹配失敗型的左括號），則說明左括號多于右括號，匹配失??；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;執(zhí)行括號匹配執(zhí)行括號匹配3.3棧的應用：表達式求值棧的應用：表達式求值表達式是由操作數(shù)（亦稱運算對象）、操作表達式是由操作數(shù)（亦稱運算對象）、操作符（亦稱運算符）和分界符組成的。符（亦稱運算符）和分界符組成的。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先對中綴表達式按運算優(yōu)先次序通統(tǒng)加上括號，再把

33、操先對中綴表達式按運算優(yōu)先次序通統(tǒng)加上括號，再把操作符前移到左括號前并以就近移動為原則，最后將所有括作符前移到左括號前并以就近移動為原則，最后將所有括號消去。號消去。 +23 * 2 3 * 2 323 + 2 * 3 ( 2* 3)( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )23 2 3 2 3*+ u先對中綴表達式按運算優(yōu)先次序加上括號，再把操作符后先對中綴表達式按運算優(yō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、綴表示，遇式后綴表示，遇到運算符，使用到運算符，使用它前面的兩個操它前面的兩個操作數(shù)做運算。作數(shù)做運算?；诤缶Y形式計算表達式的值基于后綴形式計算表達式的值如何避免重復掃如何避免重復掃描表達式？描表達式？記錄掃描過的操記錄掃描過的操作數(shù)作數(shù)23 2323*+ 遇到遇到*運算符，取出保存的最后兩個操作數(shù)運算符，取出保存的最后兩個操作數(shù)2和和3，計算，計算2*3 并將結果保存。并將結果保存。23 2 3 6遇到遇到運算符，取出保存的最后兩個操作數(shù)運算符，取出保存的最后兩個操作數(shù)3和和6，計算，計算36 并將結果保存。并將結果保存。23 2323*+ 23 2 729遇到遇到*運算符，取出保存的最后

36、兩個操作數(shù)運算符，取出保存的最后兩個操作數(shù)2和和729，計算，計算2*729并將結果保存。并將結果保存。23 2323*+ 23 1458遇到遇到+運算符，取出保存的最后兩個操作數(shù)運算符，取出保存的最后兩個操作數(shù)23和和1458，計算，計算23+1458并將結果保存。并將結果保存。23 2323*+ 1481表達式遍歷完畢，保存記錄中的數(shù)即為表達式計算結果。表達式遍歷完畢，保存記錄中的數(shù)即為表達式計算結果。23 2323*+ 回顧上述過程可知：回顧上述過程可知：u用于記錄掃描操作數(shù)的結構可以用棧來實現(xiàn)。用于記錄掃描操作數(shù)的結構可以用棧來實現(xiàn)。u為了算法書寫方便需要用一個表達式結束的標記，掃為了

37、算法書寫方便需要用一個表達式結束的標記，掃描到結束標記時，表達式計算過程結束。描到結束標記時，表達式計算過程結束。RpnEvaluate(expr) / 假定假定RPN表達式表達式expr語法正確語法正確 定義用于存放操作數(shù)的棧定義用于存放操作數(shù)的棧S; while (expr 尚未掃描完畢尚未掃描完畢) 讀入讀入expr的下一個元素的下一個元素x; if(x是操作數(shù)是操作數(shù)) 將將x壓入棧壓入棧S; else 從棧從棧S中彈出運算符中彈出運算符x所需數(shù)目操作數(shù)所需數(shù)目操作數(shù) 對彈出的操作數(shù)實施對彈出的操作數(shù)實施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優(yōu)先級高的先計算；優(yōu)先級高的先計算；u優(yōu)先級相同的自左優(yōu)先級相同的自左向右計算；向右計算；u當使用括號時從最當使用括號時從最內層括號開始計算。內層括號開始計算。表達式計算遵循規(guī)則：表達式計算遵循規(guī)則：中綴表

39、達式：中綴表達式： 23 + 2 * 3 ( 2* 3)-1值的計算過程值的計算過程23 + 2 *3 ( 2*3 ) -123 + 2 *3 6-123 + 2 *729-123 + 1458 -11481-11480從左向右掃描表達式，從左向右掃描表達式，依次判斷每個運算符的依次判斷每個運算符的優(yōu)先級優(yōu)先級是否大于它右邊是否大于它右邊運算符的運算符的優(yōu)先級優(yōu)先級，如果，如果大于則計算。大于則計算。掃描一次表達式，做掃描一次表達式，做一個運算，一個運算，如何避免如何避免多次掃描表達式？多次掃描表達式？n運算符優(yōu)先級表運算符優(yōu)先級表+-*/!()+-*/!(-*/!(=)0P(#)+進棧進棧0

40、0進棧進棧P(*)P(+)*進棧進棧進棧進棧P()P(*)進棧進棧P()P()(進棧進棧進棧進棧P(*)P()*進棧進棧進棧進棧P()P(-)從操作符從操作符棧彈出棧棧彈出棧頂?shù)捻數(shù)?；從；從操作?shù)棧操作數(shù)棧彈出兩個彈出兩個操作數(shù)操作數(shù)6和和3；運算后；運算后將結果將結果729壓入操作壓入操作數(shù)棧。數(shù)棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧使用雙棧計算表達式：使用雙棧計算表達式： 23 + 2 * 3 ( 2* 3)-1值的過程值的過程23 + 2 *729-100P(*)P(-)從操作符從操作符棧彈出棧棧彈出棧頂?shù)捻數(shù)?；從；從操作數(shù)棧操作數(shù)棧彈出兩個彈出兩個操作數(shù)操作數(shù)729和和2；運算；運算后

41、將結果后將結果1458壓入壓入操作數(shù)棧。操作數(shù)棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧使用雙棧計算表達式：使用雙棧計算表達式： 23 + 2 * 3 ( 2* 3)-1值的過程值的過程23 + 1458 -100P(+)P(-)從操作符從操作符棧彈出棧棧彈出棧頂?shù)捻數(shù)?；從；從操作數(shù)棧操作數(shù)棧彈出兩個彈出兩個操作數(shù)操作數(shù)1458和和23；運算后將運算后將結果結果1481壓入操作壓入操作數(shù)棧。數(shù)棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧使用雙棧計算表達式：使用雙棧計算表達式： 23 + 2 * 3 ( 2* 3)-1值的過程值的過程1481-100P(-)P(0)-入棧入棧入棧入棧P(-)P(0)從操作符

42、從操作符棧彈出棧棧彈出棧頂?shù)捻數(shù)?；從；從操作數(shù)棧操作數(shù)棧彈出兩個彈出兩個操作數(shù)操作數(shù)1481和和1；運算后將運算后將結果結果1480壓入操作壓入操作數(shù)棧。數(shù)棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧使用雙棧計算表達式：使用雙棧計算表達式： 23 + 2 * 3 ( 2* 3)-1值的過程值的過程148000P(0)=P(0)從操作符從操作符棧彈出棧棧彈出棧頂?shù)捻數(shù)?；操操作符棧為作符棧為空空；操作；操作數(shù)棧中的數(shù)棧中的元素即為元素即為計算結果。計算結果。操操作作數(shù)數(shù)棧棧操操作作符符棧棧使用雙棧計算表達式：使用雙棧計算表達式： 23 + 2 * 3 ( 2* 3)-1值的過程值的過程14800P(0

43、)=P(0)從操作符從操作符棧彈出棧棧彈出棧頂?shù)捻數(shù)?；操操作符棧為作符棧為空空；操作操作數(shù)棧頂元數(shù)棧頂元素即為計素即為計算結果算結果。操操作作數(shù)數(shù)棧棧操操作作符符棧棧注意：表達式正確計算完畢，操作符棧為空；注意：表達式正確計算完畢，操作符棧為空；使用雙棧計算表達式：使用雙棧計算表達式： 23 + 2 * 3 ( 2* 3)-1值的過程值的過程double Evaluate(char *s) Stack opnd;/ 操作數(shù)棧操作數(shù)棧 Stackoptr;/運算符棧運算符棧 optr.Push(0);/ 頭哨兵入棧頭哨兵入棧 while(!optr.Empty() if(當前當前*s為數(shù)字為數(shù)

44、字) /若當前字符為操作數(shù)若當前字符為操作數(shù) ReadNumber(s,opnd);/操作數(shù)進棧操作數(shù)進棧 else / 當前當前*s為操作符為操作符 switch(比較操作符棧頂元素與比較操作符棧頂元素與*s的優(yōu)先級的優(yōu)先級) case : / 操作符棧頂元素優(yōu)先級大操作符棧頂元素優(yōu)先級大 計算表達式的值計算表達式的值,并將計算結果壓入操作數(shù)棧并將計算結果壓入操作數(shù)棧; 中綴形式表達式求值算法中綴形式表達式求值算法3.3 棧的應用：表達式求值棧的應用：表達式求值n比較后綴形式和中綴形式求解表達式值的比較后綴形式和中綴形式求解表達式值的算法可知，后綴形式求值算法比較簡單。算法可知，后綴形式求值

45、算法比較簡單。不過現(xiàn)實中，我們往往遇到的是表達式的不過現(xiàn)實中，我們往往遇到的是表達式的中綴形式，如何用算法將表達式的中綴形中綴形式，如何用算法將表達式的中綴形式轉換為后綴形式呢？式轉換為后綴形式呢？( 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(-), 入操作數(shù)入操作數(shù)退棧。退棧。操操

46、作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *23 + 2 *3 2-100P(*)P(-), *入操作數(shù)入操作數(shù)退棧。退棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)紅圈中的操作數(shù)和操作符看做一個紅圈中的操作數(shù)和操作符看做一個數(shù)（利用后綴表示算）。此時將數(shù)（利用后綴表示算）。此時將3(2*3)轉變成后綴形式轉變成后綴形式: 3 2 3 * 23 + 2 *3 2-100P(+)P(-), +入操作數(shù)入操作數(shù)退棧。退棧。操操作作數(shù)數(shù)棧棧

47、操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)紅圈中的操作數(shù)和操作符看做一個紅圈中的操作數(shù)和操作符看做一個數(shù)（利用后綴表示算）。此時將數(shù)（利用后綴表示算）。此時將2*3(2*3)轉變成后綴形式轉變成后綴形式:2 3 2 3 * *23 + 2 *3 2-100P(0)P(-), -入操作符入操作符棧。棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)紅圈中的操作數(shù)和操作符看做一個紅圈中

48、的操作數(shù)和操作符看做一個數(shù)（利用后綴表示算）。此時將數(shù)（利用后綴表示算）。此時將23+2*3(2*3)轉變成后綴形式轉變成后綴形式:23 2 3 2 3 * * +23 + 2 *3 2-1001入操作數(shù)入操作數(shù)棧。棧。操操作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)紅圈中的操作數(shù)和操作符看做一個紅圈中的操作數(shù)和操作符看做一個數(shù)（利用后綴表示算）。此時將數(shù)（利用后綴表示算）。此時將23+2*3(2*3)轉變成后綴形式轉變成后綴形式:23 2 3 2 3 * * +23 + 2 *3

49、2-100操操作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)紅圈中的操作數(shù)和操作符看做一個紅圈中的操作數(shù)和操作符看做一個數(shù)（利用后綴表示算）。此時將數(shù)（利用后綴表示算）。此時將23+2*3(2*3)轉變成后綴形式轉變成后綴形式:23 2 3 2 3 * * +P(-)P(0), -入操作數(shù)入操作數(shù)棧。棧。23 + 2 *3 2-100操操作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )

50、 1)紅圈中的操作數(shù)和操作符看做一個紅圈中的操作數(shù)和操作符看做一個數(shù)（利用后綴表示算）。此時將數(shù)（利用后綴表示算）。此時將23+2*3(2*3)-1轉變成后綴形式轉變成后綴形式:23 2 3 2 3 * * + 1 -P(0)=P(0), 0出棧，出棧，算法結束，操作數(shù)算法結束，操作數(shù)棧中即為后綴形式。棧中即為后綴形式。23 + 2 *3 2-100操操作作數(shù)數(shù)棧棧操操作作符符棧棧中綴形式轉后綴形式過程演示中綴形式轉后綴形式過程演示 3 *( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)P(0)=P(0), 0出棧，出棧，算法結束，操作數(shù)算法結束，操作數(shù)棧中即為后綴形式。棧

51、中即為后綴形式。思考問題：算法過程中操作數(shù)棧只思考問題：算法過程中操作數(shù)棧只是在記錄信息（操作數(shù)和操作符），是在記錄信息（操作數(shù)和操作符），并沒有信息出棧，那么需要操作數(shù)并沒有信息出棧，那么需要操作數(shù)棧嗎？棧嗎？double Evaluate(char *s) Stack opnd;/ 操作數(shù)棧操作數(shù)棧 Stackoptr;/運算符棧運算符棧 optr.Push(0);/ 頭哨兵入棧頭哨兵入棧 while(!optr.Empty() if(當前當前*s為數(shù)字為數(shù)字) /若當前字符為操作數(shù)若當前字符為操作數(shù) ReadNumber(s,opnd);/操作數(shù)進棧操作數(shù)進棧 else / 當前當前*s為操作符為操作符 switch(比較操作符棧頂元素與比較操作符棧頂元素與*s的優(yōu)先級的優(yōu)先級) case : / 操作符棧頂元素優(yōu)先級大操作符棧頂元素優(yōu)先級大 計算表達式的值計算表達式的值,并將計算結果壓入操作數(shù)棧并將計算結果壓入操作數(shù)棧; 中綴形式轉后綴形式算法中綴形式轉后綴形式算法直接輸出此數(shù)字直接輸出此數(shù)字; /注意