P1175 后缀表达式

题意

传送门 P1175 表达式的转换

题解

编码运算符的优先级，线性复杂度将中缀表达式转换为后缀表达式。为了方便输出，可以用类似对顶栈的结构，初始时右侧栈为后缀表达式；对于每一步计算，右侧栈不断弹出数字到左侧栈，直到扫描到第一个运算符。总时间复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);vector<string> left, right;string s;cin >> s;map<char, int> rnk{{'(', -1}, {'+', 0}, {'-', 0}, {'*', 1}, {'/', 1}, {'^', 2}};vector<char> ops;for (auto c : s) {if (c == '(') {ops.push_back(c);} else if (c == ')') {for (;;) {auto cc = ops.back();ops.pop_back();if (cc == '(') {break;}left.push_back(string(1, cc));}} else if (isdigit(c)) {left.push_back(string(1, c));} else {while (!ops.empty() && (rnk[ops.back()] > rnk[c] || (rnk[ops.back()] == rnk[c] && c != '^'))) {left.push_back(string(1, ops.back()));ops.pop_back();}ops.push_back(c);}}while (!ops.empty()) {left.push_back(string(1, ops.back()));ops.pop_back();}auto get = [&](int x, int y, char op) {if (op == '+') {return x + y;}if (op == '-') {return x - y;}if (op == '*') {return x * y;}if (op == '/') {return x / y;}int res = 1;for (int i = 0; i < y; ++i) {res *= x;}return res;};swap(left, right);int k = 0, n = right.size();for (;;) {while (k < n && isdigit(right[k][0])) {left.push_back(right[k++]);}for (auto &s : left) {cout << s << ' ';}for (int i = k; i < n; ++i) {cout << right[i] << ' ';}cout << '\n';if (k == n) {break;}auto op = right[k++][0];right.pop_back();int y = stoi(left.back());left.pop_back();int x = stoi(left.back());left.pop_back();int z = get(x, y, op);left.push_back(to_string(z));}return 0;
}