LeetCode Basic Calculator II：中綴轉後綴表達式求值完整實現

問題描述

計算包含 + - * / 和非負整數的表達式字符串，整數除法向零截斷。不使用 eval。如 "3+2*2" = 7。

兩步走策略：中綴 → 後綴 → 求值

1. **中轉後**：掃描字符串，數字直接輸出，運算符按優先級進棧。
2. **後綴求值**：掃描後綴表達式，數字進棧，運算符彈出兩數計算再入棧。

中綴轉後綴核心邏輯

string toPostfix(string s) {
    string post; stack op;
    for (int i = 0; i < s.size(); ) {
        if (isdigit(s[i])) {
            while (i < s.size() && isdigit(s[i])) post += s[i++];
            post += '#'; // 數字分隔符
        } else if (s[i] == ' ') { ++i; }
        else {
            char c = s[i++];
            int prec = (c=='*'||c=='/') ? 2 : 1;
            while (!op.empty() && precedence(op.top()) >= prec)
                post += op.top(), op.pop();
            op.push(c);
        }
    }
    while (!op.empty()) post += op.top(), op.pop();
    return post;
}

後綴求值

int evalPostfix(string post) {
    stack st; int num = 0;
    for (int i = 0; i < post.size(); ) {
        if (isdigit(post[i])) {
            num = 0;
            while (isdigit(post[i])) num = num*10 + (post[i++]-'0');
            st.push(num);
        } else if (post[i] == '#') { ++i; }
        else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            switch (post[i++]) {
                case '+': st.push(a+b); break;
                case '-': st.push(a-b); break;
                case '*': st.push(a*b); break;
                case '/': st.push(a/b); break; // C++ 整除向零截斷
            }
        }
    }
    return st.top();
}

單棧一掃描優化（無需後綴串）

維護兩個棧：數值棧、運算符棧。掃描中綴時，遇運算符先計算棧頂優先級 ≥ 當前的運算，再入棧。最後清空運算符棧。代碼更緊湊，原理相同。

複雜度

時間 O(n)，空間 O(n)（棧深度）。n 為字符串長度。