Cod sursa(job #1974673)

Utilizator MaligMamaliga cu smantana Malig Data 28 aprilie 2017 14:21:14
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");

#define pb push_back
#define ll long long
const int strMax = 1e5 + 5;

// se rezolva problema transformand expresia din notatie infix in notatie postfix,
// transformand expresia postfix in arbore de expresie si evaluand arborele

int N;
int prio[1<<8];
// prio[c] = precaderea operatorului c ( ( , ) , * , / , + , - )
//           (cei cu precadere mai mare se executa primii)

struct elem {
    int nr;
    char c;
    elem (int _nr = 0,char _c = '\0') {
        nr = _nr;
        c = _c;
    }
};

struct node {
    int nr;
    char c;
    node *st,*dr;
    node (int _nr = 0,char _c = '\0',node *_st = nullptr,node *_dr = nullptr) {
        nr = _nr;
        c = _c;
        st = _st;
        dr = _dr;
    }
    node (const node& other) {
        nr = other.nr;
        c = other.c;
        st = other.st;
        dr = other.dr;
    }
};
// node = un nod in arborele expresiei, reprezentat de un operator sau de un operand (daca este frunza)

int getNumber(char*,int&);
int buildPost(char*,elem*);
node buildTree(elem*,int);
int evaluate(node*);
// getNumber = return-eaza un numar din sirul de input
// buildPost = construieste expresia in forma postfixata din cea infixata, cu algoritmul shunting-yard
// buildTree = construieste arborele din expresia postfix si return-eaza radacina
// evaluate = evalueaza arborele de expresie

int main() {
    char *str = new char[strMax];
    elem *post = new elem[strMax];

    in>>(str+1);
    str[0] = '(';
    N = strlen(str);
    str[N] = ')';

    prio['('] = 1;
    prio[')'] = 2;
    prio['+'] = prio['-'] = 2;
    prio['*'] = prio['/'] = 3;

    int nrPost = buildPost(str,post);

    node root = buildTree(post,nrPost);

    out<<evaluate(&root)<<'\n';

    in.close();out.close();
    return 0;
}

int getNumber(char *str,int& i) {
    int ans = 0;
    while ('0' <= str[i] && str[i] <= '9') {
        ans = ans * 10 + (str[i++]-'0');
    }
    --i;
    return ans;
}

int buildPost(char* str,elem* post) {
    int nrPost = 0;

    stack<char> stiv;
    for (int i=0;i<=N;++i) {
        if (str[i] == '(') {
            stiv.push('(');
        }
        else if ('0' <= str[i] && str[i] <= '9') {
            int nr = getNumber(str,i);
            post[++nrPost] = elem(nr);
        }
        else {
            while (prio[stiv.top()] >= prio[str[i]]) {
                post[++nrPost] = elem(0,stiv.top());
                stiv.pop();
            }

            if (str[i] == ')') {
                stiv.pop();
            }
            else {
                stiv.push(str[i]);
            }
        }
    }
    return nrPost;
}


node buildTree(elem* post,int nrPost) {

    stack<node> aux;
    for (int i=1;i<=nrPost;++i) {
        if (post[i].c == '\0') {
            node n(post[i].nr);
            aux.push(n);
        }
        else {
            node *n1,*n2,dad;
            n1 = new node(aux.top()); aux.pop();
            n2 = new node(aux.top()); aux.pop();
            dad = node(0,post[i].c,n2,n1);

            aux.push(dad);
        }
    }

    return aux.top();
}

int evaluate(node *n) {

    switch (n->c) {
    case '+': return evaluate(n->st) + evaluate(n->dr);
    case '-': return evaluate(n->st) - evaluate(n->dr);
    case '*': return evaluate(n->st) * evaluate(n->dr);
    case '/': return evaluate(n->st) / evaluate(n->dr);
    default: return n->nr;
    }
}