Cod sursa(job #1134255)

Utilizator toncuvasileToncu Vasile toncuvasile Data 6 martie 2014 12:03:39
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.81 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,unsigned int &);
int operatie(int,int,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;

    int A[100000];

    string canonical=getCanonicalForm(E,A);
    string polish=getPostfixPolish(canonical);
    outFile<<evaluate(polish,A);
}

string getCanonicalForm(string E, int A[]){
    string aux="";
    unsigned 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,unsigned 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( unsigned 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<int> st;
    int l=0;
    for(unsigned int i=0;i<S.size();i++){
        if(S[i]=='o') st.push(A[l++]);
        else{
            int x=st.top();
            st.pop();
            int y=st.top();
            st.pop();
            st.push( operatie(x,y,S[i]) );
        }
    }

    return st.top();
}

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