第四題 計算機程式

    使用者設計一個可以自動計算一串數學運算式的計算機，運算式中包括
由數字、括號及運算符號組成，各別說明如下：
  1. 數字：可能是整數或浮點數，例如；13.456 或 32，且數值不為負。
  2. 運算符號："＋ , - , * , / , ^"，其中 "＋,-,*,/" 分別代表算術運算的加 , 減 , 乘 , 除 ，"^" 代表次方運算 ，例如 3^2運算結果會是 9。
  3. 左、右括號：例如 (24.5+5)*6.3。
  4. 運算優先權：第一是括號 "()"，第二是 "^,*,/"，第三是 "+,-"
    5. 舉例來說，若輸入 "12+(3.4+5*6.2)/3.2"，則結果會顯示 22.75。
輸入說明

輸入一串包含 "＋,-,*,/,^" 與 "()" 及數字組合的算式，並以 Return 作結束。

輸出說明

輸出答案為整個運算式的結果，以「四捨五入」取到小數點後第二位，
如果輸入運算式 不符合一般數學的表示式，則輸出 "N/A"。
本題無需考慮運算結果發生溢位的問題。

範例
輸入 輸出
12 + (3.4 + 5 * 6.2) / 3.2 22.75
5.6 * (6.4 ^ 3 - 8) 1423.21
(1234 + 5678 N / A

分析：
此題是本年度 6 題當中最難一題，應最後做答，時間不足應優先放棄。
本題是資料結構 堆疊 入門題，使用後序式較容易演算。
因此本程式解法，必須具備 2 種演算法，分別為：
1) 中序式轉後序式。
2) 計算後序式。

在解說演算法前，先說明本題與數理相關的不同點。
  1. ) 指數運算，若無括號，則以左結合還是右結合? (可自由設定)
    2. 左結合： 3 ^ 2 ^ 4 = ( 3 ^ 2 ) ^ 4 = 9 ^ 4 = 6561
    右結合： 3 ^ 2 ^ 4 = 3 ^ ( 2 ^ 4 ) = 3 ^ 16 = 43046721
    很明顯，本題題意是左結合。
  2. ) 指數與乘法運算子，誰優先運算，在數學上是以指數優先。
    3. 5 * 2 ^ 3 = 5 * ( 2 ^ 3 ) = 5 * 8 = 40
    但依本題題意，兩者優先度相同，因此變成如下，
    5 * 2 ^ 3 = ( 5 * 2 ) ^ 3 = 10 ^ 3 = 1000
    本題以數學角度來看是錯誤的式子，但個人覺得命題者是故意改變運算優先度，其理由是避免解題者，利用語言系統執行 "字串命令運算"，如此一來就不用高難度的資料結構堆疊演算了。

下面是 VB.net 的 "字串命令運算"
   Dim sc, cmd As Object, d As Double
   sc = CreateObject("ScriptControl")
   sc.Language = "VBScript"
   cmd = sc.Modules.Add("Module1")
   d = cmd.Eval(str) "這一行指令就可執行運算式了
   Label1.Text = (CInt(d * CintN) / CintN).ToString()
   sc = Nothing
  1. 中序式轉後序式演算法
    2. 堆疊法:
    1. 中序轉後序
      2. 在中序轉換成後序的過程，我們將以下列的步驟運作：
      ISP(堆疊內優先權):In Stack Priority
      ICP(輸入優先權):In Coming Priority
      1. 由左至右讀入單一字元。
      2. 輸入為運算元，則直接輸出。
      3. "("在堆疊中比任何運算子都小，不過如果在堆疊外，卻比任何運算子優先權都高。
      4. ISP>=ICP則將堆疊的運算子pop出來，否則就push到堆疊內。
      5. 若遇")"，彈出堆疊內的運算子直到彈出一個"("為止。
      其中運算子堆疊的規則是：
      • 碰到左括號"("，一律 push。
      • 碰到右括號")"，則一直 pop 輸出至後序式，直到遇見左括號，一同抵銷。
      • 運算子在堆疊中只能優先序大的壓優先序小的，也就是當運算子在進入堆疊之前和堆疊頂端的運算子比較優先序。如果外面的優先序大，則 push。否則就一直做 pop，直到遇見優先序較小的運算子或堆疊為空。 值得注意的是:左括號在堆疊中優先序最小，亦即，任何運算子都可以壓它。
  2. 計算後序式演算法
    • 自左而右讀取每一個字。
    • 如果是運算元(例如"5),直接 push 進 stack。
      如果是運算子(例如 +),自 stack 中 pop 出兩個運算元進行運算之後將結果 push 進 stack。
    • 最後 stack 中只剩下一個元素,那就是最後結果。
    • 如果發生 stack 已經空了,但是還需要 pop 運算元的情況,表示運算式寫錯了。
    • 如果最後 stack 不只剩下一個元素,表示運算式寫錯了。

    請寫一個程式接受使用者輸入 Infix(中置式) 算術運算式字串,算出結果並且印出來。
    此一字串中間沒有空白。
    有 "+" , "-" , "*" , "/" , "^" 五個整數運算子。(含括號)
    每一個整數運算元都是1位數。

    程式測試

    承上題，運算元為整數。

    程式測試