Cod sursa(job #1134126)

Utilizator toncuvasileToncu Vasile toncuvasile Data 6 martie 2014 00:20:58
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3.07 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,int[]);
string getPostfixPolish(string);
int evaluate(string S,int[]);
bool isDigit(char);
int getNumber(string,int &);


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;

    int A[100000];

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

}

string getCanonicalForm(string E,int A[]){
    string aux="";
    int 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');
}

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

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

    for( int 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;
}

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

            st.push(y+x);
        }
        if(S[i]=='-'){
            int x=st.top();
            st.pop();
            int y=st.top();
            st.pop();

            st.push(y-x);
        }
        if(S[i]=='*'){
            int x=st.top();
            st.pop();
            int y=st.top();
            st.pop();

            st.push(y*x);
        }
        if(S[i]=='/'){
            int x=st.top();
            st.pop();
            int y=st.top();
            st.pop();

            st.push(y/x);
        }
    }

    return st.top();
}