982 C++ 第三次程式作業

作業目標：

1. 練習繼承架構的設計

作業說明：

1. 請以 C++ 語言撰寫一程式計算如下列 infix 表示之 + - * / 運算式

   3 + 4.1 * 5 / 6 - 7.0 * 8 + 9 =

   + - * / = 各個運算子 (operator) 的優先順序如下表所示：

   

   上例中運算順序如下圖所示：

   

   運算結果為 -40.583

2. 程式中請定義兩個堆疊 (Stack) 來輔助計算結果，一個堆疊用來放運算子 (operator), 另一個用來放運算元 (operand)

3. 上面範例的運算流程如下所示：

   
   current input is 3
   push 3 to operand stack
   current input is +
   precedence of + is higher than NULL (top of operator stack)
   push + to operator stack
   current input is 4.1
   push 4.1 to operand stack
   current input is *
   precedene of * is higher than + (top of operator stack)
   push * to operator stack
   current input is 5
   push 5 to operand stack
   current input is /
   precedence of / is the same as * (top of operator stack)
   pop operator stack as opr (*)
   pop operand stack as opnd2 (5)
   pop operand stack as opnd1 (4.1)
   evaluate opnd1 opr opnd2 ie. 4.1 * 5 = 20.5
   push 20.5 to operand stack
   current intput is still /
   precedence of / is higher than + (top of operator stack)
   push / to operator stack
   current input is 6
   push 6 to operand stack
   current input is -
   precedence of - is lower than / (top of operator stack)
   pop operator stack as opr (/)
   pop operand stack as opnd2 (6)
   pop operand stack as opnd1 (20.5)
   evaluate 20.5 / 6 = 3.417
   push 3.417 to operand stack
   current input is still -
   precedence of - is the same as + (top of operator stack)
   pop operator stack as opr (+)
   pop operand stack as opnd2 (3.417)
   pop operand stack as opnd1 (3)
   evaluate 3 + 3.417 = 6.417
   push 6.417 to operand stack
   current input is still -
   precedence of - is higher than NULL (top of operator stack)
   push - to operator stack
   current input is 7.0
   push 7.0 to operand stack
   current input is *
   precedence of * is higher than - (top of operator stack)
   push * to operator stack
   current input is 8
   push 8 to operand stack
   current input is +
   precedence of + is lower than * (top of operator stack)
   pop operator stack to opr (*)
   pop operand stack to opnd2 (8)
   pop operand stack to opnd1 (7.0)
   evaluate 7.0 * 8 = 56
   push 56 to operand stack
   current input is still + 
   precedence of + is the same as - (top of operator stack)
   pop operator stack to opr (-)
   pop operand stack to opnd2 (56)
   pop operand stack to opnd1 (6.417)
   evaluate 6.417 - 56 = -49.583
   push -49.583 to operand stack
   current input is still +
   precedence of + is higher than NULL (top of operator stack)
   push + to operator stack
   current input is 9
   push 9 to operand stack
   current input is =
   precedence of = is lower than + (top of operator stack)
   pop operator stack to opr (+)
   pop operand stack to opnd2 (9)
   pop operand stack to opnd1 (-49.583)
   evaluate -49.583 + 9 = -40.583
   push -40.583 to operand stack
   current input is still =
   precedence of = is higher than NULL (top of operator stack)
   push = to operator stack
   end of input
   pop operator to opr (=)
   pop operand stack to opnd1 (-40.583)
   evaluate -40.583 =
   Are operand stack and operator stack empty?
   return -40.583
   

4. 如下圖所示，我們可以設計一個程式， 其中運算子堆疊及運算元堆疊為獨立的兩種物件：
   

   然而兩個堆疊的基本運作方式是一樣的，如果用串列來實作堆疊的話， 簡單的介面規格如下：

   class CStack { struct CNode { CNode(double oprnd) : operand(oprnd), next(NULL) {}; double operand; CNode *next; }; public: CStack(); ~CStack(); void push(double oprnd); double pop(); BOOL IsEmpty(); void clear(); private: CNode *m_top; };
   因此邏輯幾乎一樣的程式碼會出現兩次，這樣子設計出來的軟體很容易有維護上的問題。

5. 請使用繼承及群集/組合的技術來改良上述版本， 但是什麼情況下該用繼承，什麼情況下該用群集/組合呢?

   請在書面報告中說明下列幾種類別架構的設計，各自的設計目標為何? 請以 C++ 語法寫下各組類別的定義? 何者滿足介面之要求? 還有沒有別種設計方法?

   

   ---

   

   ---

   

6. 範例執行程式

7. 此程式採用文字界面，由鍵盤或是檔案輸入資料，程式中分析輸入的運算式，一旦出現不允許的格式時會發出錯誤的訊息，
   例如： 3 + * 5 = 或是 3.0 5.0 - 7.0 =

   遇見這樣子的運算式時，程式無法算出正確結果而需要發出錯誤訊息，要處理這種錯誤情況的話，一種方法是等到堆疊上出現無法處理的狀況時程式才發出錯誤訊息，所以上式 3 + * 5 會把 3 和 5, + 和 * 都分別放到堆疊上，然後先做 3 * 5 = 15, 把 15 再放到堆疊上，然後由堆疊上得到 '+' 運算子，可是此時運算元堆疊上只剩下一個運算元，所以無法處理 '+' 號這個二元 (binary) 運算子，程式於此時會發出錯誤訊息。

   在我們的作業中，為了簡化你的程式，你可以完全不處理等號以外的一元 (unary) 運算子，如此可以歸納出一個簡單的法則，就是運算元和運算子會交錯地出現，如此程式可以很簡單地偵測出錯誤狀況，不過如果你要處理一元運算子的話，法則就會比較複雜了。

8. 請修改 Operand 堆疊，利用作業一裡所寫的 BigInteger 類別來完成一個 可以計算大整數運算式的應用程式

9. 由上面的提示中你可以發現有許多可以加強你的程式功能的地方，例如處理一元的正負號，或是加入處理小括號的功能等等，如果你在作業中加入額外的功能的話，記得在說明中及 demo 時強調一下，一定會有加分的。

程式撰寫注意事項

1. 變數及函式名稱請用有意義的英文或是縮寫
2. 請不要用全域變數
3. 常數請以 const 或是 enum 宣告

作業繳交注意事項

1. 請於時限內 (99/06/07 24:00前) 上傳程式檔案 (逾時無法上傳, 請預先測試你的帳號與密碼), 上傳網頁
   
   
2. 請注意雖然作業的題目不是很困難, 可是由於你對於 iostream, fstream 不適很熟悉, 所以你還是應該早點開始做, 避免先看到同學的程式, 由於程式功能已經有很多的限制了, 所以如果你先看過別人的程式, 你很難寫出和別人不一樣的東西...

3. 請編輯一個 report.txt (或是 report.doc) 檔案, 說明你的演算法高階的模型, 概念上的作法, 資料結構, 你所完成的功能, 測試結果,... 以及對於此次作業各個部份的問題? (提出問題時請盡量整理你所知道的, 與你所懷疑的, 你所不認同的..., 如此會比空洞的 "我不懂 xxx?", "yyy 是什麼?" 要容易回答, 相對的你也比較容易得到你想要的答案)
   
   
4. 請畫一張圖代表此演算法高階概念上的作法 (其實可以用 JohnsonBaugh 書中某幾張說明圖片)
   
   
5. report.txt (或是 report.doc) 中請說明你的心得 (心得可以包括你覺得你獲得的觀念, 你 debug 時發現的問題, 你 debug 的心得, 作業的感想, 你自己覺得比較好或是比較特別的設計...)