Cod sursa(job #736106)

Utilizator BitOneSAlexandru BitOne Data 17 aprilie 2012 20:54:25
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <string>
#include <fstream>
#include <cstdlib>

using namespace std;

struct vertex
{
    char op;
    int value;
    vertex *left, *right;
    vertex(char _op=0, int _value=-1, vertex *_left=NULL, vertex *_right=NULL): op(_op), value(_value), left(_left), right(_right) {}
};

string exp;
string::const_iterator it, iend;
const string op[]={ "+-", "/*", "^" };

inline vertex* createTree(int level)
{
    int nr;
    char p;
    vertex *x, *y;
    if(2 == level)
    {
        if('(' == *it)
        {
            ++it;
            x=createTree(0);
            ++it;
        }
        else {
                for(nr=0; it < iend && *it >= '0' && *it <= '9'; ++it)
                    nr=nr*10+*it-'0';
                 x=new vertex(0, nr);
             }
    }
    else for(x=createTree(level+1); it < iend && string::npos != op[level].find(*it); x=y)
         {
            p=*it; ++it;
            y=new vertex(p, -1, x, createTree(level+1));
         }

    return x;
}
inline int eval(vertex* x)
{
    if(-1 != x->value)
      return x->value;
    switch(x->op)
    {
        case '+' : return eval(x->left) + eval(x->right);
        case '-' : return eval(x->left) - eval(x->right);
        case '*' : return eval(x->left) * eval(x->right);
        case '/' : return eval(x->left) / eval(x->right);
    }
    return -1;
}
int main()
{
    ifstream in("evaluare.in");
    ofstream out("evaluare.out");

    getline(in, exp);
    it=exp.begin(), iend=exp.end();
    out<<eval(createTree(0))<<'\n';

    return EXIT_SUCCESS;
}