#include #include #include #include #include #include #include #include using namespace std; struct lexem { string lex; string type; }; struct value { int decimal; bool is_bool; }; queue split_to_lexems(string input) { queue series; string lex; int dgt=0,opr=0,bl=0,min=0; for(int i=0;i1 && lex[0]=='-') { min=1; lex.erase(0,1); l.lex=lex; series.push(l); } else if (lex.length()>1 && lex[lex.length()-1]=='-') { min=1; lex.erase(lex.length()-1,1); l.lex=lex; series.push(l); } else { l.lex = lex; series.push(l); } lex.clear(); i-=1; } else { lex+=input[i]; } } else if(bl) { string t="True",f="False",nl=lex+input[i]; if (t.find(nl)==0 || f.find(nl)==0) { lex=nl; if (nl==t || nl==f) { bl=0; lexem l; if (nl==t) l.lex="1"; else if (nl==f) l.lex="0"; l.type="bool"; series.push(l); lex.clear(); } } else throw "Parse error near symbol #"+i; } } if (lex.length()) { lexem l; l.lex = lex; if (dgt) { l.type="number"; if (min) l.lex="-"+l.lex; } else if(opr) l.type="operation"; else l.type="bracket"; series.push(l); } // Print parsed input and exit (uncomment for debug only) /*while (series.size()) { cout << series.front().lex << " "; series.pop(); } cout << endl; assert(0);*/ return series; } queue to_postfix(queue series) { map prior; // Functions priorities are desctibed here. // Function with highest priority has least prior value // (well, that is not comfortable but very usefull when evaluating). prior["+"]=2; prior["-"]=2; prior["*"]=4; prior["/"]=4; prior["^"]=5; prior[">"]=1; prior["<"]=1; prior[">="]=1; prior["<="]=1; prior["<>"]=1; prior["and"]=0; prior["or"]=0; prior["not"]=3; queue output; stack stk; while(series.size()) { if (series.front().type=="number") { output.push(series.front()); series.pop(); } else if (series.front().type=="bool") { output.push(series.front()); series.pop(); } else if (series.front().type=="bracket") { if (series.front().lex=="(") { stk.push(series.front()); series.pop(); } else if (series.front().lex==")") { while (!(stk.top().type=="bracket")) { output.push(stk.top()); stk.pop(); } stk.pop(); series.pop(); } } else if (series.front().type=="operation") { while (!stk.empty() && prior[stk.top().lex]>=prior[series.front().lex] && stk.top().type=="operation") { output.push(stk.top()); stk.pop(); } stk.push(series.front()); series.pop(); } else series.pop(); } while (!stk.empty()) { output.push(stk.top()); stk.pop(); } return output; } // Here is description of all functions that are allowed by syntax. // All functions must have two int operands and int return value. // This is required becouse boolean type is handled by value type, // not by value data type. int add(int a, int b) { return a+b; } int sub(int a, int b) { return a-b; } int fdiv(int a, int b) { return a/b; } int mul(int a, int b) { return a*b; } int ipow(int a, int b) { return (int)pow(a,b); } int gt(int a, int b) { return a>b; } int lt(int a, int b) { return a=b; } int lte(int a, int b) { return a<=b; } int ltgt(int a, int b) { return a!=b; } int and_(int a, int b) { return a && b; } int or_(int a, int b) { return a || b; } int not_(int a, int b) { return !b; } struct oper { int (*func)(int,int); int arn; bool bool_out; bool bool_in; }; oper make_func(int(*func)(int,int), int arn, bool bool_in, bool bool_out) // Helper function to create function description structure. { oper res = {func, arn, bool_out, bool_in}; return res; } value calc(string input) { map ops; // Functions array // Here all functions must be described to be evalueted. // Format: // ops["function"] = make_func( function name, number of operands, // requires boolean input, returns boolean ); ops["+"] = make_func(add, 2, false, false); ops["-"] = make_func(sub, 2, false, false); ops["/"] = make_func(fdiv, 2, false, false); ops["*"] = make_func(mul, 2, false, false); ops["^"] = make_func(ipow, 2, false, false); ops[">"] = make_func(gt, 2, false, true); ops["<"] = make_func(lt, 2, false, true); ops[">="] = make_func(gte, 2, false, true); ops["<="] = make_func(lte, 2, false, true); ops["<>"] = make_func(ltgt, 2, false, true); ops["and"] = make_func(and_, 2, true, true); ops["or"] = make_func(or_, 2, true, true); ops["not"] = make_func(not_, 1, true, true); queue series = to_postfix(split_to_lexems(input)); stack result; while (series.size()) { if (series.front().type=="number") { value val; val.decimal = atoi(series.front().lex.c_str()); val.is_bool = false; result.push(val); series.pop(); } if (series.front().type=="bool") { value val; val.decimal = atoi(series.front().lex.c_str()); val.is_bool = true; result.push(val); series.pop(); } else if (series.front().type=="operation") { if (result.empty()) throw "Syntax error 1"; value op1 = result.top(); result.pop(); value op2; if (ops[series.front().lex].arn==2) { if (result.empty()) throw "Syntax error 2"; op2 = result.top(); result.pop(); } else { op2.decimal=0; op2.is_bool=0; } if ( ((ops[series.front().lex].bool_in == ((op1.is_bool) && (op2.is_bool)) ) && (op1.is_bool == op2.is_bool) ) || ( ops[series.front().lex].arn==1 && op1.is_bool==ops[series.front().lex].bool_in )) { value val; //cout << op2.decimal << " " << op1.decimal << endl; val.decimal = ops[series.front().lex].func(op2.decimal, op1.decimal); val.is_bool=ops[series.front().lex].bool_out; result.push(val); series.pop(); } else throw "Type error"; } } if (result.size()>1) throw "Wrong syntax"; return result.top(); } int main() { string input; while (getline(cin,input)) { try { cout << calc(input).decimal << endl; } catch (const char * e) { cout << e << endl; } } }