高考申論題
111年
[資訊處理] 資料結構
第 一 題
以下是一中序運算式（Infix expression）轉換（Convert）成後序運算式（Postfix expression）的演算法
operstk = the empty stack;
while(not end of input){
symb = next input character;
if(symb is an operand)
add symb to the postfix string;
else{
while(!empty(operstk) && precedence(stacktop(operstk),symb)){
topsymb = pop(operstk);
add topsymb to the postfix string;
} /*end while*/
if (empty(operstk) || symb != ‘)’)
push(operstk, symb);
else
topsymb = pop(operstk);
} /*end else*/
} /*end while*/
while(!empty(operstk)){
topsymb = pop(operstk);
add topsymb to the postfix string;
} /*end while*/
其中資料結構：
“operstk”：用來儲存運算子的堆疊（Stack）；
“stacktop(operstk)”：表示 top 指標所指堆疊 operstk 的運算子；
程序（Procedures）或函數（Functions）：
“empty(operstk)”：檢查堆疊 operstk 是否為空的布林函數；
“pop(operstk)”：從堆疊 operstk 中取出一運算子；
“push(operstk, symb)”：將運算子 symb 存入堆疊 operstk；
“precedence(op1,op2)”：布林函數，定義在一沒有左右括弧的中序運算式中，op1 運算子出現在 op2 運算子的左邊時，當 op1 運算子優先順序不低於 op2 運算子，則設定成 TRUE，否則為 FALSE。例如，我們給定 precedence(‘*’, ‘+’)=TRUE ， precedence(‘+’, ‘+’)=TRUE ， precedence(‘+’, ‘*’)=FALSE，為了處理運算式左右括弧，設定下列的 precedence:
precedence(‘(’, op) = FALSE /*op 為任一運算子*/
precedence(op, ‘(’) = FALSE /*op 為除’)’外的任一運算子*/
precedence(op, ‘)’) = TRUE /*op 為除’(’外的任一運算子*/
precedence(‘)’, op) = undefined /*op 為任一運算子*/
以中序運算式(2+3)*4 為例，執行上述演算法，依處理每一個運算子或運算元時，輸出 postfix string 及 operstk 內容為何（“eos”表示 end of string）？（25 分）
📝 此題為申論題
思路引導 VIP
這是一題典型的「中序轉後序」演算法追蹤題。關鍵在於徹底理解題目給定的 precedence(op1, op2) 函數行為。這與一般的運算子優先權概念稍有不同，它定義的是「何時該從堆疊中彈出（pop）運算子」。
- 辨識規則：當
precedence(stacktop, symb)為 TRUE 時，表示堆疊頂端的運算子優先權較高或相等，應先輸出。對於括弧，題目特別定義：左括弧(進入堆疊時永遠不彈出其他符號（precedence 為 FALSE），而遇到右括弧)時，會不斷彈出堆疊內容直到遇到左括弧為止。
🤖
AI 詳解
AI 專屬家教
【考點分析】 本題考察資料結構中「堆疊（Stack）」的應用，特別是中序（Infix）轉後序（Postfix）的經典演算法。核心爭點在於括弧在堆疊中的處理機制以及優先權函數的邏輯判定。 【理論/法規依據】
▼ 還有更多解析內容