第三章棧和隊(duì)列(1)

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

2、“”,“”,“(”,“)”四種四種字符。字符。輸出輸出 每組輸入數(shù)據(jù)的輸出占一行，如果該字符串中所含的括號(hào)是配對(duì)的，則每組輸入數(shù)據(jù)的輸出占一行，如果該字符串中所含的括號(hào)是配對(duì)的，則輸出輸出Yes,如果不配對(duì)則輸出如果不配對(duì)則輸出No。樣例輸入樣例輸入 3 () () ()樣例輸出樣例輸出 No No Yes問題一：括號(hào)匹配問題一：括號(hào)匹配問題二：問題二：火車進(jìn)出棧問題火車進(jìn)出棧問題 判斷火車的出棧順序是否合法u/problem?id=1363編號(hào)為1,2,n的n輛火車依次進(jìn)站，給定一個(gè)n的排列， 判斷是否是合法的出站順序？車站BA1, 2, 3, 4, 55, 4,

3、3, 2, 1進(jìn)站進(jìn)站出站出站問題三：計(jì)算表達(dá)式的值問題三：計(jì)算表達(dá)式的值求形如：A+B*(C-D)-E/F 表達(dá)式的值。78+99*56*(100-66)/3-100=?問題四：迷宮問題問題四：迷宮問題入口入口出口出口 從路口找一條路到出口。從路口找一條路到出口。 從路口找一條最短路到出口。從路口找一條最短路到出口。問題四：問題四：n后問題后問題在在 n n 行行 n n 列的列的國際象棋棋盤上，若兩個(gè)皇后位于同一行、國際象棋棋盤上，若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，則稱為它們?yōu)榛ハ喙簟Ｍ涣?、同一?duì)角線上，則稱為它們?yōu)榛ハ喙?。n n 皇后皇后問題是指問題是指找到這找到這 n

4、n 個(gè)皇后的互不攻擊的布局個(gè)皇后的互不攻擊的布局。0 1 2 3 01233.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端topbottom將將a a0 0放入棧放入棧3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一

5、端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端將將a a1 1放入棧放入棧topbottoma03.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端將將a a2 2放入棧放入棧a1topbottoma03.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插

6、入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端將將a a3 3放入棧放入棧a1a2topbottoma03.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端a1a3a2topbottoma03.1 棧棧n棧（棧（stack）可以定義為只允許在表

7、的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端a1a3a2topbottoma0將將a a4 4放到元素放到元素a2a2的下面的下面只能在棧頂（只能在棧頂（top所示所示位置后面）添加元素。位置后面）添加元素。3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端

8、u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端a1a3a2topbottoma0將將a a2 2從棧中刪除從棧中刪除只能刪除棧頂元素，只能刪除棧頂元素，即即top所示位置的元素。所示位置的元素。3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端a1a3a2topbottoma0將將a a3 3從棧中刪除從棧中刪除3.1 棧棧n

9、棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端a1a2topbottoma0將將a a2 2從棧中刪除從棧中刪除3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪

10、除的另一端和刪除的另一端a1topbottoma0將將a a1 1從棧中刪除從棧中刪除3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端topbottoma0將將a a0 0從棧中刪除從棧中刪除3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和

11、刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端topbottom進(jìn)棧：進(jìn)棧：將元素加到棧頂。將元素加到棧頂。退棧：退棧：將棧頂元素刪除。將棧頂元素刪除。退棧進(jìn)棧3.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端topbottom回顧添加，刪除元素的順序：回顧添加，刪除元素的順序：添加：添加：a

12、0，a1，a2，a3刪除：刪除：a3，a2，a1，a03.1 棧棧n棧（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端topbottom回顧添加，刪除元素的順序回顧添加，刪除元素的順序發(fā)現(xiàn)：將元素按照發(fā)現(xiàn)：將元素按照a0，a1，a2，a3的順序進(jìn)棧，讓所有元素的順序進(jìn)棧，讓所有元素出棧時(shí)出棧時(shí)a3最先出棧，其次時(shí)最先出棧，其次時(shí)a2，a1，最后是，最后是a0。3.1 棧棧n棧

