資料結構課程設計：十進制二元運算式樹計算器 C++ 完整代碼審查與除錯指南

程式碼結構概覽

使用者提交完整 C++ 程式碼，實現：

1. 順序堆疊（SqStack）與動態字串（String）基本操作
2. 中綴轉後綴（Convert）演算法
3. 運算式樹建立（CreatBiTree）
4. 遞迴計算樹值（Value）
5. 運算式合法性驗證（JudegExp）
6. 主程式互動介面

關鍵問題與修正建議

1. 堆疊初始化錯誤

// 原始碼錯誤
void InitStack(SqStack *&S) {
    S = (SqStack*)malloc(sizeof(SqStack)); // C 風格，且未初始化 elem 陣列
    S->top = -1;
}
// 修正：C++ 風格，正確分配記憶體
void InitStack(SqStack *&S) {
    S = new SqStack();
    S->elem = new char[Stack_Size]; // 關鍵：分配資料陣列
    S->top = -1;
}

2. 字串結構體記憶體洩漏與淺拷貝

String Convert(String Str) {
    String Output;
    Output.ch = new char(Str.length); // 錯誤：應為 new char[Str.length+1]
    // ...
    return Output; // 返回區域物件，淺拷貝導致雙重釋放
}

建議改用 std::string + std::vector std::stack，消除手動記憶體管理風險。

3. 中綴轉後綴邏輯錯誤

• 逆序掃描但運算元直接輸出，未處理多位數字（如 123 會被拆成 3 2 1）。
• 括號處理邏輯與標準 Shunting-yard 算法不符。
• 建議參考標準演算法重寫，或直接使用 std::stack 實現。

4. 運算式樹建立錯誤

if(!IsOperator(F.ch[i])) { // 操作數
    T = new TNode;
    T->data.optr = F.ch[i]; // 錯誤：操作數應存入 opnd，非 optr
    // ...
}

聯合體 data 需區分 optr（運算子）與 opnd（運算元），建立樹時類型判斷錯誤。

5. 計算函數參數順序錯誤

return Calc(Value(T->lchild), T->data.opnd, Value(T->rchild));
// 應為
return Calc(Value(T->lchild), T->data.optr, Value(T->rchild));

6. 主函數測試資料硬編碼

S.ch = "1+2+3*7#";
S.length = strlen(S.ch) - 1; // 扣除 #，但未處理多位數

現代化重構建議

#include 
#include 
#include 
#include 
#include 

double evaluate(const std::string& expr) {
    std::stack vals;
    std::stack ops;
    auto precedence = [](char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    };
    auto apply = [&](char op) {
        double b = vals.top(); vals.pop();
        double a = vals.top(); vals.pop();
        switch(op) {
            case '+': vals.push(a+b); break;
            case '-': vals.push(a-b); break;
            case '*': vals.push(a*b); break;
            case '/': vals.push(a/b); break;
        }
    };
    for (size_t i = 0; i < expr.size(); ++i) {
        if (isspace(expr[i])) continue;
        if (isdigit(expr[i])) {
            double num = 0;
            while (i < expr.size() && isdigit(expr[i])) num = num*10 + (expr[i++]-'0');
            --i; vals.push(num);
        } else if (expr[i] == '(') {
            ops.push('(');
        } else if (expr[i] == ')') {
            while (ops.top() != '(') apply(ops.top()), ops.pop();
            ops.pop();
        } else if (strchr("+-*/", expr[i])) {
            while (!ops.empty() && precedence(ops.top()) >= precedence(expr[i]))
                apply(ops.top()), ops.pop();
            ops.push(expr[i]);
        }
    }
    while (!ops.empty()) apply(ops.top()), ops.pop();
    return vals.top();
}

int main() {
    std::string line;
    while (std::getline(std::cin, line)) {
        if (line.empty()) continue;
        try {
            std::cout << evaluate(line) << '\n';
        } catch (...) {
            std::cerr << "Invalid expression\n";
        }
    }
}

除錯步驟

1. 在 Convert、CreatBiTree、Value 關鍵點設斷點，觀察中間資料結構。
2. 針對 1+2*3、(1+2)*3、12+34 等典型用例單步追蹤。
3. 使用 _CrtDumpMemoryLeaks() 檢測記憶體洩漏。

最佳回答建議：「調試下看看呢，是不是代碼不正確」——確實，建議先跑通現代化版本，再回頭重構原始教學代碼。