試題二

　　閱讀下列說明和算法，回答問題 1 和問題2，將解答填入答題紙的對應欄內。

　　[說明]

　　算法2-1 是用來檢查文本文件中的圓括號是否匹配。若文件中存在圓括號沒有對應的左括號或者右括號，則給出相應的提示信息，如下所示：文件 提示信息

　　(1+2)

　　abc) 缺少對應左括號：第2 行，第4 列

　　((def)gx)) 缺少對應左括號：第3 行，第10 列

　　(((h)

　　ij)(k

　　(1ml)

　　缺少對應右括號：第5 行，第4 列; 第4

　　行，第1 列

　　在算法2-1 中，stack 為一整數棧。算法中各函數的說明如下表所示：

　　函數名 函數功能

　　push(int i) 將整數i 壓入棧stack 中。

　　pop() stack 的棧頂元素出棧。

　　empty() 判斷stack 棧是否為空.若為空，函數返回1，否則函數返回0。

　　nextch()

　　讀取文本文件中的下一個字符，并返回該字符的ASCII 值，將字符所在的行號以及字 符在行中的位置分別存儲到變量row 和col中，若遇到文件結束符，則將變量EOF 置為true;kind(charch)判斷字符ch 是左括號還是右括號，若是左括號，函數返回1，若是右括號，函數返回2， 若兩者都不是，函數返回0。

　　[算法2-1]

　　將棧stack 置空，置EOF 為false

　　ch←nextch();

　　while(not EOF)

　　k←kind(ch);

　　if (k ==__(1)__)

　　push(__(2)__); push(__(3)__);

　　elseif( k ==__(4)__)

　　if(not empty())

　　pop();pop()：

　　else

　　顯示錯誤信息(缺少對應左括號或右括號);顯示行號row;顯示列號col;

　　endif

　　endif

　　ch←nextch();

　　endwhile

　　if(not empty())

　　顯示錯誤信息(缺少對應左括號或右括號);

　　while(not empty())

　　row←pop(); col←pop();

　　顯示行號row;顯示列號col;

　　endwhile

　　endif

　　為了識別更多種類的括號，對算法2-1 加以改進后得到算法2-2。算法2-2 能夠識別圓括號，方括號和花括號(不同類型的括號不能互相匹配)。改進后，函數kind(charch)的參數及其對應的返回值如下表所示：

　　ch ( ) { } [ ] 其它

　　返回值 1 2 3 4 5 6 0

　　[算法2-2]

　　將棧stack 置空，置EOF 為false

　　ch←nextch();

　　while(not EOF)

　　k←kind(ch);

　　if(k > 0)

　　if(判斷條件1)

　　push(__(5)__)：push(__(6)__);push(__(7)__)：

　　elseif( 判斷條件2 and 判斷條件3 )

　　pop(); pop(); pop();

　　else

　　顯示錯誤信息(缺少對應左括號或右括號);顯示行號row;顯示列號col;

　　endif

　　endif

　　ch←nextch();

　　endwhile

　　if(not empty())

　　顯示錯誤信息(缺少對應左括號或右括號);

　　while(not empty())

　　pop();row←pop();col←pop();

　　顯示行號row;顯示列號col;

　　endwhile

　　endif

　　[問題1]

　　請將[算法2-1]和[算法2-2]中(1)至(7)處補充完整。

　　[問題2]

　　請從下面的選項中選擇相應的判斷邏輯填補[算法2-2]中的“判斷條件廣至“判斷條件3”。注意，若“判斷條件2”的邏輯判斷結果為假，就無需對“判斷條件3”進行判斷。

　　(a)字符是括號 (b)字符是左括號 (c)字符是右括號 (d)棧空 (e)棧不空

　　(f)棧頂元素表示的是與當前字符匹配的左括號

　　(g)棧頂元素表示的是與當前字符匹配的右括號