solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

bool delim(char c) { return c == ' '; }

bool is_op(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

bool is_unary(char c) { return c == '+' || c == '-'; }

int priority(char op) {
    if (op < 0)  // unary operator
        return 3;
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return -1;
}

void process_op(stack<long long>& st, char op) {
    if (op < 0) {
        int l = st.top();
        st.pop();
        switch (-op) {
            case '+':
                st.push(l);
                break;
            case '-':
                st.push(-l);
                break;
        }
    } else {  // 取出栈顶元素，注意顺序
        int r = st.top();
        st.pop();
        int l = st.top();
        st.pop();
        switch (op) {
            case '+':
                st.push(l + r);
                break;
            case '-':
                st.push(l - r);
                break;
            case '*':
                st.push(l * r);
                break;
            case '/':
                st.push(l / r);
                break;
        }
    }
}

set<char> S{'+', '-', '*', '/'};
bool left_assoc(char op) {
    return S.count(op);
}

long long evaluate(string& s) {
    stack<long long> st;
    stack<char> op;
    bool may_be_unary = true;
    for (int i = 0; i < (int)s.size(); i++) {
        if (delim(s[i])) continue;

        if (s[i] == '(') {
            op.push('(');  // 2. 如果遇到左括号，那么将其放在运算符栈上
            may_be_unary = true;
        } else if (s[i] == ')') {  // 3. 如果遇到右括号，执行一对括号内的所有运算符
            while (op.top() != '(') {
                process_op(st, op.top());
                op.pop();  // 不断输出栈顶元素，直至遇到左括号
            }
            op.pop();  // 左括号出栈
            may_be_unary = false;
        } else if (is_op(s[i])) {  // 4. 如果遇到其他运算符
            char cur_op = s[i];
            if (may_be_unary && is_unary(cur_op)) cur_op = -cur_op;
            while (!op.empty() &&
                   ((left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) || (!left_assoc(cur_op) && priority(op.top()) > priority(cur_op)))) {
                process_op(st, op.top());
                op.pop();  // 不断输出所有运算优先级大于等于当前运算符的运算符
            }
            op.push(cur_op);  // 新的运算符入运算符栈
            may_be_unary = true;
        } else {  // 1. 如果遇到数字，直接输出该数字
            long long number = 0;
            while (i < (int)s.size() && isalnum(s[i]))
                number = number * 10 + s[i++] - '0';
            --i;
            st.push(number);
            may_be_unary = false;
        }
    }

    while (!op.empty()) {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}

class Solution {
   public:
    int calculate(string s) {
        return evaluate(s);
    }
};