題意

傳送門 P1175 表達(dá)式的轉(zhuǎn)換

題解

編碼運(yùn)算符的優(yōu)先級(jí)，線性復(fù)雜度將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。為了方便輸出，可以用類似對(duì)頂棧的結(jié)構(gòu)，初始時(shí)右側(cè)棧為后綴表達(dá)式；對(duì)于每一步計(jì)算，右側(cè)棧不斷彈出數(shù)字到左側(cè)棧，直到掃描到第一個(gè)運(yùn)算符。總時(shí)間復(fù)雜度 $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;
}