Notes

解法一、遞迴

🔹 大式子拆成小式子

依照優先度由低而高、由後往前的順序處理
+, - → *, /, % → (, )

當一個式子沒有任何運算符號 (代表他只剩數字)，返回數值
當一個式子運算完成，返回數值

由於括號優先度高 (遞迴中要最後處理)
因此需要一個變數 layer 紀錄當前位置括號的層數
層數 = 0 時，才能處理 +, -, *, /, %

當最左最右都是刮號才去括號

遞迴代碼

(begin1 ~ end1 為前半式子，begin2 ~ end2 為後半式子)

int calculate(int begin, int end){
    // find + -
    return calculate(begin1, end1) [op] calculate(begin2, end2);

    // find * / %
    return calculate(begin1, end1) [op] calculate(begin2, end2);

    // find ( )
    return calculate(begin1, end2);

    // only find number
    return num;
}

12 * 34 * 56 + 78
+ 明顯需要最後處理
於是由後往前找到 + 後
將問題拆成 [12 * 34 * 56] + [78] 兩個式子遞迴
遞迴會先處理完這兩個式子，再處理加法

以下是完整的步驟 (中括號代表式子的拆法)

拆 + 號：[12 * 34 * 56] + [78]
拆 * 號：[[12 * 34] * 56] + [78]
拆 * 號：[[[12] * [34]] * 56] + [78]
返回結果：22926

✅ 完整代碼

評分結果(參考) ： AC (2ms, 332KB)

#include <bits/stdc++.h>
using namespace std;
#define int long long

string s;

int s2i(int begin_, int end_){
    int num = 0;
    for (int i=begin_; i<end_; i++) {
        num = num*10 + (s[i]-'0');
    }
    return num;
}

int calculate(int begin_, int end_) {

    if (begin_ >= end_) return 0;

    // handle + -
    int layer = 0;
    for(int i=end_-1; i>=begin_; i--) {
        if(s[i] == ')') layer++;
        else if(s[i] == '(') layer--;
        
        else if((s[i] == '+' || s[i] == '-') && layer == 0) {
            if(s[i] == '+') return calculate(begin_, i-1) + calculate(i+2, end_);
            else return calculate(begin_, i-1) - calculate(i+2, end_);
        }
    }

    // handle * / %
    layer = 0;
    for(int i = end_-1; i>=begin_; i--) {
        if(s[i] == ')') layer++;
        else if(s[i] == '(') layer--;
        
        else if(layer == 0) {
            if(s[i] == '*') return calculate(begin_, i-1) * calculate(i+2, end_);
            if(s[i] == '/') return calculate(begin_, i-1) / calculate(i+2, end_);
            if(s[i] == '%') return calculate(begin_, i-1) % calculate(i+2, end_);
        }
    }

    // handle ( )
    if(s[begin_] == '(' && s[end_-1] == ')') {
        return calculate(begin_+2, end_-2);
    }

    return s2i(begin_, end_);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while(getline(cin, s)) {
        cout << calculate(0, s.size()) << endl;
    }
}