Cod sursa(job #1153506)

Utilizator mihai995mihai995 mihai995 Data 25 martie 2014 15:37:32
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <fstream>
#include <cstring>
using namespace std;

const int N = 100000, charSize = 256;
const char stopLabel = 0, _digit = 50;

template<class Type>
class Stack{
    Type v[N];
    int size;

public:
    Stack(){
        size = 0;
    }

    void push(Type X){
        v[size++] = X;
    }

    Type top(){
        return v[size - 1];
    }

    int pop(){
        return v[--size];
    }

    bool isEmpty(){
        return size == 0;
    }

    void clear(){
        size = 0;
    }
};

class Evaluator{
    Stack<int> vals;
    Stack<char> ops;
    unsigned char priority[charSize];

    inline void evaluate(){
        int b = vals.pop(), a = vals.pop();
        char op = ops.pop();

        if (op == '+')
            vals.push(a + b);
        if (op == '-')
            vals.push(a - b);
        if (op == '*')
            vals.push(a * b);
        if (op == '/')
            vals.push(a / b);
    }

    void pushOperator(char c){
        if ( c == '(' )
            ops.push(stopLabel);
        else if ( c == ')' ){
            while ( ops.top() != stopLabel )
                evaluate();
            ops.pop();
        } else {
            while ( priority[ c ] <= priority[ ops.top() ] )
                evaluate();
            ops.push(c);
        }
    }

public:
    Evaluator(){
        memset(priority, 0, sizeof(priority));
        priority[stopLabel] = 0;
        priority['+'] = 1;
        priority['-'] = 1;
        priority['*'] = 2;
        priority['/'] = 2;

        for (char c = '0' ; c <= '9' ; c++)
            priority[c] = _digit;
    }

    int evaluate(char* s){
        char* poz = s;
        vals.clear();
        ops.clear();

        pushOperator('(');
        while (*poz)
            if ( priority[*poz] != _digit ){
                pushOperator(*poz);
                poz++;
            } else {
                int nr = 0;
                while ( priority[*poz] == _digit ){
                    nr = nr * 10 + *poz - '0';
                    poz++;
                }
                vals.push(nr);
            }
        pushOperator(')');

        return vals.top();
    }
};

int main(){
    Evaluator E;
    char s[N + 1];

    ifstream in("evaluare.in");
    in >> s;
    in.close();

    ofstream out("evaluare.out");
    out << E.evaluate(s) << '\n';
    out.close();

    return 0;
}