MT3034 算术招亲

#include <bits/stdc++.h>
using namespace std;
const int N = 40;
bool tag[N];
bool is_op(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
int priority(char op)
{ // 优先级排序
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    if (op == '^')
        return 3;
    return -1;
}
void process_op(stack<int> &st, char op)
{
    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;
    case '^':
        st.push(pow(l, r));
        break;
    }
}
 
int evaluate(string &s)
{
    stack<int> st;
    stack<char> op;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
        {
            if (!tag[i])
            {
                continue; // 括号位置不合法
            }
            op.push(s[i]);
        }
        else if (s[i] == ')')
        {
            if (!tag[i])
            {
                continue; // 括号位置不合法
            }
            while (op.top() != '(')
            {
                process_op(st, op.top());
                op.pop();
            }
            op.pop();
        }
        else if (is_op(s[i]))
        { // 运算符优先级
            while (!op.empty() && priority(op.top()) >= priority(s[i]))
            {
                process_op(st, op.top());
                op.pop();
            }
            op.push(s[i]);
        }
        else
        {
            int num = 0;
            while (i < s.size() && isdigit(s[i]))
            {
                num = num * 10 + s[i] - '0';
                i++;
            }
            i--;
            st.push(num);
        }
    }
    while (!op.empty())
    {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}
 
void init(string &s)
{ // 去除多余的括号
    stack<pair<char, int>> st;
    for (int i = 0; i < s.size(); i++)
    {
        if (!st.empty() && st.top().first == '(' && s[i] == ')')
        {                                         // 如果栈顶为(并且当前遍历到了(  --> 合法
            tag[i] = tag[st.top().second] = true; // 两个位置为true 即括号位置合法
            st.pop();                             // 合法的(弹出
        }
        else if (s[i] == '(') // 记录(位置
        {
            st.push({'(', i});
        }
    }
}
 
int main()
{
    string s;
    cin >> s;
    init(s);
    cout << evaluate(s);
    return 0;
}