952 C++ 第三次程式作業

2007/05/22

作業目標：

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 宣告