您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

C++ 運算式求值程式：堆疊類別模板與型別轉換完整解析

編輯：程式設計綜合問答

程式概述

本程式實作一個中序運算式求值器，支援 + - * / 運算子與括號優先序，使用兩個堆疊（運算子堆疊 OPTR、運算元堆疊 OPND）演算法。程式分為三個檔案：主程式 Expression.cpp、堆疊類別宣告 SeqStack.h、堆疊類別實作 SeqStack.cpp。

核心演算法：運算子優先序矩陣

程式核心為 Precede() 函數，使用 7x7 字元矩陣 operates 定義運算子之間的優先關係：

'>'：棧頂運算子優先序高，執行運算 (Pop 並計算)
'<'：當前運算子優先序高，Push 入棧
'='：優先序相等 (如左右括號配對)，Pop 棧頂運算子

運算子對應索引：+ - * / ( ) @ (0~6)，其中 @ 為運算式結束符號。

程式碼結構與關鍵點解析

1. 主程式 Expression.cpp

// 關鍵流程
SeqStack OPTR, OPND;  // 修正：模板參數應為 char 與 double
OPTR.Push('@');
char ch = getchar();
while (ch != '@' || OPTR.Top() != '@') {
    if (isdigit(ch)) {
        OPND.Push(ch - '0');  // 單位數字轉換
        ch = getchar();
    } else {
        char pre_op = OPTR.Top();
        switch (Precede(pre_op, ch)) {
            case '<': OPTR.Push(ch); ch = getchar(); break;
            case '=': OPTR.Pop(); ch = getchar(); break;
            case '>': 
                double b = OPND.Pop();
                double a = OPND.Pop();
                pre_op = OPTR.Pop();
                OPND.Push(Operate(a, pre_op, b));
                break;
        }
    }
}
return OPND.Top();

潛在問題：

SeqStack 模板實例化型別不一致：主程式用 SeqStack OPTR; (預設 int) 存 char，SeqStack OPND; 存 double。建議明確指定 SeqStack、SeqStack。
僅支援單位數字 (0-9)，多位數需修改掃描邏輯 (累積 num = num*10 + (ch-'0'))。
缺少除零檢查 (Operate 中 case '/': return a/b;)。

2. 堆疊類別宣告 SeqStack.h

template   // 建議加入預設大小
class SeqStack {
    T data[MaxSize];
    int top;
public:
    SeqStack();
    void Push(T x);
    T Pop();
    T Top();
    bool Empty();
    bool Full();
};

注意： 原始碼缺少模板參數 MaxSize 定義，需在類別模板參數列加入 int MaxSize 或使用動態陣列 (std::vector)。

3. 堆疊類別實作 SeqStack.cpp

關鍵錯誤： 模板類別的成員函數定義必須放在標頭檔 (或包含 .tpp 內聯檔)，否則連結時會出現 unresolved external symbol 錯誤。原因在於模板實體化發生於編譯期，編譯器需看到完整定義。

修正後的標頭檔完整版 (SeqStack.h)：

#ifndef SEQSTACK_H
#define SEQSTACK_H

#include 
#include 
using namespace std;

template 
class SeqStack {
    T data[MaxSize];
    int top;
public:
    SeqStack() : top(-1) {}
    
    void Push(T x) {
        if (top == MaxSize - 1) {
            cerr << "堆疊上溢" << endl;
            exit(1);
        }
        data[++top] = x;
    }
    
    T Pop() {
        if (top == -1) {
            cerr << "堆疊下溢" << endl;
            exit(1);
        }
        return data[top--];
    }
    
    T Top() const {
        if (top == -1) {
            cerr << "堆疊為空" << endl;
            exit(1);
        }
        return data[top];
    }
    
    bool Empty() const { return top == -1; }
    bool Full() const { return top == MaxSize - 1; }
};

#endif

型別轉換與設計改進建議

1. 字元轉數值

原始碼 OPND.Push(ch - '0') 僅支援 0-9。改進為多位數解析：

double num = 0;
while (isdigit(ch)) {
    num = num * 10 + (ch - '0');
    ch = getchar();
}
OPND.Push(num);

2. 運算子優先序表驅動化

將矩陣改為 std::map 對應優先序等級，邏輯更清晰：

int GetPriority(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '(': return 3;  // 棧內最低
        case ')': return 0;
        case '@': return -1;
        default: return -1;
    }
}
// 比較邏輯：若棧頂優先序 >= 當前優先序 則計算

3. 使用標準庫替代自訂堆疊

生產代碼建議直接使用 std::stack，減少錯誤並提升可讀性：

#include 
std::stack OPTR;
std::stack OPND;

4. 錯誤處理現代化

將 exit(1) 改為拋出例外 (throw std::runtime_error)，讓上層決定如何處理。

完整可執行範例 (單一檔案版)

#include 
#include 
#include 
#include 
#include 
using namespace std;

double Operate(double a, char op, double b) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': 
            if (b == 0) throw runtime_error("除零錯誤");
            return a / b;
        default: throw runtime_error("未知運算子");
    }
}

int Priority(char op) {
    static map pri = {{'+',1},{'-',1},{'*',2},{'/',2},{'(',3},{')',0},{'@',-1}};
    return pri[op];
}

double Evaluate() {
    stack OPTR;
    stack OPND;
    OPTR.push('@');
    char ch = cin.get();
    
    while (ch != '@' || OPTR.top() != '@') {
        if (isdigit(ch)) {
            double num = 0;
            while (isdigit(ch)) {
                num = num * 10 + (ch - '0');
                ch = cin.get();
            }
            OPND.push(num);
        } else if (ch == ' ') {
            ch = cin.get();  // 忽略空白
        } else {
            if (Priority(ch) > Priority(OPTR.top())) {
                OPTR.push(ch);
                ch = cin.get();
            } else if (Priority(ch) == Priority(OPTR.top())) {
                if (ch == ')') { OPTR.pop(); ch = cin.get(); }  // 括號配對
                else throw runtime_error("語法錯誤");
            } else {
                char op = OPTR.top(); OPTR.pop();
                double b = OPND.top(); OPND.pop();
                double a = OPND.top(); OPND.pop();
                OPND.push(Operate(a, op, b));
            }
        }
    }
    return OPND.top();
}

int main() {
    cout << "請輸入運算式 (以 @ 結束)，例如: 3+4*2@\n";
    try {
        double result = Evaluate();
        cout << "結果 = " << result << endl;
    } catch (exception& e) {
        cerr << "錯誤: " << e.what() << endl;
    }
    return 0;
}