Cod sursa(job #1500212)

Utilizator stefanzzzStefan Popa stefanzzz Data 11 octombrie 2015 16:59:11
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <stdio.h>
#include <vector>
#include <assert.h>
#include <stdlib.h>
#define MAXS 100020
using namespace std;

struct expr {
    char type, op;
    int nr;
};

int prior[260], n, pos;
char s[MAXS];
vector<char> v;
expr e[MAXS];

inline int computeOp(char op, int a, int b) {
    switch(op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: exit(1);
    }
}

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

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

    scanf("%s", s);
    while(s[pos] != '\0') {
        if(s[pos] >= '0' && s[pos] <= '9') {
            int x = 0;
            while(s[pos] >= '0' && s[pos] <= '9')
                x = x * 10 + s[pos++] - '0';
            e[++n].type = 'n';
            e[n].nr = x;
            continue;
        }
        if(s[pos] == ')') {
            ++pos;
            while(v.back() != '(') {
                e[++n].type = 'o';
                e[n].op = v.back();
                v.pop_back();
            }
            v.pop_back();
            continue;
        }
        if(s[pos] == '(') {
            v.push_back(s[pos++]);
            continue;
        }
        while(!v.empty() && v.back() != '(' && prior[v.back()] >= prior[s[pos]]) {
            e[++n].type = 'o';
            e[n].op = v.back();
            v.pop_back();
        }
        v.push_back(s[pos++]);
    }
    while(!v.empty()) {
        e[++n].type = 'o';
        e[n].op = v.back();
        v.pop_back();
    }

    vector<int> v;
    for(int i = 1; i <= n; i++) {
        if(e[i].type == 'n')
            v.push_back(e[i].nr);
        else {
            int x1, x2;
            x2 = v.back(); v.pop_back();
            x1 = v.back(); v.pop_back();
            v.push_back(computeOp(e[i].op, x1, x2));
        }
    }

    assert(v.size() == 1);
    printf("%d\n", v[0]);

    return 0;
}