Cod sursa(job #1214237)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 29 iulie 2014 21:04:25
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.83 kb
#include <cstdio>
using namespace std;
class Stack
{
private:
    char s[50000];
    int top;
public:
    Stack(){};
    Stack(int newTop):top(newTop){}
    void pop() {--top;}
    void push(char c)
    {
        ++top;
        this->s[top]=c;
    }
    bool isEmpty()
    {
        if(top>0) return 0;
        return 1;
    }
    char Top() { return s[top]; }
    void emptyStack() { top=0; }
};
 
typedef struct nod
{
    nod *left,*right;
    char op;
    long val;
    nod(long _val=0,char _op=' '):val(_val),op(_op){};
}NOD;
 
typedef struct{nod* v[100001];int top;} NodeStack;
 
bool isOperator(char c)
{
    return (c=='+' || c=='-' || c=='*' || c=='/');
}
 
int priority(char c)
{
    int pri=0;
    if(c=='+' || c=='-') pri=1;
    else if(c=='*' || c=='/') pri=2;
    return pri;
}
 
NOD* pop(NodeStack &s) { NOD * n=s.v[s.top];--s.top; return n;}
 
void push(NodeStack &s,NOD *p) { s.v[++s.top]=p;}
 
long calculus(long a,long b,char c)
{
    switch(c)
    {
        case '+': return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
    }
}
 
long st[100001],m;
void evaluate(NOD *root)
{
    long calc;
    if(root!=NULL)
    {
        evaluate(root->left);
        evaluate(root->right);
        if(root->op==' ') st[++m]=root->val;
        else
        {
            long a,b;
            a=st[m];--m;
            b=st[m];--m;
            calc=calculus(b,a,root->op);
            st[++m]=calc;
        }
    }
}
int main()
{
    FILE *f,*g;
    f=fopen("evaluare.in","r");
    g=fopen("evaluare.out","w");
    char s[100002],postfix[200002];
    int i,length,neg,p=0;
    long rez=0,nr=0;
    length=fread(s,sizeof(char),100002,f);
    Stack stack(0);
    for(i=0;i<length;++i)
    {
        if(s[i]>='0' && s[i]<='9')
        {
            postfix[p++]=s[i];
            while(s[i+1]>='0' && s[i+1]<='9')
            {
                ++i;
                postfix[p++]=s[i];
            }
            postfix[p++]=' ';
        }
        else if(s[i]=='(') stack.push(s[i]);
        else if(s[i]==')')
        {
            while(stack.Top()!='(')
            {
                postfix[p++]=stack.Top();
                postfix[p++]=' ';
                stack.pop();
            }
            stack.pop();
        }
        else if(isOperator(s[i]))
        {
            if(stack.isEmpty())
            {
                stack.push(s[i]);
            }
            else
            {
                while(priority(stack.Top())>=priority(s[i]))
                {
                    postfix[p++]=stack.Top();
                    postfix[p++]=' ';
                    stack.pop();
                }
                stack.push(s[i]);
            }
        }
    }
    while(!stack.isEmpty()) {postfix[p++]=stack.Top();postfix[p++]=' ';stack.pop();}
    postfix[p]='\0';
    NodeStack nstack;
    nstack.top=0;
    for(i=0;i<p;++i)
    {
        if(postfix[i]>='0' && postfix[i]<='9')
        {
            while(postfix[i]!=' ')
            {
                nr=nr*10+postfix[i]-'0';
                ++i;
            }
            if(neg==1) nr=nr*(-1);
            NOD *newN=new nod;
            newN->left=NULL;
            newN->right=NULL;
            newN->val=nr;
            push(nstack,newN);
            nr=0;
            neg=0;
        }
        else if(isOperator(postfix[i]))
        {
            NOD *op1,*op2;
            op1=pop(nstack);
            op2=pop(nstack);
            NOD *newN=new nod;
            newN->left=op2;
            newN->right=op1;
            newN->op=postfix[i];
            push(nstack,newN);
        }
    }
    NOD *root=pop(nstack);
    stack.emptyStack();
    evaluate(root);
    fprintf(g,"%ld",st[m]);
    fclose(f);
    fclose(g);
    return 0;
}