friendbooloperator>=(const Opt &x, const Opt &y) { int xx = x.getval(), yy = y.getval(); if (xx != yy) return xx > yy; if (x.opt == '^') returnfalse; // 特殊处理 ^ 的向右结合 returntrue; } };
classEle { public: bool type; // 是否为运算符 union { int val; char opt; } u;
friend ostream &operator<<(ostream &cout, const Ele &x) { if (x.type) return cout << x.u.opt; return cout << x.u.val; } };
intpow(int x, int y){ int res = 1; for (int i = 0; i < y; i++) { res *= x; } return res; }
voidsolve(){ vector<Ele> suffix;
{ string s; cin >> s; s += '$'; int i = 0; stack<Opt> stk; while (i < s.size()) if (isdigit(s[i])) { int x = 0; while (isdigit(s[i])) { x = x * 10 + s[i] - '0'; suffix.push_back({false, x}); i++; } } else { char c = s[i++]; switch (c) { case'(': stk.push('('); break; case')': while (stk.top().opt != '(') { suffix.push_back({true, stk.top().opt}); stk.pop(); } stk.pop(); break; default: while (not stk.empty() and stk.top() >= c) { suffix.push_back({true, stk.top().opt}); stk.pop(); } stk.push(c); break; } } }
{ for (const Ele &ele : suffix) cout << ele << ' '; cout << endl; while (suffix.size() > 1) { int i = 2; while (not suffix[i].type) i++; int x = suffix[i - 2].u.val; int y = suffix[i - 1].u.val; int c = suffix[i].u.opt; suffix.erase(suffix.begin() + i - 1, suffix.begin() + i + 1); switch (c) { case'+': x = x + y; break; case'-': x = x - y; break; case'*': x = x * y; break; case'/': x = x / y; break; case'^': x = pow(x, y); break; } suffix[i - 2].u.val = x; for (const Ele &ele : suffix) cout << ele << ' '; cout << endl; } } }