Cod sursa(job #977323)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 25 iulie 2013 17:11:02
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <string>
#include <sstream>
#include <cctype>
#include <stack>
using namespace std;

inline short prec(char c){
    if(c=='+'||c=='-') return 1;
    else if(c=='*'||c=='/') return 2;
    else return 0;
}

void calc(char c,stack<int> &results){
    int a=results.top();
    results.pop();
    int b=results.top();
    results.pop();
    switch(c){
        case '+': results.push(b+a); break;
        case '-': results.push(b-a); break;
        case '*': results.push(b*a); break;
        case '/': results.push(b/a); break;
    }
}

int evaluate(istream &in){ //idee bazata pe Shunting_yard algorithm(Edsger Dijkstra)
    stack<int> results;
    stack<char> op_stack;

    char c;
    bool prev_nr_lp=false,nextneg=false;
    while(in.get(c)){
        if(c>='0'&&c<='9'){
            in.putback(c);
            int value=-1;
            in>>value;
            results.push(nextneg?-value:value);
            prev_nr_lp=true;
            nextneg=false;
        }
        else if(c=='*'||c=='/'||c=='+'||c=='-'){
            if(c=='-'&&(!prev_nr_lp)) nextneg=true;
            else if(c!='+'||prev_nr_lp){
                while(!op_stack.empty()&&op_stack.top()!='('&&prec(c)<=prec(op_stack.top())){
                    calc(op_stack.top(),results);
                    op_stack.pop();
                }
                op_stack.push(c);
            }
            prev_nr_lp=false;
        }
        else if(c=='('){
            op_stack.push('(');
            prev_nr_lp=false;
        }
        else if(c==')'){
            while(op_stack.top()!='('){
                calc(op_stack.top(),results);
                op_stack.pop();
            }
            op_stack.pop();
            prev_nr_lp=true;
        }
    }
    while(!op_stack.empty()){
        calc(op_stack.top(),results);
        op_stack.pop();
    }

    return results.top();
}

int main(){
    ifstream fin("evaluare.in");
    ofstream fout("evaluare.out");

    string s; fin>>s;
    istringstream sin(s);

    fout<<evaluate(sin)<<'\n';

    return 0;
}