Code written by me, post generated by ChatGPT. Hope it'll help!

解法

這題可以用 Two Stack (Shunting Yard) 演算法。

使用兩個 stack：

values stack     存數值
operators stack  存運算子

演算法流程

逐個讀 token：

1. 數字

直接 push 到 values stack。

vals.push(number)

2. 左括號 (

直接 push 到 operator stack。

opers.push('(')

3. 右括號 )

持續計算直到遇到 (：

while(opers.top() != '(')
    reduce()

pop '('

4. 運算子

假設新運算子為 op。

如果 stack top 的運算子優先度 大於等於 新運算子，就先計算：

while(
    opers 不空 &&
    opers.top() != '(' &&
    precedence(top) >= precedence(op)
)
    reduce()

然後 push 新運算子。

reduce 操作

從 stack 取出兩個數字與一個 operator：

rhs = vals.top()
lhs = vals.top()
op  = opers.top()

計算：

lhs op rhs

再 push 回 values stack。

最後處理

當整行 token 讀完後：

while(opers 不空)
    reduce()

stack 中剩下的值就是答案。

時間複雜度

每個 token 最多 push / pop 一次：

O(n)

範例

輸入

2 + ( 3 + 4 ) * 5

輸出

37

計算流程示意

讀到 2

vals:  [2]
opers: []

讀到 +

vals:  [2]
opers: [+]

讀到 (

vals:  [2]
opers: [+, (]

讀到 3

vals:  [2, 3]
opers: [+, (]

讀到 +

vals:  [2, 3]
opers: [+, (, +]

讀到 4

vals:  [2, 3, 4]
opers: [+, (, +]

讀到 )

開始計算直到遇到 (：

3 + 4 = 7

vals:  [2, 7]
opers: [+]

讀到 *

vals:  [2, 7]
opers: [+, *]

讀到 5

vals:  [2, 7, 5]
opers: [+, *]

最後清空 operator stack：

7 * 5 = 35
2 + 35 = 37

結果：

37

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

ll doOper(ll a, ll b, char op){
    switch(op){
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        case '%': return a % b;
    }
    throw runtime_error("Invalid op");
}

int main(){

    stack<ll> vals;
    stack<char> opers;

    auto reduce = [&](){
        char op = opers.top(); opers.pop();
        ll rhs = vals.top(); vals.pop();
        ll lhs = vals.top(); vals.pop();
        vals.push(doOper(lhs, rhs, op));
    };

    string line;

    while(getline(cin, line)){

        vals = stack<ll>();
        opers = stack<char>();

        stringstream ss(line);
        string token;

        while(ss >> token){

            char c = token[0];

            if(isdigit(c)){
                vals.push(stoll(token));
            }

            else if(c == '('){
                opers.push('(');
            }

            else if(c == ')'){
                while(opers.top() != '(')
                    reduce();
                opers.pop();
            }

            else{

                int prec = getPrec(c);

                while(!opers.empty() &&
                      opers.top() != '(' &&
                      getPrec(opers.top()) >= prec)
                    reduce();

                opers.push(c);
            }
        }

        while(!opers.empty())
            reduce();

        cout << vals.top() << "\n";
    }
}

 

這題本質是 expression parsing。

常見O(n)解法：

Two Stack / Shunting Yard （此題推）
Recursive Descent
Pratt Parsing
LR Parsing