投稿類別 : 資訊類 篇名 : 作者 : 李信穎 高雄市立高雄高工 資訊科三年級 朱培一 高雄市立高雄高工 資訊科三年級 指導老師 : 莊利吉老師
壹 前言 一 研究動機 在 Excel 中, 使用者可以自行在儲存格輸入公式, 電腦就會根據輸入的資料計算出結果 同樣的程式設計師也可根據邏輯需要在程式中撰寫適當運算式, 程式執行時也會計算出正確答案 不論是哪一種電腦都無法事先預知使用者會輸入的運算式內容, 那電腦究竟是如何了解運算式內涵, 進而計算出結果呢? 本研究即針對此一疑問進行文獻探討, 並撰寫程式模擬 Excel 或 Compiler 內部的運作原理 二 研究目的 1. 了解中序 後序 前序三種運算式及堆疊的意義 2. 如何運用堆疊將中序式轉為後序式 3. 如何運用堆疊計算後序式之值 4. 設計上述運用的演算法並轉為 VB 的視窗應用程式 三 研究方法 ( 一 ) 研究架構 1. 準備期 : 進行文獻探討及建置開發程式所需的環境 2. 演算法設計 : 根據文獻探討結果設計最適合目前程度的演算法 3. 程式設計 : 將上述演算法轉為 VB 程式, 並進行偵錯 4. 問題討論 : 探討程式中各項設計技巧的優劣性 ( 二 ) 研究工具 硬體 : 個人電腦 軟體 :Visual Studio 2008 貳 正文 一 中序 後序與前序式 運算式的表示方式有 3 種, 分別是中序式 (Infix): 運算子在兩個運算元的中間 ; 後序式 (Postfix): 運算子在兩個運算元的後面 ; 前序式 (Prefix): 運算子在兩個運算元前面, 表 1 是三 個運算式的三種表示方式 1
表 1 三個運算式的三種表示方式 中序式 A+B A+B-C A+B*C 後序式 AB+ AB+C- ABC*+ 前序式 +AB -+ABC +A*BC 二 中序式轉為後序式方法 ( 一 ) 加括號法 1. 依運算子的優先順序, 加上所有的括號, 例如中序式 (A+B)*C 變成 ((A+B)*C) 2. 若要轉為後序式則將運算子移到對應的右括號處, 然後去掉所有的括號 若要轉為前序式則將運算子移到對應的左括號處, 然後去掉所有的括號 ( 廖榮貴 王龍發 許正憲 蔡能聰,2007) 圖 1 是其進行步驟示意圖, 表 2 是三個不同中序式分別轉為後序與前序的過程 圖 1 利用加括號轉為後序式過程 表 2 三個不同中序式分別轉為後序與前序的過程 中序式 將中序式加上括號 後序式 前序式 A+B-C ((A+B)-C) AB+C- -+ABC A+B*C (A+(B*C)) ABC*+ +A*BC (A+B)*C ((A+B)*C) AB+C* *+ABC ( 二 ) 堆疊法 堆疊法是在轉換過程中利用堆疊先進後出的特性, 將中序式的括號去除, 並依運算優先 順序重排為後序式的方法 下表 3 是以中序式 A/(B+C)*D 為例, 呈現轉換過程中每一單元 (token) 的處理過程 表 3 中序式 A/(B+C)*D 轉為後序式的過程 Token Stack Postfix A A / / A ( / ( A B / ( A B + / ( + A B C / ( + A B C 2
) / A B C + * * A B C + / D * A B C + / D 空 A B C + / D * 上述的轉換過程可以歸納成如下圖 2 的演算法, 其中較重要參數說明如下 ( 莊利吉,2008): 1. InfixTokenArray() 為中序式單元存放處, 從 1 開始, 例如若中序式等於 123+A*6, 則 TokenArray(1)="123" TokenArray(2)="+" TokenArray(3)="A" TokenArray(4)="*" TokenArray(5)="6" 2. InfixTokenAmount 表示共有多少個中序式單元, 以本例而言等於 5 3. PostfixTokenArray(): 後序式單元存放處, 從 1 開始 4. PostfixTokenAmount: 共有多少個後序式單元 For i As Integer = 1 To InfixTokenAmount ' 逐一取出中序式的每一個單元 Token = InfixTokenArray(i) If Token 是數值常數或變數 Then 直接添加到後序式的單元陣列中 If Token = "(" Then 優先權最高, 放入堆疊 If Token = ")" Then 優先權最低, 將堆疊頂端的單元取出添加到後序式的單元陣列中, 重複上述步驟直到碰到左括號為止 其他運算子, 執行下列動作 1. 若堆疊頂端運算子的優先順序大於等於目前運算子的優先順序則 POP 到後序式單元陣列中, 直到優先順序小於目前運算子或堆疊為空的 2. 將目前運算子加入到堆疊 將堆疊內所剩的運算子移到後序式單元陣列中 圖 2 中序式轉為後序式的演算法 三 後序式的計算步驟 後序式計算步驟是當遇到運算元時先 Push 到堆疊, 碰到運算子時 POP 運算元出來計算, 再將計算結果 Push 回堆疊, 當所有單元 (token) 都處理完畢後, 堆疊頂端元素就是整個運算式的結果, 將其 Pop 出來即可 ( 葉榮木,1999) 下表 4 是後序式 ABC+/D* 的計算過程, 原中序式為 :A/(B+C)*D 3
表 4 後序式 ABC+/D* 的計算過程 Token Stack 說明 A A B A B C A B C + A T1 執行 T1 = B + C, 再將 T1 加入堆疊 / T2 執行 T2 = A / T1, 再將 T2 加入堆疊 D T2 D * T3 執行 T3 = T2 * D, 再將 T3 加入堆疊 空 取出堆疊頂端元素, 也就是 T3 卽為答案 從上述過程中可知後序式的值為 T3, 若將 T3 展開會得到 T3 = T2 * D = ( A / T1 ) * D = ( A / (B + C ) ) * D 運算的順序與原來的中序式是相同的, 證明此一方法是正確的 上述的計算過程可以歸納成如下圖 3 的演算法, 其中較重要參數說明如下 ( 莊利吉,2008): 1. PostfixTokenArray(): 後序式單元存放處, 從 1 開始 2. PostfixTokenAmount: 共有多少個後序式單元 For i As Integer = 1 To PostfixTokenAmount Token = PostfixTokenArray(i) If Token 數值常數或變數 Then Stack.Push(Token) If Token = "+" Then 相加 Stack.Pop(Operand2) : Stack.Pop(Operand1) ExpressionValue = Single.Parse(Operand1) + Single.Parse(Operand2) If Token = "-" Then 相減 Stack.Pop(Operand2) : Stack.Pop(Operand1) ExpressionValue = Single.Parse(Operand1) - Single.Parse(Operand2) If Token = 其他運算子依此類推 Stack.Push(ExpressionValue.ToString) Stack.Pop(Operand1) 圖 3 計算後序式結果的演算法 四 研究成果 ( 一 ) 程式功能與執行畫面 4
1. 程式功能 使用者可以在 TextBox 上輸入運算式, 運算式中可以包含加 (+) 減(-) 乘(*) 除 (/) 取餘數(%) 次方(^), 英文字母的變數名稱與數值常數 使用者可以在變數資料列給訂變數的值, 讓程式計算 本程式提供使用者 3 個按鈕, 代表電腦計算過程中的 3 個主要步驟, 每個步驟的輸出都會呈現在 ListBox 上, 除方便程式偵錯, 也可增進對內部運作原理的了解 2. 執行畫面 使用者輸入運算式 給訂運算式變數之值 圖 4 起始畫面 圖 5 輸入運算式並按下分割中序的按鈕 圖 6 按下轉為後序的按鈕 圖 7 按下計算後序的按鈕 5
( 二 ) 程式解析 整個程式的中心在下列 3 個副程式, 程式解析請參閱各副程式中的註解 1. SplitInfixToken(ByVal Infix As String, ByRef InfixTokenList As ListBox) 功能 : 將中序式分解為一個個單元 (Token), 存於 InfixTokenList 中 假設中序式只有正確運算子 : 加 (+) 減(-) 乘(*) 除(/) 取餘數(%) 次方(^), 英文字母的變數名稱與數值常數參數說明 Infix:String 中序式字串, 例如 123+A^B InfixTokenList:ListBox 中序式單元存放處, 結果如圖 5 2. InfixToPostfix(ByVal InfixTokenList As ListBox, ByRef PostfixTokenList As ListBox) 功能 : 將中序式轉為後序式參數說明 : InfixTokenList:ListBox 中序式單元存放處, 例如圖 5 PostfixTokenList:ListBox 後序式單元存放處, 例如圖 6 3. EvalPostfix(ByVal PostfixTokenList As ListBox, ByVal DataList As TextBox) As Single 功能 : 計算後序式的結果參數說明 : PostfixTokenList:ListBox 後序式單元存放處, 例如圖 6 DataList:TextBox 各個變數的對應值, 例如圖 7 傳回值 : 計算結果 原始程式如下圖 8: Public Class Form1 Function count(byval a As Integer, ByVal b As Integer, ByVal c As String) If c = "+" Then Return a + b If c = "-" Then Return a - b If c = "*" Then Return a * b If c = "/" Then Return a / b If c = "%" Then Return a Mod b If c = "^" Then Return a ^ b Return False Private Function Priority(ByVal OP As String) As Integer ' 功能 : 訂定運算子優先順序 ' 傳回值 : 運算子優先順序, 最低為 1 If OP = "(" Then Return 1 If OP = "+" Or OP = "-" Then Return 2 If OP = "%" Then Return 3 If OP = "*" Or OP = "/" Then Return 4 If OP = "^" Then Return 5 If OP = ")" Then Return 6 6
Return 7 ' 變數或數字 Private Sub SplitInfixToken(ByVal Infix As String, ByRef InfixTokenList As ListBox) ' 功能 : 將中序式分解為一個個單元 (Token), 存於 InfixTokenList 中 ' 假設中序式只有正確運算子 : 加 (+) 減(-) 乘(*) 除(/) 取餘數(%) 次方(^), 英文字母的變數名稱與數值常數 ' 參數說明 'Infix:String 中序式字串 'InfixTokenList:ListBox 中序式單元存放處 Dim temp As String = String.Empty InfixTokenList.Items.Clear() For i As Integer = 0 To Infix.Length - 1 ' 將各項取出 If Priority(Infix(i)) <= 6 Then ' 判斷是否為運算符號 If temp.length <> 0 Then InfixTokenList.Items.Add(temp) : temp = String.Empty InfixTokenList.Items.Add(Infix(i)) temp &= Infix(i) If temp.length <> 0 Then InfixTokenList.Items.Add(temp) End Sub Private Sub InfixToPostfix(ByVal InfixTokenList As ListBox, ByRef PostfixTokenList As ListBox) ' 功能 : 將中序式轉為後序式 ' 參數說明 : ' InfixTokenList:ListBox 中序式單元存放處 ' PostfixTokenList:ListBox 後序式單元存放處 PostfixTokenList.Items.Clear() Dim temp As New ListBox ' 儲存運算符號 Dim temp1 As String = String.Empty ' 存放傳回的值 For i As Integer = 0 To InfixTokenList.Items.Count - 1 ' 將各項目取出 If InfixTokenList.Items.Item(i) = "(" Then ' 如果是 "(" 直接 Push Push(temp, "(") If InfixTokenList.Items.Item(i) = ")" Then ' 如果是 ")"Pop 到出現 "(" 為止 GetTop(temp, temp1) Do While temp1 <> "(" Pop(temp, temp1) PostfixTokenList.Items.Add(temp1) GetTop(temp, temp1) Loop Pop(temp, temp1) If Priority(InfixTokenList.Items.Item(i)) <= 6 Then ' 判斷是否為運算符號 If IsStacEmpty(temp) Then Push(temp, InfixTokenList.Items.Item(i)) GetTop(temp, temp1) If Priority(InfixTokenList.Items.Item(i)) <= Priority(temp1) Then ' 判斷運算符號優先順序 Do Until Priority(InfixTokenList.Items.Item(i)) > Priority(temp1) Or IsStacEmpty(temp) ' 如果要 Push 進去的運算符號優先順序大於堆疊中的優先順序將堆疊項目依序 Pop 出來 Pop(temp, temp1) PostfixTokenList.Items.Add(temp1) GetTop(temp, temp1) Loop Push(temp, InfixTokenList.Items.Item(i)) Push(temp, InfixTokenList.Items.Item(i)) ' 為變數 7
PostfixTokenList.Items.Add(InfixTokenList.Items.Item(i)) Do Until IsStacEmpty(temp) = True ' 將 temp 堆疊中的項目 Push 到 PostfixTokenList 堆疊中直到 temp 為空 Pop(temp, temp1) PostfixTokenList.Items.Add(temp1) Loop ' 將結果顯示在 TextBox2 TextBox2.Text = String.Empty For i As Integer = 0 To PostfixTokenList.Items.Count - 1 TextBox2.Text &= PostfixTokenList.Items.Item(i) End Sub Private Function EvalPostfix(ByVal PostfixTokenList As ListBox, ByVal DataList As TextBox) As Single ' 功能 : 計算後序式的結果 ' 參數說明 : 'PostfixTokenList:ListBox 後序式單元存放處 'DataList:TextBox 各個變數的對應值 Dim temp(postfixtokenlist.items.count - 1) As String ' 存 PostfixTokenList 的 item Dim test As New ListBox ' 最後計算答案用的 PostfixTokenList.Items.CopyTo(temp, 0) ' 將之前紀錄後序式的結果複製到 temp 陣列 For i As Integer = 0 To temp.length - 1 ' 將所有陣列的值取出 If Not IsNumeric(temp(i)) AndAlso Priority(temp(i)) = 7 Then ' 判斷是否為變數 ' 將變數取代為數值 For j As Integer = 0 To DataList.Lines.Length - 1 Dim test2() As String = DataList.Lines(j).Split(",") If temp(i) = test2(0) Then temp(i) = test2(1) : Exit For For i As Integer = 0 To temp.length - 1 ' 將 temp 陣列取出 If Priority(temp(i)) <= 6 Then ' 判斷是否為運算符號 ' 取出前兩個數值做運算 Dim data2 As Integer = Integer.Parse(test.Items.Item(test.Items.Count - 1)) test.items.removeat(test.items.count - 1) Dim data1 As Integer = Integer.Parse(test.Items.Item(test.Items.Count - 1)) test.items.removeat(test.items.count - 1) test.items.add(count(data1, data2, temp(i))) test.items.add(temp(i)) ' 將結果顯示在 TextBox3 TextBox3.Text = test.items.item(0) Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click SplitInfixToken(TextBox1.Text, ListBox1) End Sub Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click InfixToPostfix(ListBox1, ListBox2) End Sub Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click EvalPostfix(ListBox2, TextBox4) End Sub End Class 圖 8 原始程式碼 8
參 結論 一 問題與討論 ( 一 ) 如何模擬堆疊 利用 ListBox 物件的特性, 來模擬堆疊, 使用者可以清楚的看到堆疊中目前內含的元素, 並撰寫一些副程式, 來完整模擬出堆疊的功能 以下為模擬堆疊的副程式 : Private Function Push(ByRef lststack As ListBox, ByVal NewItem As String) As Boolean ' 功能 : 加入一個新元素 (NewItem) 到堆疊 (lststack) 頂端, 成功時傳回 True lststack.items.insert(0, NewItem) : Return True 圖 9 堆疊的 Push ( 增加元素到堆疊中 ) Private Function Pop(ByRef lststack As ListBox, ByRef Item As String) As Boolean ' 功能 : 刪除堆疊 (lststack) 頂端元素並由參數 (Item) 帶回 成功時傳回 True If IsStacEmpty(lstStack) Then Return False Item = lststack.items.item(0) lststack.items.removeat(0) Return True 圖 10 堆疊的 Pop ( 自堆疊中取出元素 ) Private Function GetTop(ByVal lststack As ListBox, ByRef Item As String) As Boolean ' 功能 : 讀取但未刪除堆疊 (lststack) 頂端元素並由參數 (Item) 帶回 成功時傳回 True If IsStacEmpty(lstStack) Then Return False Item = lststack.items.item(0) Return True 圖 11 取得堆疊最上層的原素 Private Function IsStacEmpty(ByVal lststack As ListBox) As Boolean ' 功能 : 若堆疊是空的則傳回 True If lststack.items.count = 0 Then Return True Return False 圖 12 取得堆疊是否為空 ( 二 ) 如何處理運算式中的變數 要運算的時候遇到變數, 就將變數取代為使用者所輸入的數值 For i As Integer = 0 To temp.length - 1 ' 將所有陣列的值取出 If Not IsNumeric(temp(i)) AndAlso Priority(temp(i)) = 7 Then ' 判斷是否為變數 For j As Integer = 0 To DataList.Lines.Length - 1 ' 將變數取代為數值 9
Dim test2() As String = DataList.Lines(j).Split(",") If temp(i) = test2(0) Then temp(i) = test2(1) : Exit For 圖 13 取代的程式碼 二 未來研究建議 1. 探討是否可以以前序式的方式計算出正確的答案 2. 將程式擴充, 加入更多的運算子及 Excel 函式給使用者使用 3. 將本程式轉換成網頁版, 可當資料結構課程的輔助教具 肆 引註資料 1. 莊利吉 (2008) 適合高職學生的資料結構 擷取日期 2011 年 9 月 25 日, 擷取自莊利吉教學網站 : http://lichi.ksvs.kh.edu.tw 2. 葉榮木 (1999) 資料結構使用 Visual Basic 台北市: 松崗 3. 廖榮貴 王龍發 許正憲 蔡能聰 (2007) 資料結構與演算法- 使用 VB.NET VB2005 台北市 : 文魁 10