#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; } using namespace std; // Parser (T must have constructor T(long long)) template struct Parser { /* basic settings */ vector> OPERATORS; // binary operator priority function OPERATION; // binary operation /* optional settings */ function GET_LEAF; // leaf parser vector UNARY_OPERATORS; // unary operator (ex: "-", "log") function UNARY_OPERATION; // unary operation const string OPERATOR_NUMBER = "num"; /* results */ string S; int root; // vals[root] is the answer vector vals; // value of each node vector ops; // operator of each node vector left, right; // the index of left-node, right-node vector ids; // the node-index of i-th value /* constructor */ Parser() {} Parser(const vector> &operators, const function operation) { init(operators, operation); } Parser(const vector> &operators, const function operation, const function get_leaf) { init(operators, operation, get_leaf); } Parser(const vector> &operators, const function operation, const function get_leaf, const vector &unary_operators, const function unary_operation) { init(operators, operation, get_leaf, unary_operators, unary_operation); } void init(const vector> &operators, const function operation) { OPERATORS = operators, OPERATION = operation; } void init(const vector> &operators, const function operation, const function get_leaf) { OPERATORS = operators, OPERATION = operation; GET_LEAF = get_leaf; } void init(const vector> &operators, const function operation, const function get_leaf, const vector &unary_operators, const function unary_operation) { OPERATORS = operators, OPERATION = operation; GET_LEAF = get_leaf; UNARY_OPERATORS = unary_operators, UNARY_OPERATION = unary_operation; } void clear() { S = ""; vals.clear(), ops.clear(), left.clear(), right.clear(), ids.clear(); } /* node generator */ // value int new_leaf(T val, int &id) { vals.push_back(val); ops.push_back(OPERATOR_NUMBER); left.push_back(-1); right.push_back(-1); ids.push_back(id++); return (int)vals.size() - 1; } // FUNC(lp) int new_node_with_left(T val, const string &op, int lp) { vals.push_back(val); ops.push_back(op); left.push_back(lp); right.push_back(-1); ids.push_back(-1); return (int)vals.size() - 1; } // (lp) op (rp) int new_node_with_left_right(const string &op, int lp, int rp) { vals.push_back(OPERATION(op, vals[lp], vals[rp])); ops.push_back(op); left.push_back(lp); right.push_back(rp); ids.push_back(-1); return (int)vals.size() - 1; } /* main parser */ T parse(const string &str, bool default_parse_numeric = true) { clear(); S = str; int p = 0, id = 0; root = parse(p, id, default_parse_numeric); return vals[root]; } int parse(int &p, int &id, bool default_parse_numeric, int depth = 0) { assert(p >= 0 && p < (int)S.size()); string op; if (depth < (int)OPERATORS.size()) { // recursive descent int lp = parse(p, id, default_parse_numeric, depth + 1); bool update = false; do { update = false; if (is_in_the_operators(p, op, OPERATORS[(int)OPERATORS.size() - depth - 1])) { int rp = parse(p, id, default_parse_numeric, depth + 1); lp = new_node_with_left_right(op, lp, rp); update = true; } } while (p < (int)S.size() && update); return lp; } else if (S[p] == '(') { return get_bracket(p, id, default_parse_numeric); } else if (default_parse_numeric && (S[p] == '-' || isdigit(S[p]))) { return get_number(p, id); } else if (is_in_the_operators(p, op, UNARY_OPERATORS)) { return get_unary_operation(p, id, op, default_parse_numeric); } else { return new_leaf(GET_LEAF(S, p), id); } } bool is_the_operator(int &p, const string &op) { if (op != "" && S.substr(p, op.size()) == op) { p += op.size(); return true; } return false; } bool is_in_the_operators(int &p, string &res_op, const vector &ops) { for (const auto &op : ops) { if (is_the_operator(p, op)) { res_op = op; return true; } } return false; } int get_number(int &p, int &id) { long long val = 0, sign = 1; if (S[p] == '-') sign = -1, ++p; while (p < (int)S.size() && isdigit(S[p])) { val = val * 10 + (int)(S[p++] - '0'); } return new_leaf(T(val * sign), id); } int get_bracket(int &p, int &id, bool default_parse_numeric) { ++p; // skip "(" int lp = parse(p, id, default_parse_numeric, 0); ++p; // skip ")" return lp; } int get_unary_operation(int &p, int &id, const string &op, bool default_parse_numeric) { int lp; if (S[p] == '(') lp = get_bracket(p, id, default_parse_numeric); else lp = parse(p, id, default_parse_numeric, (int)OPERATORS.size()); return new_node_with_left(UNARY_OPERATION(op, vals[lp]), op, lp); } /* dump */ void dump() { dump_rec(root); } void dump_rec(int v, string space = "") { cout << space << v << ": (" << ops[v] << ", " << vals[v] << ") -> left: " << left[v] << ", right: " << right[v] << endl; if (left[v] != -1) dump_rec(left[v], space + " "); if (right[v] != -1) dump_rec(right[v], space + " "); } }; int main() { vector> operators = {{"*"}, {"+", "-"}}; auto operation = [&](const string &op, bigint a, bigint b) -> bigint { if (op == "+") return a + b; else if (op == "-") return a - b; else if (op == "*") return a * b; else return 0; }; Parser ps(operators, operation); int N; cin >> N; string S, news; cin >> S; int c = 0; for (char i: S) { if (i == '-') c++; else { if (c % 2 == 1) { news += '-'; c = 0; } news += i; } } cout << ps.parse(news) << endl; }