C++ 堆疊/二元樹教學專案完整原始碼：從資料結構實作到實際問題求解

專案需求

• 實作堆疊或二元樹資料結構。
• 應用該結構解決一個實際問題。
• 提供完整可編譯原始碼。

方案：堆疊實作 + 後綴運算式求值（經典應用）

後綴表示法（逆波蘭）無需括號即可唯一表達運算優先序，利用堆疊單掃描即可求值，展示資料結構實用價值。

完整原始碼 (C++17)

// stack.h
#pragma once
#include 
#include 

template 
class Stack {
    std::vector data;
public:
    void push(const T& v) { data.push_back(v); }
    T pop() {
        if (data.empty()) throw std::out_of_range("Stack empty");
        T v = data.back(); data.pop_back(); return v;
    }
    T top() const {
        if (data.empty()) throw std::out_of_range("Stack empty");
        return data.back();
    }
    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

// main.cpp
#include 
#include 
#include 
#include 
#include "stack.h"

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

double apply(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return b != 0 ? a / b : throw std::runtime_error("Divide by zero");
    }
    return 0;
}

// 中綴轉後綴 (Shunting-yard 簡化版)
std::string toPostfix(const std::string& infix) {
    std::ostringstream out;
    Stack ops;
    for (size_t i = 0; i < infix.size(); ++i) {
        char c = infix[i];
        if (std::isspace(c)) continue;
        if (std::isdigit(c) || c == '.') {
            out << c;
            while (i + 1 < infix.size() && (std::isdigit(infix[i+1]) || infix[i+1] == '.')) 
                out << infix[++i];
            out << ' ';
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') out << ops.pop() << ' ';
            if (!ops.empty()) ops.pop(); // 移除 '('
        } else if (strchr("+-*/", c)) {
            while (!ops.empty() && precedence(ops.top()) >= precedence(c)) 
                out << ops.pop() << ' ';
            ops.push(c);
        }
    }
    while (!ops.empty()) out << ops.pop() << ' ';
    return out.str();
}

// 後綴求值
double evalPostfix(const std::string& postfix) {
    Stack st;
    std::istringstream in(postfix);
    std::string token;
    while (in >> token) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            double b = st.pop(), a = st.pop();
            st.push(apply(a, b, token[0]));
        } else {
            st.push(std::stod(token));
        }
    }
    return st.pop();
}

int main() {
    std::string expr;
    std::cout << "輸入中綴運算式 (如 3+4*2/(1-5)): ";
    std::getline(std::cin, expr);
    try {
        std::string postfix = toPostfix(expr);
        std::cout << "後綴: " << postfix << "\n";
        double result = evalPostfix(postfix);
        std::cout << "結果: " << result << "\n";
    } catch (const std::exception& e) {
        std::cerr << "錯誤: " << e.what() << "\n";
    }
    return 0;
}

編譯與執行

g++ -std=c++17 main.cpp -o calc
./calc
# 輸入: 3+4*2/(1-5)
# 輸出: 後綴: 3 4 2 * 1 5 - / + 
# 結果: 1

延伸：二元樹應用 — 運算式樹

同樣的中綴轉換過程中，可改建構運算式樹（葉節點為運算元、內節點為運算子），支援：

• 多次求值（變數代入不同值）。
• 符號微分/化簡。
• 產生組合語言/位元碼。

掌握堆疊與樹的轉換，即掌握編譯器前端核心技術。