後綴表達式求值與驗證：堆疊演算法、動態監測與 MFC 實作

問題定義

輸入後綴表達式 (逆波蘭表示法)，僅含整數與四則運算，輸出計算結果。

範例：

• 2 3 * 1 - → 5 (即 2*3-1)
• 1 2 + 5 4 * 3 - * 6 - → 45 (即 (1+2)*(5*4-3)-6)

演算法原理

後綴表達式無需括號，適合電腦處理。採用堆疊：

1. 左至右掃描。
2. 遇運算元 → 入堆疊。
3. 遇運算子 → 彈出兩個運算元計算 → 結果入堆疊。
4. 掃描結束，堆疊剩單一元素即為結果。

創新點：動態驗證機制

在計算過程中即時檢測錯誤，遇錯誤立即中止並報錯，避免程式異常終止。驗證層次：

1. 字符合法性：check() 檢查是否含非法字符。
2. 運算元/運算子數量關係：合法後綴表達式滿足「運算元個數 = 運算子個數 + 1」。
3. 計算過程堆疊深度：遇運算子時堆疊至少需有 2 元素，否則表達式錯誤 (如 1 +)。
4. 最終堆疊狀態：計算結束堆疊必剩 1 元素，且入/出堆疊次數符合特定公式。

此「動態監視」思想可推廣至任意表達式解析器。

類別設計：CStack

class CStack {
private:
  int num[100];     // 堆疊資料
  int sum;          // 當前元素數
  int flag;         // 非法操作標記 (1=合法, 0=非法)
  int popcount;     // POP 次數
  int pushcount;    // PUSH 次數
public:
  CStack();
  int getflag();    // 取得非法標記
  int getsum();     // 取得當前元素數
  void setflag(int);
  int getcount();   // 依 push/pop 計算運算元個數
  void Pop();       // 出堆疊
  void Push(int);   // 入堆疊
  int Top();        // 取堆疊頂
  virtual ~CStack();
};

關鍵實作

CStack::CStack() {
  for(int i=0;i<=50;i++) num[i]=0;
  sum=0; flag=1; popcount=0; pushcount=0;
}
void CStack::Pop() {
  if(sum>=1) { num[sum]=0; sum--; popcount++; }
  else flag=0; // 非法：堆疊空仍嘗試彈出
}
void CStack::Push(int temp) {
  sum++; num[sum]=temp; pushcount++;
}
int CStack::Top() {
  if(sum>=1) return num[sum];
  else { flag=0; return 0; } // 非法：空堆疊取頂
}
int CStack::getcount() {
  return (pushcount*2 - popcount)/2; // 推導公式
}

主程式邏輯：OnCalculate()

void CB05031126Dlg::OnCalculate() {
  UpdateData(TRUE);
  m_expression.TrimLeft(); m_expression.TrimRight();
  m_expression = trimblank(m_expression); // 移除多餘空格
  CStack s;
  int i=0, k=0;
  int ntemp, ntemp1, ntemp2, result;

  if(check(m_expression)==1) { // 字符合法性
    while(i < m_expression.GetLength() && s.getflag()!=0) {
      if(m_expression[i]=='+' || m_expression[i]=='-' ||
         m_expression[i]=='*' || m_expression[i]=='/') {
        // 運算子處理
        if(m_expression[i]=='+') { // 加法
          ntemp1 = s.Top(); s.Pop();
          ntemp2 = s.Top(); s.Pop();
          ntemp = ntemp1 + ntemp2;
          s.Push(ntemp);
        }
        else if(m_expression[i]=='-') { // 減法：注意順序
          ntemp1 = s.Top(); s.Pop();
          ntemp2 = s.Top(); s.Pop();
          ntemp = ntemp2 - ntemp1;
          s.Push(ntemp);
        }
        else if(m_expression[i]=='*') { // 乘法
          ntemp1 = s.Top(); s.Pop();
          ntemp2 = s.Top(); s.Pop();
          ntemp = ntemp1 * ntemp2;
          s.Push(ntemp);
        }
        else if(m_expression[i]=='/') { // 除法：檢查除零
          ntemp1 = s.Top(); s.Pop();
          ntemp2 = s.Top(); s.Pop();
          if(ntemp1 != 0) { ntemp = ntemp2 / ntemp1; s.Push(ntemp); }
          else s.setflag(0);
        }
        k += 2; i = k + 1; // 簡化索引推進 (實際應解析 token)
      }
      else {
        // 解析多位數運算元
        ntemp = m_expression[i] - '0';
        k = i + 1;
        while(k < m_expression.GetLength() &&
              m_expression[k]!=' ' && m_expression[k]!='+' &&
              m_expression[k]!='-' && m_expression[k]!='*' &&
              m_expression[k]!='/') {
          k++;
        }
        for(int j=i+1; j