algo-aha

括号的解析

递归法，假设parse(const string &s, int &idx)函数能解析一层')'，内部的递归调用解析掉内层括号

while (idx < N && s[idx] != ')') {
    if (s[idx] == '(') {
        idx++; // (
        auto paren = parse(formula, idx); // 递归解析内层
        idx++; // )
        ...
    } else {
        ...
    }
}

或者用遇'('++、遇')'--的计数来确认合法括号的结束位置（当count==0时）

化学式中各原子数

• https://leetcode.com/problems/number-of-atoms

string countOfAtoms(string formula) {
    int idx = 0;
    auto count = parse(formula, idx);
    ostringstream oss;
    for (auto &e : count) {
        oss << e.first;
        if (e.second > 1) oss << e.second;
    }
    return oss.str();
}

// 解析一层括号
map<string, int> parse(const string &formula, int &idx) {
    const int N = formula.size();
    map<string, int> count;
    while (idx < N && formula[idx] != ')') {
        if (formula[idx] == '(') {
            idx++; // (
            auto paren = parse(formula, idx);
            idx++; // )
            int num = parseNum(formula, idx);
            for (auto &e : paren) { 
                count[e.first] += e.second * num;                    
            }
        } else {
            auto name = parseName(formula, idx);
            int num = parseNum(formula, idx);
            count[name] += num;
        }
    }    
    return count;
}

int parseNum(const string &formula, int &idx) {
    int start = idx;
    while (idx < formula.size() && isdigit(formula[idx])) idx++;
    if (idx == start) return 1;
    return stoi(formula.substr(start, idx - start));
}

string parseName(const string &formula, int &idx) {
    int start = idx;
    idx++; // upper case
    while (idx < formula.size() && islower(formula[idx])) idx++;
    return formula.substr(start, idx - start);
}

解析k[encoded]串

• https://leetcode.com/problems/decode-string/

string decodeString(string s) {
    int idx = 0;
    return decodeString(s, idx);
}

// 能decode掉最外一层[xxx]
string decodeString(string &s, int &idx) {
    string ans;
    while (idx < s.size() && s[idx] != ']') {
        if (isalpha(s[idx])) {
            ans += s[idx];
            idx++;
        } else { // 数字开头
            int num = 0;
            while (idx < s.size() && isdigit(s[idx])) {
                num = num * 10 + s[idx] - '0';
                idx++;
            }
            idx++; // [
            string sub = decodeString(s, idx);
            idx++; // ]
            while (num--) ans += sub;
        }
    }
    return ans;
}

加减乘除计算

• https://leetcode.com/problems/basic-calculator/ 加减、括号
• https://leetcode.com/problems/basic-calculator-ii/ 加减、乘除
• https://leetcode.com/problems/basic-calculator-iii/ 加减、乘除、括号

i和ii是iii的特例，iii的栈解法如下

int calculate(string &s) {
    // 中缀转后缀，用nums栈和ops栈
    // 遇到下一个优先级<=栈顶的op时、先弹出计算再把op入栈。
    // 左括号'('先入栈，等遇到右括号')'时不断弹出计算直到'('；
    // 左括号只能遇右括号时弹出，将'('的优先级设为最小，以防止被其他op计算误弹出。
    unordered_map<char, int> priority = {
        {'*', 2}, {'/', 2},
        {'+', 1}, {'-', 1},
        {'(', 0},
    };

    stack<int> nums;
    stack<char> ops;
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (c == ' ') continue;
        if (isdigit(c)) {
            // 因为最后会i++，这里解析完num后i指针必须停在最后一位数字上
            int num = c - '0';
            while (i + 1 < s.size() && isdigit(s[i+1]))
                num = num * 10 + s[++i] - '0';
            nums.push(num);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.top() != '(') 
                calc(nums, ops);
            ops.pop(); // 弹出'('
        } else { // +-*/
            while (!ops.empty() && priority[c] <= priority[ops.top()])
                calc(nums, ops);
            ops.push(c);
        }
    }
    while (!ops.empty())
        calc(nums, ops);

    return nums.top();
}

void calc(stack<int> &nums, stack<char> &ops) {
    if (ops.empty() || nums.size() < 2) return;
    char op = ops.top(); ops.pop();
    int val2 = nums.top(); nums.pop();
    int val1 = nums.top(); nums.pop();

    if (op == '*') {
        nums.push(val1 * val2);
    } else if (op == '/') {
        nums.push(val1 / val2);
    } else if (op == '+') {
        nums.push(val1 + val2);
    } else if (op == '-') {
        nums.push(val1 - val2);
    }
}