13、（棧（stack）可以定義為只允許在表的末端）可以定義為只允許在表的末端進(jìn)行插入和刪除的線性表。進(jìn)行插入和刪除的線性表。u棧頂（棧頂（top）：允許插入和刪）：允許插入和刪除的一端除的一端u棧底（棧底（bottom）：不允許插入）：不允許插入和刪除的另一端和刪除的另一端topbottom棧的典型特點(diǎn)是：后進(jìn)先出棧的典型特點(diǎn)是：后進(jìn)先出（LIFO，Last In First Out）3.2 棧的實(shí)現(xiàn)方式棧的實(shí)現(xiàn)方式n順序棧 (Array-based Stack)n鏈?zhǔn)綏＃↙inked Stack）u使用向量實(shí)現(xiàn)，本質(zhì)上是順序表的簡化版u用單鏈表方式存儲(chǔ)，其中指針的方向是從棧頂向下鏈接3.2.1

14、順序棧順序棧n順序棧 (Array-based Stack)u使用向量實(shí)現(xiàn)，本質(zhì)上是順序表的簡化版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進(jìn)棧進(jìn)棧0 1 2 3 4 5 6 7 8 9 maxSize-1top =1data:a1a2進(jìn)棧進(jìn)棧a2a3進(jìn)棧進(jìn)棧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 鏈?zhǔn)綏鏈?zhǔn)綏＃↙inked S

17、tack）u用單鏈表方式存儲(chǔ)，其中指針的方向是從棧頂向下鏈接top棧頂棧頂鏈?zhǔn)綏５臈ｍ斣阪湵淼谋眍^鏈?zhǔn)綏５臈ｍ斣阪湵淼谋眍^。因此，新結(jié)點(diǎn)的插入和棧。因此，新結(jié)點(diǎn)的插入和棧頂結(jié)點(diǎn)的刪除都在鏈表的表頭，即棧頂進(jìn)行。頂結(jié)點(diǎn)的刪除都在鏈表的表頭，即棧頂進(jìn)行。top?？諚？誸opa1topa1topa1a3a2a2a1進(jìn)棧進(jìn)棧a2進(jìn)棧進(jìn)棧a3進(jìn)棧進(jìn)棧a3退棧退棧topa1a2a2退棧退棧topa1a2退棧退棧top基于不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧基于不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧top?？諚？誸opa1a1a1a3a2a2a1進(jìn)棧進(jìn)棧a2進(jìn)棧進(jìn)棧a3進(jìn)棧進(jìn)棧toptopa3退棧退棧a1a2topa2退棧退棧top

18、a1a1退棧退棧top基于帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)?；趲ь^結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧3.2.2鏈?zhǔn)綏ｆ準(zhǔn)綏emplate struct StackNode T data; StackNode *next; StackNode(T d = 0, StackNode *suc = NULL):next(suc),data(d) ;結(jié)點(diǎn)定義：結(jié)點(diǎn)定義：3.2.2 鏈?zhǔn)綏ｆ準(zhǔn)綏emplate 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 棧的應(yīng)用：括號(hào)匹配棧的

