C++ 實習期末線上測試:

template Stack and Exception 設計

時間: 150分鐘 (請注意時間, 於 12:05 前上傳)

首先你會看到一個完整可以執行的範例應用程式，這個程式可以計算正整數的 infix expression，例如輸入 2 * 3 + ( 5 - 4 ) 的計算結果為 7，順便印出 postfix 的算式表示法 2 3 * 5 4 - +，在計算的過程中需要使用兩個堆疊，一個存放整數運算元 (範圍在 0 ~ 999 之間)，另一個存放運算子 +, -, *, /, (, )

這個線上測試由簡單到繁瑣分為四個階段， 希望你完成的程式簡單描述如下 (這四個程式是分開來的，希望你完成一個之後就上傳，在上傳網頁的 "完成度敘述" 標示是那一個程式):

1. 在上面範例應用程式裡的兩個堆疊，除了資料的型態不一樣之外，所有的介面都是一樣的，請運用 template 的語法，撰寫一個 Stack 類別，可以讓編譯器作出所需要的 Stack<int> 和 Stack<char> 兩個類別，並符合指定的基本測試
   
2. 由於在上面的範例應用程式中完全沒有處理不正常的狀況，包括輸入運算式的語法錯誤或是計算演算法的錯誤，請針對上題所寫的 template Stack 來處理可能發生的錯誤，主要包括 push 時記憶體配置的不足，pop 已經空了的堆疊這兩種狀況，top 介面在堆疊是空的時我們定義會回傳 eos (end of stack) 常數，所以不算是錯誤，請在發生錯誤時，產生 std::out_of_range 例外物件，並在基本測試中捕捉所產生的錯誤，列印錯誤的原因即可
   
3. 由於堆疊的錯誤有兩種，我們又有兩種堆疊，有的時候其實應用程式需要針對不同的例外狀況來處理，如果發生例外時，只產生 std::out_of_range 例外，程式就沒有辦法簡單地區分這四種錯誤了。因為例外的捕捉是以類別為標的，所以請繼承 std::out_of_range 類別成為 push_out_of_range 以及 pop_out_of_range 兩個類別，為了進一步分辨是哪一種堆疊產生的例外，請把這兩個 push_out_of_range 和 pop_out_of_range 類別設計成 template，同樣地請在基本測試中捕捉所產生的錯誤，列印錯誤的原因即可
   
4. 最後一個步驟就是修改上面的範例應用程式了，運用前一個步驟產生的 template Stack 和 template Exception 來達成正常的功能和基本的例外處理架構 (同樣地請先列印錯誤的原因即可)

計算正整數的 infix expression 範例應用程式

程式碼

詳細計算方法請參考先前資料結構實習: 中序運算式計算

演算法簡述如下：

1. 遇見正整數就 push 到 operand stack 上
   
2. 遇見運算符號時，比較這個算符和 operator stack 上的算符的優先順序，優先順序低的話，就把 operator stack 上高優先順序的算符 pop 出來計算，把結果 push 到 operand stack 上，直到 operator stack 上的算符優先順序較低為止
   
3. 遇見左邊小括號就 push 到 operator stack 上
   
4. 遇到右邊小括耗時，就把 operator stack 上的算符 pop 出來計算，把結果 push 到 operand stack 上，直到 operator stack 上出現左邊小括號為止

1. 請運用 template 的語法，撰寫一個 Stack 類別，可以讓編譯器作出所需要的 Stack<int> 和 Stack<char> 兩個類別

請拷貝上面範例程式中 stack 相關的 push, pop, isEmpty, top 程式

請使用動態記憶體配置，建構元請傳入一個堆疊大小的整數參數

請用 template 語法修改為 template Stack

指定的基本測試如下：iStack 存放整數，cStack 存放字元, 請在建構元中指定大小為 30

    int i;
    for (i=0; i<25; i++)
        iStack.push(i);
    for (i=0; i<25; i++)
    {
        cout << iStack.top() << ' ';
        iStack.pop();
    }
    
    for (i=0; i<25; i++)
        cStack.push(i);
    for (i=0; i<25; i++)
    {
        cout << cStack.top() << ' ';
        cStack.pop();
    }

放在 main() 函式裡，請加入其它需要的程式碼，並且測試上面的 template Stack, 把測試結果貼在上傳網頁的完成度敘述

請壓縮後在 考試作業區 選擇 2015-6-25 Labfinal 上傳

參考答案: test1.cpp, tStack1.h

2. 由於在上面的範例應用程式中完全沒有處理不正常的狀況，包括輸入運算式的語法錯誤或是計算演算法的錯誤，請針對上題所寫的 template Stack 來處理可能發生的錯誤，在發生錯誤時，產生 std::out_of_range 例外物件，並在基本測試中捕捉所產生的錯誤，列印錯誤的原因即可

請在適當地方產生 std::out_of_range 例外物件：包括 push 時記憶體配置的不足，pop 已經空了的堆疊這兩種狀況

請在適當地捕捉所產生的例外物件，列印發生錯誤的原因即可, 請修改基本測試程式, 產生錯誤的狀況進行測試, 把測試結果貼在上傳網頁的完成度敘述

請壓縮後選擇 2015-6-25 Labfinal 上傳

參考答案: test2.cpp, tStack2.h

3. 為了進一步分辨是哪一種堆疊產生的例外，請把這兩個 push_out_of_range 和 pop_out_of_range 類別設計成 template，同樣地請在基本測試中捕捉所產生的錯誤 push_out_of_range<int>, pop_out_of_range<int>, push_out_of_range<char>, pop_out_of_range<char>，列印錯誤的原因即可, 請修改基本測試程式, 產生錯誤的狀況進行測試, 把測試結果貼在上傳網頁的完成度敘述

請壓縮後在 考試作業區 選擇 2015-6-25 Labfinal 上傳

參考答案: test3.cpp, tStack3.h, tExcept3.h

4. 修改上面的範例應用程式了，運用前一個步驟產生的 template Stack 和 template Exception 來達成正常的功能和基本的例外處理架構 (同樣地請先列印錯誤的原因即可, 請修改輸入資料, 以及堆疊的大小, 產生錯誤的狀況進行測試, 把測試結果貼在上傳網頁的完成度敘述)

請壓縮後在 考試作業區 選擇 2015-6-25 Labfinal 上傳

參考答案: infixExpression4.cpp, tStack4.h, tExcept4.h

• 在 CppUnit 或是 Google Test 中都有測試 exception 的部份, 暑假裡有機會請練習, 如果遇見任何問題都可以來討論
  
• 期末考考卷已公佈, 請在考試作業區選擇 "期末考"
  
• 另外如果你進一步去看相關的物件導向書籍, Design Pattern 書籍, 或是嘗試寫 MFC/Qt/Gnome/Java 也歡迎你來討論