#include using namespace std; typedef long long ll; #define int ll string p; stack s; // ??? stack op; // ?? /*????????*/ stack num; // ???? stack tmp; // ??????????? /*??????????*/ inline int id(char ch) { /*????????????????*/ if (ch == '+' || ch == '-') return 1; if (ch == '*' || ch == '/') return 2; if (ch == '^') return 3; if (ch == '(' || ch == ')') return 0; return -1; } inline string solve(string p) { /*?????*/ while (s.size()) s.pop(); while (op.size()) op.pop(); for (int i = 0; i < int(p.size()); i++) { if (p[i] >= '0' && p[i] <= '9') s.push(p[i]); else { if (p[i] == '(') { op.push(p[i]); continue; } if (p[i] == ')') { while (!op.empty() && op.top() != '(') { s.push(op.top()); op.pop(); } if (!op.empty()) op.pop(); continue; } if (id(p[i]) <= 2) { while (!op.empty() && id(op.top()) >= id(p[i])) { s.push(op.top()); op.pop(); } } else { while (!op.empty() && id(op.top()) > id(p[i])) { s.push(op.top()); op.pop(); } } op.push(p[i]); } } while (!op.empty()) { s.push(op.top()); op.pop(); } string res = ""; while (!s.empty()) { res += s.top(); s.pop(); } reverse(res.begin(), res.end()); // ?? return res; } inline int f(int x, int y, char ch) { if (ch == '+') return x + y; if (ch == '-') return x - y; if (ch == '*') return x * y; if (ch == '/') return x / y; if (ch == '^') return int(pow(x, y)); return -1; } inline void Query(string s) { /*?????????*/ while (num.size()) num.pop(); for (int i = 0; i < int(s.size()); i++) { if (s[i] >= '0' && s[i] <= '9') num.push(s[i] - '0'); else { while (tmp.size()) tmp.pop(); while (num.size()) { tmp.push(num.top()); num.pop(); } while (tmp.size()) { num.push(tmp.top()); // cout << tmp.top() << " "; tmp.pop(); } // for(int j=i;j> p; Query(solve(p)); }