#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 binaryPriority; // 二項演算子の優先順位(数値が小さいほど優先順位が高い。-1ならば二項演算子ではない) vector binaryAssociativity; // 二項演算子の結合規則(trueならば左から右に結合) vector isUnaryOpe; // 単項演算子 stack > stk; void deleteAllNodes() { while(!stk.empty()){ delete stk.top().first; stk.pop(); } } bool calc(int maxPriority) { if(!stk.top().second) return false; pair right = stk.top(); stk.pop(); while(stk.top().first != NULL){ pair 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 >& binaryOpe, const string& unaryOpe) { binaryPriority.assign(128, -1); binaryAssociativity.resize(128); isUnaryOpe.assign(128, false); for(unsigned i=0; i 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; }