Cod sursa(job #1093643)

Utilizator kiralalaChitoraga Dumitru kiralala Data 28 ianuarie 2014 14:21:32
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <fstream>
#include <cstring>
#include <stack>
#define NMAX 100005

using namespace std;
//expresion trees
FILE* f=freopen("evaluare.in","r",stdin);
FILE* o=freopen("evaluare.out","w",stdout);

struct Tree {
    char type;
    char op;
    int number;
    Tree *left,*right;
    Tree(char a=0, char b=0, int c=0, Tree *d=0, Tree *e=0) :
    type(a),op(b),number(c),left(d),right(e) {}
} *A;
typedef Tree * TREE;
char exp[NMAX];
int l;
stack<TREE> stk;
stack<char> op;
char sign[]="+-*/",prsign[]="*/";

void ToTree()
{
    int i;
    for(i=0;i<l;++i)
    {
        char c=exp[i];
        switch(c)
        {
            case '+':case '-':
                while(!op.empty()&&strchr(sign,op.top()))
                {
                    Tree *r=stk.top(); stk.pop();
                    Tree *l=stk.top(); stk.pop();
                    Tree *x=new Tree('o',op.top(),0,l,r);
                    op.pop();
                    stk.push(x);
                }
                op.push(c);
            break;
            case '*':case '/':
                if(!op.empty()&&strchr(prsign,op.top()))
                {
                    Tree *r=stk.top(); stk.pop();
                    Tree *l=stk.top(); stk.pop();
                    Tree *x=new Tree('o',op.top(),0,l,r);
                    op.pop();
                    stk.push(x);
                }
                op.push(c);
            break;
            case '(':
                op.push(c);
            break;
            case ')':
                while(op.top()!='(')
                {
                    Tree *r=stk.top(); stk.pop();
                    Tree *l=stk.top(); stk.pop();
                    Tree *x=new Tree('o',op.top(),0,l,r);
                    op.pop();
                    stk.push(x);
                }
                op.pop();
            break;
            default:
                int num=0;
                while(i<l&&exp[i]>='0'&&exp[i]<='9')
                    num=num*10+(exp[i++]-'0');
                i-=1;
                Tree *x=new Tree('n',0,num,0,0);
                stk.push(x);
            break;
        }
    }
    while(!op.empty())
    {
        Tree *r=stk.top(); stk.pop();
        Tree *l=stk.top(); stk.pop();
        Tree *x=new Tree('o',op.top(),0,l,r);
        op.pop();
        stk.push(x);
    }
    A=stk.top(); stk.pop();
}

int Solve(Tree x)
{
    if(x.type=='n')
        return x.number;
    switch(x.op)
    {
        case '+': return Solve(*x.left)+Solve(*x.right);
        case '-': return Solve(*x.left)-Solve(*x.right);
        case '*': return Solve(*x.left)*Solve(*x.right);
        case '/': return Solve(*x.left)/Solve(*x.right);
    }
    return 0;
}

int main()
{
    scanf("%s",exp);
    l=strlen(exp);
    ToTree();

    printf("%d",Solve(*A));

    return 0;
}