#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pi = pair; using pl = pair; using pd = pair; #define mp make_pair #define f first #define s second #define tcT template using V = vector; tcT, size_t SZ > using AR = array; using vi = V; using vb = V; using vl = V; using vd = V; using vs = V; using vpi = V; using vpl = V; using vpd = V; // vectors #define sz(x) int(size(x)) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) rbegin(x), rend(x) #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound tcT > int lwb(const V &a, const T &b) { return int(lb(all(a), b) - bg(a)); } tcT > int upb(const V &a, const T &b) { return int(ub(all(a), b) - bg(a)); } // loops #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define rep(a) F0R(_, a) #define each(a, x) for (auto &a : x) const int MOD = 998244353; // 1e9+7; const int MX = (int)2e5 + 5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template using pqg = priority_queue, greater>; // bitwise ops // also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until // USACO updates ... return x == 0 ? 0 : 31 - __builtin_clz(x); } // floor(log2(x)) constexpr int p2(int x) { return 1 << x; } constexpr int msk2(int x) { return p2(x) - 1; } ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down tcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b) tcTU > T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); // assuming f is increasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; } tcTU > T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); // assuming f is decreasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; } tcT > void remDup(vector &v) { // sort and remove duplicates sort(all(v)); v.erase(unique(all(v)), end(v)); } tcTU > void safeErase(T &t, const U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); } inline namespace IO { #define SFINAE(x, ...) \ template struct x : std::false_type {}; \ template struct x> : std::true_type {} SFINAE(DefaultI, decltype(std::cin >> std::declval())); SFINAE(DefaultO, decltype(std::cout << std::declval())); SFINAE(IsTuple, typename std::tuple_size::type); SFINAE(Iterable, decltype(std::begin(std::declval()))); template struct Reader { template void Impl(T &t) { if constexpr (DefaultI::value) is >> t; else if constexpr (Iterable::value) { for (auto &x : t) Impl(x); } else if constexpr (IsTuple::value) { std::apply([this](auto &...args) { (Impl(args), ...); }, t); } else static_assert(IsTuple::value, "No matching type for read"); } template void read(Ts &...ts) { ((Impl(ts)), ...); } }; template void re(Ts &...ts) { Reader{}.read(ts...); } #define def(t, args...) \ t args; \ re(args); template struct Writer { string comma() const { return debug ? "," : ""; } template constexpr char Space(const T &) const { return print_nd && (Iterable::value or IsTuple::value) ? '\n' : ' '; } template void Impl(T const &t) const { if constexpr (DefaultO::value) os << t; else if constexpr (Iterable::value) { if (debug) os << '{'; int i = 0; for (auto &&x : t) ((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x)); if (debug) os << '}'; } else if constexpr (IsTuple::value) { if (debug) os << '('; std::apply( [this](auto const &...args) { int i = 0; (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)), ...); }, t); if (debug) os << ')'; } else static_assert(IsTuple::value, "No matching type for print"); } template void ImplWrapper(T const &t) const { if (debug) os << "\033[0;31m"; Impl(t); if (debug) os << "\033[0m"; } template void print(Ts const &...ts) const { ((Impl(ts)), ...); } template void print_with_sep(const std::string &sep, F const &f, Ts const &...ts) const { ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n'; } void print_with_sep(const std::string &) const { os << '\n'; } }; template void pr(Ts const &...ts) { Writer{}.print(ts...); } template void ps(Ts const &...ts) { Writer{}.print_with_sep(" ", ts...); } } // namespace IO inline namespace Debug { template void err(Args... args) { Writer{}.print_with_sep(" | ", args...); } template void errn(Args... args) { Writer{}.print_with_sep(" | ", args...); } void err_prefix(str func, int line, string args) { cerr << "\033[0;31m\u001b[1mDEBUG\033[0m" << " | " << "\u001b[34m" << func << "\033[0m" << ":" << "\u001b[34m" << line << "\033[0m" << " - " << "[" << args << "] = "; } #ifdef LOCAL #define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args) #define dbgn(args...) err_prefix(__FUNCTION__, __LINE__, #args), errn(args) #else #define dbg(...) #define dbgn(args...) #endif const auto beg_time = std::chrono::high_resolution_clock::now(); // https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1 double time_elapsed() { return chrono::duration(std::chrono::high_resolution_clock::now() - beg_time) .count(); } } // namespace Debug inline namespace FileIO { void setIn(str s) { freopen(s.c_str(), "r", stdin); } void setOut(str s) { freopen(s.c_str(), "w", stdout); } void setIO(str s = "") { cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams cout << fixed << setprecision(12); // cin.exceptions(cin.failbit); // throws exception when do smth illegal // ex. try to read letter into int if (sz(s)) setIn(s + ".in"), setOut(s + ".out"); // for old USACO } } // namespace FileIO #include #include #include const int DIGIT = 6; const int BASE = 1000000; struct positive_bigint { std::vector d; positive_bigint() {} positive_bigint(long long X) { while (X > 0) { d.push_back(X % BASE); X /= BASE; } } positive_bigint(std::string S) { if (S == "0") { S = ""; } int L = S.size(); d.resize((L + DIGIT - 1) / DIGIT, 0); for (int i = L - 1; i >= 0; i -= 6) { for (int j = std::max(i - 5, 0); j <= i; j++) { d[i / DIGIT] *= 10; d[i / DIGIT] += S[j] - '0'; } } std::reverse(d.begin(), d.end()); } bool empty() const { return d.empty(); } int size() const { return d.size(); } int &operator[](int i) { return d[i]; } int operator[](int i) const { return d[i]; } }; std::string to_string(const positive_bigint &A) { int N = A.size(); std::string ans; for (int i = N - 1; i >= 0; i--) { std::string tmp = std::to_string(A[i]); if (i < N - 1) { ans += std::string(DIGIT - tmp.size(), '0'); } ans += tmp; } if (ans.empty()) { ans = "0"; } return ans; } std::istream &operator>>(std::istream &is, positive_bigint &A) { std::string S; is >> S; A = positive_bigint(S); return is; } std::ostream &operator<<(std::ostream &os, positive_bigint &A) { os << to_string(A); return os; } int cmp(const positive_bigint &A, const positive_bigint &B) { int N = A.size(); int M = B.size(); if (N < M) { return -1; } else if (N > M) { return 1; } else { for (int i = N - 1; i >= 0; i--) { if (A[i] < B[i]) { return -1; } if (A[i] > B[i]) { return 1; } } return 0; } } bool operator==(const positive_bigint &A, const positive_bigint &B) { return cmp(A, B) == 0; } bool operator!=(const positive_bigint &A, const positive_bigint &B) { return cmp(A, B) != 0; } bool operator<(const positive_bigint &A, const positive_bigint &B) { return cmp(A, B) < 0; } bool operator>(const positive_bigint &A, const positive_bigint &B) { return cmp(A, B) > 0; } bool operator<=(const positive_bigint &A, const positive_bigint &B) { return cmp(A, B) <= 0; } bool operator>=(const positive_bigint &A, const positive_bigint &B) { return cmp(A, B) >= 0; } positive_bigint &operator+=(positive_bigint &A, const positive_bigint &B) { int N = A.size(); int M = B.size(); while (N < M) { A.d.push_back(0); N++; } for (int i = 0; i < M; i++) { A[i] += B[i]; } for (int i = 0; i < N - 1; i++) { if (A[i] >= BASE) { A[i] -= BASE; A[i + 1]++; } } if (N > 0) { if (A[N - 1] >= BASE) { A.d.push_back(1); A[N - 1] -= BASE; } } return A; } positive_bigint operator+(const positive_bigint &A, const positive_bigint &B) { positive_bigint A2 = A; A2 += B; return A2; } positive_bigint &operator-=(positive_bigint &A, const positive_bigint &B) { int N = A.size(); int M = B.size(); for (int i = 0; i < M; i++) { A[i] -= B[i]; } for (int i = 0; i < N - 1; i++) { if (A[i] < 0) { A[i] += BASE; A[i + 1]--; } } while (!A.empty()) { if (A.d.back() == 0) { A.d.pop_back(); } else { break; } } return A; } positive_bigint operator-(const positive_bigint &A, const positive_bigint &B) { positive_bigint A2 = A; A2 -= B; return A2; } positive_bigint operator*(const positive_bigint &A, const positive_bigint &B) { if (A.empty() || B.empty()) { return 0; } int N = A.size(); int M = B.size(); std::vector a(N); for (int i = 0; i < N; i++) { a[i] = A[i]; } std::vector b(M); for (int i = 0; i < M; i++) { b[i] = B[i]; } std::vector C = atcoder::convolution_ll(a, b); for (int i = 0; i < N + M - 2; i++) { C[i + 1] += C[i] / BASE; C[i] %= BASE; } if (C[N + M - 2] >= BASE) { C.resize(N + M); C[N + M - 1] += C[N + M - 2] / BASE; C[N + M - 2] %= BASE; } positive_bigint ans; ans.d.resize(C.size()); for (int i = 0; i < C.size(); i++) { ans[i] = C[i]; } return ans; } positive_bigint operator*=(positive_bigint &A, const positive_bigint &B) { A = A * B; return A; } struct bigint { bool neg = false; positive_bigint a; bigint() {} bigint(long long X) : neg(X < 0), a(abs(X)) {} bigint(const positive_bigint &X, bool neg = false) : neg(neg), a(X) {} bigint(const std::string &s) { if (!s.empty()) { if (s[0] == '-') { neg = true; a = positive_bigint(s.substr(1, s.size() - 1)); } else { a = positive_bigint(s); } } } bool empty() const { return a.empty(); } int size() const { return a.size(); } int &operator[](int i) { return a[i]; } }; std::string to_string(const bigint &A) { std::string ans; if (A.neg) { ans += '-'; } ans += to_string(A.a); return ans; } std::istream &operator>>(std::istream &is, bigint &A) { std::string S; is >> S; if (S != "0") { A = bigint(S); } return is; } std::ostream &operator<<(std::ostream &os, bigint A) { os << to_string(A); return os; } positive_bigint abs(const bigint &A) { return A.a; } int cmp(const bigint &A, const bigint &B) { if (!A.neg) { if (!B.neg) { return cmp(A.a, B.a); } else { return 1; } } else { if (!B.neg) { return -1; } else { return cmp(B.a, A.a); } } } bool operator==(const bigint &A, const bigint &B) { return cmp(A, B) == 0; } bool operator!=(const bigint &A, const bigint &B) { return cmp(A, B) != 0; } bool operator<(const bigint &A, const bigint &B) { return cmp(A, B) < 0; } bool operator>(const bigint &A, const bigint &B) { return cmp(A, B) > 0; } bool operator<=(const bigint &A, const bigint &B) { return cmp(A, B) <= 0; } bool operator>=(const bigint &A, const bigint &B) { return cmp(A, B) >= 0; } bigint operator+(const bigint &A) { return A; } bigint operator-(const bigint &A) { bigint A2 = A; if (!A2.empty()) { A2.neg = !A2.neg; } return A2; } bigint &operator+=(bigint &A, const bigint &B) { if (A.neg == B.neg) { A.a += B.a; } else { int c = cmp(A.a, B.a); if (c > 0) { A.a -= B.a; } else if (c < 0) { A.a = B.a - A.a; A.neg = !A.neg; } else { A = 0; } } return A; } bigint operator+(const bigint &A, const bigint &B) { bigint A2 = A; A2 += B; return A2; } bigint &operator-=(bigint &A, const bigint &B) { if (A.neg != B.neg) { A.a += B.a; } else { int c = cmp(A.a, B.a); if (c > 0) { A.a -= B.a; } else if (c < 0) { A.a = B.a - A.a; A.neg = !A.neg; } else { A = 0; } } return A; } bigint operator-(const bigint &A, const bigint &B) { bigint A2 = A; A2 -= B; return A2; } bigint operator*=(bigint &A, const bigint &B) { if (A.empty() || B.empty()) { A = 0; } else { if (B.neg) { A.neg = !A.neg; } A.a *= B.a; } return A; } bigint operator*(const bigint &A, const bigint &B) { bigint A2 = A; A2 *= B; return A2; } str s; struct Node { char op = '.'; Node *l = nullptr, *r = nullptr; str val; bigint eval() { if (op == '.') { assert(sz(val)); return bigint(val); } assert(l && r); bigint x = l->eval(); bigint y = r->eval(); if (op == '*') return x * y; if (op == '-') return x - y; assert(op == '+'); return x + y; } }; Node *make_op(char c, Node *l, Node *r) { return new Node{c, l, r}; } Node *combine(V nodes, str ops) { assert(sz(ops) == sz(nodes) - 1); V node_stk; str op_stk; F0R(i, sz(nodes)) { if (sz(op_stk) && op_stk.bk == '*') { assert(sz(node_stk)); node_stk.bk = make_op(op_stk.bk, node_stk.bk, nodes[i]); op_stk.pop_back(); } else { node_stk.pb(nodes[i]); } if (i < sz(ops)) { op_stk.pb(ops.at(i)); } } F0R(i, sz(op_stk)) { node_stk.ft = make_op(op_stk.at(i), node_stk.ft, node_stk.at(i + 1)); } return node_stk.ft; // assert(sz(nodes)); // dbg(sz(nodes), ops); // exit(0); } pair dfs(int pos) { V nodes; str ops; int parity = 0; while (true) { dbg(parity, pos); if (parity == 0) { if (s.at(pos) == '(') { ++pos; auto [npos, node] = dfs(pos); pos = npos; assert(sz(nodes) == sz(ops)); nodes.pb(node); } else if (s.at(pos) == '-' || isdigit(s.at(pos))) { int sgn = 1; while (s.at(pos) == '-') ++pos, sgn *= -1; str num; while (isdigit(s.at(pos))) num += s.at(pos++); if (sgn == -1) num = '-' + num; nodes.pb(new Node{'.', nullptr, nullptr, num}); } else { assert(false); } } else { if (s.at(pos) == ')') { ++pos; return {pos, combine(nodes, ops)}; } assert(s.at(pos) == '*' || s.at(pos) == '+' || s.at(pos) == '-'); ops += s.at(pos++); } parity ^= 1; } } int main() { // read read read setIO(); def(int, N); re(s); s = s + ")"; dbg(s); auto ret = dfs(0); assert(ret.f == sz(s)); ps(ret.s->eval()); // you should actually read the stuff at the bottom } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */