Cod sursa(job #1464232)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 22 iulie 2015 17:48:35
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.3 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("evaluare.in");
ofstream g("evaluare.out");
int N,rez,dimpolpost;
int prio[50];
char sir[100010];

struct pol {
    int nr;
    char c;
    bool e_nr;
};
pol polpost[100010]; // polpost[i]=fiecare element al formei poloneze postfixate. daca e_nr=true => avem un operand else avem un operator

struct stiva { // stiva alocata dinamic
    char val;
    stiva* next=NULL;
};
stiva* stiv;

struct nod {
    int nr;
    char c;
    bool e_nr;
    nod* right=NULL;
    nod* left=NULL;
};

struct stivanod_struct { // stiva alocata dinamic
    nod val;
    stivanod_struct* next=NULL;
};
stivanod_struct* stivanod;

bool gol();
char top();
void pop();
void push(char);
bool golnod();
nod topnod();
void popnod();
void pushnod(nod);
void determina_nr(int&,int&);
void parcurgere(nod*);

int main()
{
    f>>sir;
    N=strlen(sir);
    prio['(']=1;
    prio[')']=2;
    prio['+']=prio['-']=3;
    prio['*']=prio['/']=4;
    stiv=new stiva;
    for (int i=0;i<N;++i) {
        if (sir[i]>=48 && sir[i]<=57) {
            int nr=0;
            determina_nr(nr,i);
            polpost[++dimpolpost].nr=nr;
            polpost[dimpolpost].e_nr=true;
            --i;
        }
        else if (sir[i]=='(') {
            push('(');
        }
        else if (sir[i]==')') {
            while (top()!='(') {
                polpost[++dimpolpost].c=top();
                polpost[dimpolpost].e_nr=false;
                pop();
            }
            pop();
        }
        else {
            while (!gol() && prio[top()]>=prio[sir[i]]) {
                polpost[++dimpolpost].c=top();
                polpost[dimpolpost].e_nr=false;
                pop();
            }
            push(sir[i]);
        }
    }
    while (!gol()) {
        polpost[++dimpolpost].c=top();
        polpost[dimpolpost].e_nr=false;
        pop();
    }
    stivanod=new stivanod_struct;
    FOR (i,1,dimpolpost) { // se construieste arborele
        if (polpost[i].e_nr) {
            nod a;
            a.e_nr=true;
            a.nr=polpost[i].nr;
            pushnod(a);
        }
        else {
            nod* nod1=new nod;
            *nod1=topnod();
            popnod();
            nod* nod2=new nod;
            *nod2=topnod();
            popnod();
            nod a;
            a.e_nr=false;
            a.c=polpost[i].c;
            a.left=nod2;
            a.right=nod1;
            pushnod(a);
        }
    }
    nod* a=new nod;
    *a=topnod(); // a=pointer spre radacina arborelui
    parcurgere(a);
    g<<a->nr;
    f.close();g.close();
    return 0;
}

bool gol() {
    if (stiv->next==NULL) {
        return true;
    }
    return false;
}

char top() {
    return stiv->val;
}

void pop() {
    stiva* p=stiv;
    stiv=stiv->next;
    delete p;
}

void push(char x) {
    stiva* p=new stiva;
    p->val=x;
    p->next=stiv;
    stiv=p;
}

bool golnod() {
    if (stivanod->next==NULL) {
        return true;
    }
    return false;
}

nod topnod(){
    return stivanod->val;
}

void popnod(){
    stivanod_struct* p=stivanod;
    stivanod=stivanod->next;
    delete p;
}

void pushnod(nod x) {
    stivanod_struct* p=new stivanod_struct;
    p->val=x;
    p->next=stivanod;
    stivanod=p;
}

void determina_nr(int& nr,int& i) {
    while (sir[i]>=48 && sir[i]<=57) {
        nr=nr*10+sir[i]-48;
        ++i;
    }
}

void parcurgere(nod* x) {
    nod* l=x->left;
    nod* r=x->right;
    if (!l->e_nr) {
        parcurgere(l);
    }
    if (!r->e_nr) {
        parcurgere(r);
    }
    x->e_nr=true;
    switch (x->c) {
        case ('+'): {
            x->nr=l->nr+r->nr;
            break;
        }
        case ('-'): {
            x->nr=l->nr-r->nr;
            break;
        }
        case ('*'): {
            x->nr=l->nr*r->nr;
            break;
        }
        case ('/'): {
            x->nr=l->nr/r->nr;
            break;
        }
    }
 }