#include namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; constexpr int DIGIT = 6; constexpr int BASE = 1000000; struct lazy_bigint { vector d; lazy_bigint() {} lazy_bigint(integral auto X) { while (X) { d.push_back(X % BASE); X /= BASE; } } lazy_bigint(string_view S) { if (S == "0") S = ""; int L = S.size(); bool neg = false; while (!S.empty() && (S.front() == '+' || S.front() == '-')) { neg ^= S.front() == '-'; S = {S.begin() + 1, S.end()}; } int dlen = (L + DIGIT - 1) / DIGIT; d = vector(dlen); for (int i = 0; i < dlen; i++) { int l = i * DIGIT, r = min((i + 1) * DIGIT, L); int x = 0; for (int i = r - 1; i >= l; i--) { char c = S[L - 1 - i]; assert(isdigit(c)); x = 10 * x + (c - '0'); } d[i] = x; } if (neg) for (int &x : d) x *= -1; } 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]; } void normalize() { if (empty()) return; assert(d.back()); if (d.back() > 0) { bool borrow = false; for (int &x : d) { x -= borrow; borrow = x < 0; if (borrow) x += BASE; } assert(!borrow); } else { bool borrow = false; for (int &x : d) { x += borrow; borrow = x > 0; if (borrow) x -= BASE; } assert(!borrow); } while (!d.back()) d.pop_back(); } string to_string() { normalize(); if (empty()) return "0"; string ans; for (int x : d) { x = abs(x); for (int i = 0; i < DIGIT; i++) { ans += '0' + x % 10; x /= 10; } } while (ans.back() == '0') ans.pop_back(); if (d.back() < 0) ans += '-'; ranges::reverse(ans); return ans; } friend istream &operator>>(istream &is, lazy_bigint &A) { string S; is >> S; A = lazy_bigint(S); return is; } friend ostream &operator<<(ostream &os, lazy_bigint &A) { return os << A.to_string(); } template void plus_minus_core(const lazy_bigint& rhs) { int n = d.size(), m = rhs.d.size(); d.resize(max(n, m)); int carry = 0; for (int i = 0; i < m; i++) { if constexpr (!minus) d[i] += carry + rhs.d[i]; else d[i] += carry - rhs.d[i]; if (d[i] <= -BASE) carry = -1, d[i] += BASE; else if (d[i] >= BASE) carry = 1, d[i] -= BASE; else carry = 0; } if (carry) d.emplace_back(carry); while (!empty() && !d.back()) d.pop_back(); } lazy_bigint& operator+=(const lazy_bigint& rhs) { plus_minus_core(rhs); return *this; } lazy_bigint& operator-=(const lazy_bigint& rhs) { plus_minus_core(rhs); return *this; } friend lazy_bigint operator+(const lazy_bigint &lhs, const lazy_bigint &rhs) { auto res = lhs; res += rhs; return res; } friend lazy_bigint operator-(const lazy_bigint &lhs, const lazy_bigint &rhs) { auto res = lhs; res -= rhs; return res; } friend lazy_bigint operator*(const lazy_bigint &A, const lazy_bigint &B) { if (A.empty() || B.empty()) return 0; int N = A.size(); int M = B.size(); vector a(N), b(M); for (int i = 0; i < N; i++) a[i] = A[i]; for (int i = 0; i < M; i++) b[i] = B[i]; auto C = atcoder::convolution_ll(a, b); long long carry = 0; for (int i = 0; i < N + M - 1; i++) { C[i] += carry; carry = C[i] / BASE; C[i] %= BASE; } while (carry) { C.push_back(carry % BASE); carry /= BASE; } while (C.back() == 0) C.pop_back(); lazy_bigint ans; ans.d.resize(C.size()); for (int i = 0; i < ssize(C); i++) ans[i] = C[i]; return ans; } lazy_bigint& operator*=(const lazy_bigint &rhs) { return *this = *this * rhs; } }; string s; int ptr = 0; lazy_bigint rd_expr(); optional rd_term(); optional rd_factor(); optional rd_number(); optional rd_number() { int l = ptr; while (isdigit(s[ptr])) ptr++; if (l == ptr) return {}; lazy_bigint res({s.begin() + l, s.begin() + ptr}); return res; } optional rd_factor() { while (s[ptr] == '+') ptr++; if (s[ptr] == '-') { s[ptr] = '*'; return -1; } optional res; if (s[ptr] == '(') { ptr++; res = rd_expr(); assert(s[ptr] == ')'); ptr++; } else { res = rd_number(); } return res; } optional rd_term() { vector facts; while (true) { optional res = rd_factor(); if (!res) break; facts.push_back(move(res.value())); if (s[ptr] != '*') break; ptr++; } if (facts.empty()) return {}; static queue q; while (facts.size()) { q.emplace(move(facts.back())); facts.pop_back(); } while (q.size() >= 2) { auto a = move(q.front()); q.pop(); auto b = move(q.front()); q.pop(); q.emplace(a * b); } auto res = move(q.back()); q.pop(); return res; } lazy_bigint rd_expr() { vector terms; while (true) { optional res = rd_term(); if (!res) break; terms.push_back(move(res.value())); } auto it = ranges::max_element(terms, less{}, [](const auto &x) { return x.size(); }); auto res = move(*it); terms.erase(it); for (const auto& t : terms) res += t; return res; } } // namespace int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n >> s; s += '$'; auto ans = rd_expr(); assert(ptr == n); cout << ans << '\n'; }