結果
問題 | No.708 (+ー)の式 |
ユーザー |
|
提出日時 | 2018-06-29 22:34:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,128 bytes |
コンパイル時間 | 1,424 ms |
コンパイル使用メモリ | 123,216 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 23:59:09 |
合計ジャッジ時間 | 2,101 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#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);elsereturn 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;}