投稿類別 : 資訊類篇名 : 堆疊應用 : 電腦如何求出運算式的值作者 : 李信穎高雄市立高雄高工資訊科三年級朱培一高雄市立高雄高工資訊科三年級指導老師 : 莊利吉老師

Size: px

Start display at page:

Download "投稿類別 : 資訊類篇名 : 堆疊應用 : 電腦如何求出運算式的值作者 : 李信穎高雄市立高雄高工資訊科三年級朱培一高雄市立高雄高工資訊科三年級指導老師 : 莊利吉老師"

孔萧
6 years ago
Views:

1 投稿類別 : 資訊類篇名 : 作者 : 李信穎高雄市立高雄高工資訊科三年級朱培一高雄市立高雄高工資訊科三年級指導老師 : 莊利吉老師

2 壹前言一研究動機在 Excel 中, 使用者可以自行在儲存格輸入公式, 電腦就會根據輸入的資料計算出結果同樣的程式設計師也可根據邏輯需要在程式中撰寫適當運算式, 程式執行時也會計算出正確答案不論是哪一種電腦都無法事先預知使用者會輸入的運算式內容, 那電腦究竟是如何了解運算式內涵, 進而計算出結果呢? 本研究即針對此一疑問進行文獻探討, 並撰寫程式模擬 Excel 或 Compiler 內部的運作原理二研究目的 1. 了解中序後序前序三種運算式及堆疊的意義 2. 如何運用堆疊將中序式轉為後序式 3. 如何運用堆疊計算後序式之值 4. 設計上述運用的演算法並轉為 VB 的視窗應用程式三研究方法 ( 一 ) 研究架構 1. 準備期 : 進行文獻探討及建置開發程式所需的環境 2. 演算法設計 : 根據文獻探討結果設計最適合目前程度的演算法 3. 程式設計 : 將上述演算法轉為 VB 程式, 並進行偵錯 4. 問題討論 : 探討程式中各項設計技巧的優劣性 ( 二 ) 研究工具硬體 : 個人電腦軟體 :Visual Studio 2008 貳正文一中序後序與前序式運算式的表示方式有 3 種, 分別是中序式 (Infix): 運算子在兩個運算元的中間 ; 後序式 (Postfix): 運算子在兩個運算元的後面 ; 前序式 (Prefix): 運算子在兩個運算元前面, 表 1 是三個運算式的三種表示方式 1

3 表 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

4 ) / 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

5 表 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

6 1. 程式功能使用者可以在 TextBox 上輸入運算式, 運算式中可以包含加 (+) 減(-) 乘(*) 除 (/) 取餘數(%) 次方(^), 英文字母的變數名稱與數值常數使用者可以在變數資料列給訂變數的值, 讓程式計算本程式提供使用者 3 個按鈕, 代表電腦計算過程中的 3 個主要步驟, 每個步驟的輸出都會呈現在 ListBox 上, 除方便程式偵錯, 也可增進對內部運作原理的了解 2. 執行畫面使用者輸入運算式給訂運算式變數之值圖 4 起始畫面圖 5 輸入運算式並按下分割中序的按鈕圖 6 按下轉為後序的按鈕圖 7 按下計算後序的按鈕 5

7 ( 二 ) 程式解析整個程式的中心在下列 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

8 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

9 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

10 參結論一問題與討論 ( 一 ) 如何模擬堆疊利用 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

11 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 日, 擷取自莊利吉教學網站 : 2. 葉榮木 (1999) 資料結構使用 Visual Basic 台北市: 松崗 3. 廖榮貴王龍發許正憲蔡能聰 (2007) 資料結構與演算法- 使用 VB.NET VB2005 台北市 : 文魁 10

Microsoft PowerPoint - VB14.ppt

Microsoft PowerPoint - VB14.ppt VB 列表盒 LISTBOX 應用資科系林偉川執行畫面 1 2 1 重要屬性 LISTBOX 物件 (VB6) 新增至 LISTBOX 物件中 ADDITEM 自 LISTBOX 物件中刪除選取物件 REMOVEITEM 自 LISTBOX 物件中取出選取物件 ListIndex 顯示 LISTBOX 物件中紀錄個數 Listcount 3 LISTBOX 物件 (VB.NET) 重要屬性新增至

投稿類別 : 資訊類 篇名 : 堆疊應用 : 電腦如何求出運算式的值 作者 : 李信穎 高雄市立高雄高工 資訊科三年級 朱培一 高雄市立高雄高工 資訊科三年級 指導老師 : 莊利吉老師

投稿類別 : 資訊類篇名 : 堆疊應用 : 電腦如何求出運算式的值作者 : 李信穎高雄市立高雄高工資訊科三年級朱培一高雄市立高雄高工資訊科三年級指導老師 : 莊利吉老師