20、應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。(a*(b-c)-d)-e/(f+g)-h)*i*j-(k+m)/n對(duì)于一個(gè)括號(hào)正確匹配的式子對(duì)于一個(gè)括號(hào)正確匹配的式子，從左向右掃描它時(shí)，每一，從左向右掃描它時(shí)，每一個(gè)右括號(hào)與最近遇到的一個(gè)相同類型的左括號(hào)相匹配。個(gè)右括號(hào)與最近遇到的一個(gè)相同類型的左括號(hào)相匹配。簡單的例子：簡單的例子：()左右括號(hào)配對(duì)次序不正確左右括號(hào)配對(duì)次序不正確()右括號(hào)多于左括號(hào)右括號(hào)多于左括號(hào)(左括號(hào)多于右括號(hào)左括號(hào)多于右括號(hào)()左右括號(hào)匹配正確左右括號(hào)匹配正確3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否

21、匹配。編程檢查下面式子中的括號(hào)是否匹配。簡單的例子：簡單的例子：()左右括號(hào)配對(duì)次序不正確左右括號(hào)配對(duì)次序不正確()右括號(hào)多于左括號(hào)右括號(hào)多于左括號(hào)(左括號(hào)多于右括號(hào)左括號(hào)多于右括號(hào)()左右括號(hào)匹配正確左右括號(hào)匹配正確)( () )( () 3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到左括號(hào)（左括號(hào)（”(”，“”,”），讓它們進(jìn)棧，讓它們進(jìn)棧。3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)

22、是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到左括號(hào)（左括號(hào)（”(”，“”,”），讓它們進(jìn)棧，讓它們進(jìn)棧。(3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到左括號(hào)（左括號(hào)（”(”，“”,”），讓它們進(jìn)棧，讓它們進(jìn)棧。(3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇

23、到右括號(hào)（右括號(hào)（”)”，“”,”）判斷它與棧頂括號(hào)是否匹配，判斷它與棧頂括號(hào)是否匹配，如果匹配，棧頂元素退棧，否如果匹配，棧頂元素退棧，否則，匹配失敗，退出則，匹配失敗，退出。( 3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top(從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到左括號(hào)（左括號(hào)（”(”，“”,”），讓它們進(jìn)棧，讓它們進(jìn)棧。3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列

24、，從左到右掃描括號(hào)序列，遇到遇到右括號(hào)（右括號(hào)（”)”，“”,”）判斷它與棧頂括號(hào)是否匹配，判斷它與棧頂括號(hào)是否匹配，如果匹配，棧頂元素退棧，否如果匹配，棧頂元素退棧，否則，匹配失敗，退出則，匹配失敗，退出。(3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到右括號(hào)（右括號(hào)（”)”，“”,”）判斷它與棧頂括號(hào)是否匹配，判斷它與棧頂括號(hào)是否匹配，如果匹配，棧頂元素退棧，否如果匹配，棧頂元素退棧，否則，匹配失敗，退出則，匹配失敗，退出。(3.3 棧的應(yīng)用：

25、括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到右括號(hào)（右括號(hào)（”)”，“”,”）判斷它與棧頂括號(hào)是否匹配，判斷它與棧頂括號(hào)是否匹配，如果匹配，棧頂元素退棧，否如果匹配，棧頂元素退棧，否則，匹配失敗，退出則，匹配失敗，退出。(3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )( ()top從左到右掃描括號(hào)序列，從左到右掃描括號(hào)序列，遇到遇到右括號(hào)（右括號(hào)（”)”，“”,”）判斷它與棧頂括號(hào)是

26、否匹配，判斷它與棧頂括號(hào)是否匹配，如果匹配，棧頂元素退棧，否如果匹配，棧頂元素退棧，否則，匹配失敗，退出則，匹配失敗，退出。(3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配n編程檢查下面式子中的括號(hào)是否匹配。編程檢查下面式子中的括號(hào)是否匹配。( ( ) )上面括號(hào)的展示的括號(hào)匹配過程，考慮了情況上面括號(hào)的展示的括號(hào)匹配過程，考慮了情況，在括號(hào)匹配的過程中如何體現(xiàn)出來呢？在括號(hào)匹配的過程中如何體現(xiàn)出來呢？()左右括號(hào)配對(duì)次序不正確左右括號(hào)配對(duì)次序不正確()右括號(hào)多于左括號(hào)右括號(hào)多于左括號(hào)(左括號(hào)多于右括號(hào)左括號(hào)多于右括號(hào)()左右括號(hào)匹配正確左右括號(hào)匹配正確3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹

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

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

29、直接退出號(hào)多于左括號(hào)，匹配失敗，直接退出；5.字符串循環(huán)掃描結(jié)束時(shí)，若堆棧非空（即堆棧尚有某種類字符串循環(huán)掃描結(jié)束時(shí)，若堆棧非空（即堆棧尚有某種類型的左括號(hào)），則說明左括號(hào)多于右括號(hào)，匹配失敗型的左括號(hào)），則說明左括號(hào)多于右括號(hào)，匹配失?。?.正常結(jié)束則括號(hào)匹配正確。正常結(jié)束則括號(hào)匹配正確。3.3 棧的應(yīng)用：括號(hào)匹配棧的應(yīng)用：括號(hào)匹配class BracketMatcherprivate: const char* exp; / 括號(hào)串括號(hào)串 char terminator; /括號(hào)串的結(jié)束標(biāo)記括號(hào)串的結(jié)束標(biāo)記public: BracketMatcher(const char* ep,char

30、term):exp(ep),terminator(term) bool BracketMatching();括號(hào)匹配類括號(hào)匹配類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í)行括號(hào)匹配執(zhí)行括號(hào)匹配3.3棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值表達(dá)式是由操作數(shù)（亦稱運(yùn)算對(duì)象）、操作表達(dá)式是由操作數(shù)（亦稱運(yùn)算對(duì)象）、操作符（亦稱運(yùn)算符）和分界符組成的。符（亦稱運(yùn)算符）和分界符組成的。u算術(shù)表達(dá)式有算術(shù)表達(dá)式有3中表示方法：中表示方法：u中綴中綴(infix)(infix)表示表示 ，如如 A+BA+B；u前綴前綴(prefix)(prefix)表示表示 ，如如 +A

32、B+AB；u后綴后綴(postfix)(postfix)表示表示 ，如如 AB+AB+；3.3 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n平時(shí)常見的表達(dá)式均為表達(dá)式的中綴形式平時(shí)常見的表達(dá)式均為表達(dá)式的中綴形式23 + 2 * 3 ( 2* 3)0!+1-(2-(3!-4)5)*67-8+9可以將表達(dá)式的中綴形式轉(zhuǎn)換為表達(dá)式的前綴和后綴形式。可以將表達(dá)式的中綴形式轉(zhuǎn)換為表達(dá)式的前綴和后綴形式。3.3 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n中綴形式轉(zhuǎn)換為前綴形式中綴形式轉(zhuǎn)換為前綴形式( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )u先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序通統(tǒng)加上括號(hào)，再把

33、操先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序通統(tǒng)加上括號(hào)，再把操作符前移到左括號(hào)前并以就近移動(dòng)為原則，最后將所有括作符前移到左括號(hào)前并以就近移動(dòng)為原則，最后將所有括號(hào)消去。號(hào)消去。 +23 * 2 3 * 2 323 + 2 * 3 ( 2* 3)( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) )23 2 3 2 3*+ u先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序加上括號(hào)，再把操作符后先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序加上括號(hào)，再把操作符后移到右括號(hào)的后面并以就近移動(dòng)為原則，最后將所有括號(hào)消移到右括號(hào)的后面并以就近移動(dòng)為原則，最后將所有括號(hào)消去。去。3.3 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n中綴形式轉(zhuǎn)換為

34、后綴形式中綴形式轉(zhuǎn)換為后綴形式23 + 2 * 3 ( 2* 3)3.3 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n基于前綴形式計(jì)算表達(dá)式的值基于前綴形式計(jì)算表達(dá)式的值n基于中綴形式計(jì)算表達(dá)式的值基于中綴形式計(jì)算表達(dá)式的值n基于后綴形式計(jì)算表達(dá)式的值基于后綴形式計(jì)算表達(dá)式的值3.3 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n基于后綴形式計(jì)算表達(dá)式的值基于后綴形式計(jì)算表達(dá)式的值23 2 3 2 3*+ 23 2 3 2 3*+ 23 2 3 6*+ 計(jì)算計(jì)算2*323 2 729*+ 計(jì)算計(jì)算3623 1458+ 計(jì)算計(jì)算2*7291481 計(jì)算計(jì)算23+1458思路：掃描表達(dá)思路：掃描表達(dá)式后

35、綴表示，遇式后綴表示，遇到運(yùn)算符，使用到運(yùn)算符，使用它前面的兩個(gè)操它前面的兩個(gè)操作數(shù)做運(yùn)算。作數(shù)做運(yùn)算?；诤缶Y形式計(jì)算表達(dá)式的值基于后綴形式計(jì)算表達(dá)式的值如何避免重復(fù)掃如何避免重復(fù)掃描表達(dá)式？描表達(dá)式？記錄掃描過的操記錄掃描過的操作數(shù)作數(shù)23 2323*+ 遇到遇到*運(yùn)算符，取出保存的最后兩個(gè)操作數(shù)運(yùn)算符，取出保存的最后兩個(gè)操作數(shù)2和和3，計(jì)算，計(jì)算2*3 并將結(jié)果保存。并將結(jié)果保存。23 2 3 6遇到遇到運(yùn)算符，取出保存的最后兩個(gè)操作數(shù)運(yùn)算符，取出保存的最后兩個(gè)操作數(shù)3和和6，計(jì)算，計(jì)算36 并將結(jié)果保存。并將結(jié)果保存。23 2323*+ 23 2 729遇到遇到*運(yùn)算符，取出保存的最后

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

37、算法書寫方便需要用一個(gè)表達(dá)式結(jié)束的標(biāo)記，掃描到結(jié)束標(biāo)記時(shí)，表達(dá)式計(jì)算過程結(jié)束。描到結(jié)束標(biāo)記時(shí)，表達(dá)式計(jì)算過程結(jié)束。RpnEvaluate(expr) / 假定假定RPN表達(dá)式表達(dá)式expr語法正確語法正確 定義用于存放操作數(shù)的棧定義用于存放操作數(shù)的棧S; while (expr 尚未掃描完畢尚未掃描完畢) 讀入讀入expr的下一個(gè)元素的下一個(gè)元素x; if(x是操作數(shù)是操作數(shù)) 將將x壓入棧壓入棧S; else 從棧從棧S中彈出運(yùn)算符中彈出運(yùn)算符x所需數(shù)目操作數(shù)所需數(shù)目操作數(shù) 對(duì)彈出的操作數(shù)實(shí)施對(duì)彈出的操作數(shù)實(shí)施x運(yùn)算，并將運(yùn)算運(yùn)算，并將運(yùn)算 結(jié)果壓入結(jié)果壓入S; 返回棧頂返回棧頂后綴表達(dá)式求

38、值算法后綴表達(dá)式求值算法3.3 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n基于中綴形式計(jì)算表達(dá)式的值基于中綴形式計(jì)算表達(dá)式的值23 + 2 * 3 ( 2* 3)-1中綴表達(dá)式：中綴表達(dá)式： 23 + 2 * 3 ( 2* 3)-1值的計(jì)算過程值的計(jì)算過程23 + 2 *3 ( 2*3 ) -123 + 2 *3 6-123 + 2 *729-123 + 1458 -11481-11480u優(yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)高的先計(jì)算；u優(yōu)先級(jí)相同的自左優(yōu)先級(jí)相同的自左向右計(jì)算；向右計(jì)算；u當(dāng)使用括號(hào)時(shí)從最當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開始計(jì)算。內(nèi)層括號(hào)開始計(jì)算。表達(dá)式計(jì)算遵循規(guī)則：表達(dá)式計(jì)算遵循規(guī)則：中綴表

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

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

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

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

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

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

45、算法比較簡單。不過現(xiàn)實(shí)中，我們往往遇到的是表達(dá)式的不過現(xiàn)實(shí)中，我們往往遇到的是表達(dá)式的中綴形式，如何用算法將表達(dá)式的中綴形中綴形式，如何用算法將表達(dá)式的中綴形式轉(zhuǎn)換為后綴形式呢？式轉(zhuǎn)換為后綴形式呢？( 23 + ( 2 * ( 3 ( 2* 3 ) ) ) ) 1)23 2 3 2 3*+1- 中綴形式轉(zhuǎn)后綴形式過程演示中綴形式轉(zhuǎn)后綴形式過程演示23 + 2 *3 ( 2*3) -1進(jìn)棧進(jìn)棧P(+)P(#)+進(jìn)棧進(jìn)棧00進(jìn)棧進(jìn)棧P(*)P(+)*進(jìn)棧進(jìn)棧進(jìn)棧進(jìn)棧P()P(*)進(jìn)棧進(jìn)棧P()P()(進(jìn)棧進(jìn)棧進(jìn)棧進(jìn)棧P(*)P()*進(jìn)棧進(jìn)棧進(jìn)棧進(jìn)棧P()P(-), 入操作數(shù)入操作數(shù)退棧。退棧。操操

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

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

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

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

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

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