Cod sursa(job #1134212)

Utilizator toncuvasileToncu Vasile toncuvasile Data 6 martie 2014 10:47:09
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
// Infoarena. Arhiva Educationala. Evaluarea unei Expresii.
// http://www.infoarena.ro/problema/evaluare

#include<iostream>
#include<fstream>
#include<string>
#include<stack>
using namespace std;

string getCanonicalForm(string,long long[]);
string getPostfixPolish(string);
long long evaluate(string S,long long[]);
bool isDigit(char);
long long getNumber(string,unsigned long long &);
long long operatie(long long,long long,char);


int main(){
   // freopen("evaluare.in","r",stdin);
   // freopen("evaluare.out","w",stdout);
   ifstream inFile("evaluare.in");
   ofstream outFile("evaluare.out");

    string E,e;
    getline(inFile,E);
   // cout<<E;

    long long A[100000];

    string canonical=getCanonicalForm(E,A);
    //cout<<canonical<<endl;
    string polish=getPostfixPolish(canonical);
    //cout<<polish;
    outFile<<evaluate(polish,A);

}

string getCanonicalForm(string E,long long A[]){
    string aux="";
    unsigned long long i=0,level=0;

    while( i<E.size() ){
        if( !isDigit(E[i]) ) aux+=E[i++];
        else{
            A[level++]=getNumber(E,i);
            aux+='o';
        }
    }
    return aux;
}

bool isDigit(char c){
    return (c>='0' && c<='9');
}

long long getNumber(string E,unsigned long long &i){
    long long aux=0;
    while( isDigit(E[i]) ) aux=10*aux+(E[i++]-'0');
    return aux;
}

string getPostfixPolish(string S){
    stack<char> st;
    string p="";

    for( unsigned long long i=0;i<S.size();i++ ){
        if(S[i]=='o') p+='o';
        if(S[i]=='(') st.push('(');
        if(S[i]==')'){
            while(st.top()!='('){
                p+=st.top();
                st.pop();
            }
            st.pop();
        }
        if(S[i]=='+' || S[i]=='-'){
            if(st.empty() || st.top()=='(') st.push(S[i]);
            else{
                while( !(st.empty() || st.top()=='(') ){
                        p+=st.top();
                        st.pop();
                }
                st.push(S[i]);
            }

        }
        if(S[i]=='*' || S[i]=='/'){
            if( st.empty() || st.top()=='(' || st.top()=='+' || st.top()=='-' ) st.push(S[i]);
            else{
                while( !(st.empty() || st.top()=='(' || st.top()=='+' || st.top()=='-' ) ){
                    p+=st.top();
                    st.pop();
                }
                st.push(S[i]);
            }
        }
    }
    while(!st.empty()){
        p+=st.top();
        st.pop();
    }

    return p;
}

long long evaluate(string S,long long A[]){
    stack<long long> st;
    int l=0;
    for(unsigned long long i=0;i<S.size();i++){
        if(S[i]=='o') st.push(A[l++]);
        else{
            long long x=st.top();
            st.pop();
            long long y=st.top();
            st.pop();
            st.push( operatie(x,y,S[i]) );
        }
    }
    return st.top();
}

long long operatie(long long x,long long y,char c){
    switch(c){
        case '+': return x+y;
        case '-': return x-y;
        case '*': return x*y;
        case '/': return x/y;
    }
    return 0;
}