#define _USE_MATH_DEFINES #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <vector> #include <array> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <iterator> using namespace std; class Node{ public: char ope; string s; Node *left, *right; Node(){ ope = '\0'; left = right = NULL; } ~Node(){ delete left; delete right; } }; // 数式の構文木を作成する class syntacticAnalysis { vector<int> binaryPriority; // 二項演算子の優先順位(数値が小さいほど優先順位が高い。-1ならば二項演算子ではない) vector<bool> binaryAssociativity; // 二項演算子の結合規則(trueならば左から右に結合) vector<bool> isUnaryOpe; // 単項演算子 stack<pair<Node*, bool> > stk; void deleteAllNodes() { while(!stk.empty()){ delete stk.top().first; stk.pop(); } } bool calc(int maxPriority) { if(!stk.top().second) return false; pair<Node*, bool> right = stk.top(); stk.pop(); while(stk.top().first != NULL){ pair<Node*, bool> ope = stk.top(); if(ope.second) break; stk.pop(); if(binaryPriority[ope.first->ope] != -1 && stk.top().second){ if(binaryPriority[ope.first->ope] > maxPriority || binaryPriority[ope.first->ope] == maxPriority && !binaryAssociativity[ope.first->ope]){ stk.push(ope); break; } ope.first->right = right.first; ope.first->left = stk.top().first; ope.second = true; right = ope; stk.pop(); }else if(isUnaryOpe[ope.first->ope]){ ope.first->right = right.first; ope.second = true; right = ope; }else{ stk.push(ope); break; } } bool ret = (stk.top().first == NULL); stk.push(right); return ret; } public: // binaryOpe : 二項演算子(優先順位の高い順に並べる。secondは結合規則を表し、trueならば左から右に結合) // unaryOpe : 単項演算子(前置演算子のみ対応) syntacticAnalysis(const vector<pair<string, bool> >& binaryOpe, const string& unaryOpe) { binaryPriority.assign(128, -1); binaryAssociativity.resize(128); isUnaryOpe.assign(128, false); for(unsigned i=0; i<binaryOpe.size(); ++i){ for(unsigned j=0; j<binaryOpe[i].first.size(); ++j){ binaryPriority[binaryOpe[i].first[j]] = i; binaryAssociativity[binaryOpe[i].first[j]] = binaryOpe[i].second; } } for(unsigned i=0; i<unaryOpe.size(); ++i) isUnaryOpe[unaryOpe[i]] = true; } Node* makeTree(const string& s) { int n = s.size(); int i = 0; stk.push(make_pair((Node*)NULL, false)); while(i < n){ if(s[i] == '('){ stk.push(make_pair((Node*)NULL, false)); ++ i; }else if(s[i] == ')'){ if(!calc(INT_MAX) || stk.size() == 2){ deleteAllNodes(); return NULL; } pair<Node*, bool> node = stk.top(); stk.pop(); stk.pop(); stk.push(node); ++ i; }else if(binaryPriority[s[i]] != -1 || isUnaryOpe[s[i]]){ calc(binaryPriority[s[i]]); Node* node = new Node; node->ope = s[i]; stk.push(make_pair(node, false)); ++ i; }else{ Node* node = new Node; while(i < n && s[i] != '(' && s[i] != ')' && binaryPriority[s[i]] == -1 && !isUnaryOpe[s[i]]){ node->s += s[i]; ++ i; } stk.push(make_pair(node, true)); } } if(!calc(INT_MAX) || stk.size() != 2){ deleteAllNodes(); return NULL; }else{ Node* ret = stk.top().first; stk.pop(); stk.pop(); return ret; } } }; int solve(const Node* node) { if(node->ope == '+') return solve(node->left) + solve(node->right); else if(node->ope == '-') return solve(node->left) - solve(node->right); else return stoi(node->s); } int main() { string s; cin >> s; syntacticAnalysis sa({make_pair("+-", true)}, ""); Node* node = sa.makeTree(s); cout << solve(node) << endl; delete node; return 0; }