Cod sursa(job #1438841)

Utilizator stefanzzzStefan Popa stefanzzz Data 20 mai 2015 23:20:55
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <assert.h>
#define MAXS 110000
using namespace std;

struct pol_oper {
    int val;
    char op;

    pol_oper(): val(0), op('$') {}
    pol_oper(char c): val(0), op(c) {}
};

pol_oper pol[MAXS];
char pr[256];
char expr[MAXS];
int n, cnt, lg;
vector<char> op;
vector<int> v;

pol_oper get_int() {
    pol_oper ans;
    
    while(expr[cnt] >= '0' && expr[cnt] <= '9')
        ans.val = ans.val * 10 + expr[cnt++] - '0';
    cnt--;
    return ans;
}

int result(int a, int b, char op) {
    switch(op) {
        case '+':
            return a + b; break;
        case '-':
            return a - b; break;
        case '*':
            return a * b; break;
        default:
            return a / b;
    }
}

int main() {
    freopen("evaluare.in", "r", stdin);
    freopen("evaluare.out", "w", stdout);

    scanf("%s\n", expr);
    lg = strlen(expr);

    pr['+'] = pr['-'] = 1;
    pr['*'] = pr['/'] = 2;

    for(cnt = 0; cnt < lg; cnt++) {
        if(expr[cnt] >= '0' && expr[cnt] <= '9') {
            pol[++n] = get_int();
            continue;
        }

        if(expr[cnt] == '(') {
            op.push_back('(');
            continue;
        }

        if(expr[cnt] == ')') {
            while(op.back() != '(') {
                pol[++n] = pol_oper(op.back());
                op.pop_back();
            }
            op.pop_back();
            continue;
        }

        while(!op.empty() && pr[op.back()] >= pr[expr[cnt]]) {
            pol[++n] = pol_oper(op.back());
            op.pop_back();
        }
        op.push_back(expr[cnt]);
    }
    while(!op.empty()) {
        pol[++n] = pol_oper(op.back());
        op.pop_back();
    }

    for(int i = 1; i <= n; i++) {
        if(strchr("+-*/", pol[i].op) == NULL)
            v.push_back(pol[i].val);
        else {
            int y = v.back(); v.pop_back();
            int x = v.back(); v.pop_back();
            v.push_back(result(x, y, pol[i].op));
        }
    }

    assert(v.size() == 1);
    printf("%d\n", v.back());
    return 0;
}