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

template Stack and Exception

2015/06/25

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 範例應用程式

程式碼

輸入資料 輸出
2 * 3 + ( 5 - 4 ) 2 3 * 5 4 - +
7
2 * 4 - 2 * 3 / ( 6 - 2 * 2 ) 2 4 * 2 3 * 6 2 2 * - / -
5
1 - 2 * 3 / ( 6 - 5 * ( 1 + 2 * 2 - 3 ) % 7 ) 1 2 3 * 6 5 1 2 2 * + 3 - * 7 % - / -
-1
23 * 312 + ( 525 - 411 ) 23 312 * 525 411 - +
7290

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

演算法簡述如下:

  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

不論你做到什麼階段, 請將你的 project (只需保留 .cpp, .h, .sln 以及 .vcxproj 檔案即可; 刪除掉 .suo, .sdf, .filters, .users, debug\ 資料匣, 以及 ipch\ 資料匣下的所有內容) 以 zip/rar/7zip 程式將整個資料匣壓縮起來, 在考試作業區選擇 2015-6-25 Labfinal 上傳
  • 在 CppUnit 或是 Google Test 中都有測試 exception 的部份, 暑假裡有機會請練習, 如果遇見任何問題都可以來討論
  • 期末考考卷已公佈, 請在考試作業區選擇 "期末考"
  • 另外如果你進一步去看相關的物件導向書籍, Design Pattern 書籍, 或是嘗試寫 MFC/Qt/Gnome/Java 也歡迎你來討論

C++ 物件導向程式設計課程 首頁

製作日期: 06/25/2015 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 電機資訊學院 資訊工程學系 Lagoon