Cod sursa(job #1590905)

Utilizator ciocan_catalinCiocan Catalin - Iulian ciocan_catalin Data 5 februarie 2016 17:20:23
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.78 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <cstring>

using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
int NMAX = 100005,n,NEXT[100005];
char s[100005];
stack <int> st;
stack <int> st2;
int Eval(int St, int dr)
{
    int i,nr,x,op;
    for(i = St; i <= dr; i++)
    {
        if(s[i]>='0' && s[i]<='9')
        {
            nr = 0;
            while(s[i]>='0' && s[i]<='9')
            {
                nr = nr*10 + (s[i]-'0');
                i++;
            }
            i--;
            st.push(nr);
        }
        else if(s[i]=='(')
        {
            x = Eval(i+1,NEXT[i]);
            st.push(x);
            i = NEXT[i];
        }
        else if(s[i]=='*')
        {
            if(s[i+1]>='0' && s[i+1]<='9')
            {
                i++;
                nr = 0;
                while(s[i]>='0' && s[i]<='9')
                {
                    nr = nr*10 + (s[i]-'0');
                    i++;
                }
                i--;
                x = st.top()*nr;
                st.pop();
                st.push(x);
            }
            else if(s[i+1]=='(')
            {
                x = st.top();
                st.pop();
                nr = Eval(i+2,NEXT[i+1]);
                st.push(x*nr);
                i = NEXT[i+1];
            }
        }
        else if(s[i]=='/')
        {
            if(s[i+1]>='0' && s[i+1]<='9')
            {
                i++;
                nr = 0;
                while(s[i]>='0' && s[i]<='9')
                {
                    nr = nr*10 + (s[i]-'0');
                    i++;
                }
                i--;
                x = st.top()/nr;
                st.pop();
                st.push(x);
            }
            else if(s[i+1]=='(')
            {
                x = st.top();
                st.pop();
                nr = Eval(i+2,NEXT[i+1]);
                st.push(x/nr);
                i = NEXT[i+1];
            }
        }
        else if(s[i]=='+') st.push(-1);
        else if(s[i]=='-') st.push(-2);
    }
    while(!st.empty())
    {
        x = st.top();
        st2.push(x);
        st.pop();
    }
    x = st2.top();
    st2.pop();
    while(!st2.empty())
    {
        op = st2.top();
        st2.pop();
        nr = st2.top();
        st2.pop();
        if(op==-1) x +=nr;
        else x-=nr;
    }
    return x;
}

void Check()
{
    int i;
    for(i = 1; i <= n; i++)
    {
        if(s[i]=='(') st.push(i);
        else if(s[i]==')')
        {
            NEXT[st.top()] = i;
            st.pop();
        }
    }
}


int main()
{
    fin>>(s+1);
    n = strlen(s+1);
    Check();
    fout<<Eval(1,n);
    fout.close();
    return 0;
}