Cod sursa(job #2274889)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 2 noiembrie 2018 17:17:34
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
const int MAX_SIZE = 100002;

int values[MAX_SIZE];
char expression[MAX_SIZE];
char postfix[2 * MAX_SIZE];
char stack[MAX_SIZE];

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

int precedence(char ch){
    if(ch == '*' || ch == '/')
        return 1;
    if(ch == '+' || ch == '-')
        return 0;
    return -1; /// ch == '('
}

void getPostfix(){
    int len = strlen(expression), h = 0, size = 0, prec;
    char ch;
    postfix[size++] = '0';
    for(int i=0;i<len;i++){
        ch = expression[i];

        if(isDigit(ch))
            postfix[size++] = ch;

        else if(ch == '(')
            stack[++h] = '(';

        else if(ch == ')'){
            while(h > 0 && stack[h] != '(')
                postfix[size++] = stack[h--];
            if(stack[h] == '(')
                h--;
        }

        else{
            prec = precedence(ch);
            postfix[size++] = ' ';
            while(h > 0 && prec <= precedence(stack[h]))
                postfix[size++] = stack[h--];
            stack[++h] = ch;
        }

    }

    while(h > 0)
        postfix[size++] = stack[h--];
}

int getResult(int a, int b, char ch){
    switch(ch){
        case '+' : return a + b;
        case '-' : return a - b;
        case '*' : return a * b;
        case '/' : return a / b;
        default : return 0;
    }
}

int getValue(int &pos, int len){
    int result = 0;
    while(pos < len && isDigit(postfix[pos]))
        result = result * 10 + (postfix[pos++] - '0');
    return result;
}

int evaluate(){
    int len = strlen(postfix), h = 0, a, b, num, pos = 0;
    char ch;
    while(pos < len){
        ch = postfix[pos];

        if(ch == ' ')
            pos++;

        else if(isDigit(ch)){
            num = getValue(pos,len);
            values[++h] = num;
        }

        else{
            a = values[h--];
            b = values[h--];
            values[++h] = getResult(b,a,ch);
            pos++;
        }

    }
    return values[1];
}
int main()
{
    in.getline(expression,MAX_SIZE,'\n');
    in.close();
    getPostfix();
    out<<evaluate()<<"\n";
    out.close();
    return 0;
}