洛谷P1175 表达式的转换

题目传送门：https://www.luogu.com.cn/problem/P1175

要点1：运算符优先级

int priority(char ch) {
    switch (ch) {
        case '+': return 1;
        case '-': return 1;
        case '*': return 2;
        case '/': return 2;
        case '^': return 3;
        case '(': return 0;
    }
}

维护dat表达式栈和op符号栈，如果当前符号优先级高于op栈顶就放入，否则先把栈顶不满足条件的符号移到dat栈。

要点2：^符号的处理

2^2^3 => 2 2 3 ^ ^

^运算是右结合的，且优先级最高，因此可以直接放入op栈

要点3：括号的处理

括号内的必须先运算，因此发现左括号时直接存入op栈，发现右括号时从op栈内弹出括号内所有运算符到dat。

要点4：运算中间过程打印

维护一个nums数组存运算中间结果的数，如果后缀表达式中检测到数字就放入nums，检测到符号就pop两个操作数运算后存回nums，并打印一次。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;
mt19937_64 rng(random_device{}());
int priority(char ch) {
    switch (ch) {
        case '+': return 1;
        case '-': return 1;
        case '*': return 2;
        case '/': return 2;
        case '^': return 3;
        case '(': return 0;
    }
}
int ksm(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}
int eval(int x, int y, char op) {
    switch (op) {
        case '+': return x+y;
        case '-': return x-y;
        case '*': return x*y;
        case '/': return x/y;
        case '^': return ksm(x, y);
    }
}
void solve() {
    string str;
    cin >> str;
    stack<char> dat;
    deque<char> op;
    for (auto ch : str) {
        if (ch >= '0' && ch <= '9') {
            dat.push(ch);
        } else if (ch == '(') {
            op.push_back(ch);
        } else if (ch == ')') {
            while (op.back() != '(') {
                dat.push(op.back()); op.pop_back();
            }
            op.pop_back(); // pop '('
        } else {
            // ^右结合
            if (op.empty() || priority(op.back()) < priority(ch) || ch == '^') {
                op.push_back(ch);
            } else {
                while (op.size() && priority(op.back()) >= priority(ch)) {
                    dat.push(op.back()); op.pop_back();
                }
                op.push_back(ch);
            }
        }
    }
    while (dat.size()) {
        op.push_back(dat.top()); dat.pop();
    }
    deque<int> nums;

    auto print = [&]() {
        for (int x : nums) {
            cout << x << ' ';
        }
        for (auto it = op.rbegin(); it != op.rend(); ++it) {
            cout << *it << ' ';
        }
        cout << '\n';
    };

    print();

    while (op.size()) {
        char ch = op.back(); op.pop_back();
        if (ch >= '0' && ch <= '9') nums.push_back(ch - '0');
        else {
            int v2 = nums.back(); nums.pop_back();
            int v1 = nums.back(); nums.pop_back();
            int v = eval(v1, v2, ch);
            nums.push_back(v);
            print();
        }
    }
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) 
        solve();
    return 0;
}