Cod sursa(job #1512790)

Utilizator BaweeLazar Vlad Bawee Data 28 octombrie 2015 17:17:43
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define MAX 1000000005

using namespace std;

ifstream f("evaluare.in");
ofstream g("evaluare.out");

char a[100001];

struct
{
    int pr;
    int num;
    char c;
} v[100001];

struct Nod {
    int num;
    char c;
    Nod *ls;
    Nod *ld;
};

typedef Nod *PNod;

int poz;

int cauta(int a,int b){
    int minn = MAX,minni;
    for(int i = a; i <= b; i++)
        if(v[i].pr <= minn){
            minn = v[i].pr;
            minni = i;
        }
    return minni;
}

void magic(PNod &p)
{
    p -> num = 0;
    p -> c = NULL;
}

void mache(int a, int b,int poz, PNod &p)
{
    if(p)
    {
        poz = cauta(a,b);
        p = new Nod;
        magic(p);
        if(a != b) p -> c = v[poz].c;
        else p -> num = v[poz].num, p -> ls = NULL, p -> ld = NULL;

        mache(a,poz - 1,poz,p -> ls);
        mache(poz + 1,b,poz,p -> ld);
    }
}

int eval(PNod p)
{
    if(p -> c)
    {
        if(p -> c == '+') return eval(p -> ls) + eval(p -> ld);
        if(p -> c == '-') return eval(p -> ls) - eval(p -> ld);
        if(p -> c == '*') return eval(p -> ls) * eval(p -> ld);
        if(p -> c == '/') return eval(p -> ls) / eval(p -> ld);
    }
    return p -> num;
}

int main()
{
    int num,vf = 0;

    f >> a;
    int l = strlen(a);

    int p = 0;// fac vectorul de prioritati
    for(int i = 0; i < l; i++)
    {
        if(a[i] == '(') p += 10;
        else if(a[i] == ')') p -= 10;
        else
        {
            if(a[i] == '*' or a[i] == '/')
                v[++vf].pr = 10 + p, v[vf].c = a[i];
            else if(a[i] == '+' or a[i] == '-')
                v[++vf].pr = 1 + p, v[vf].c = a[i];

            else
            {
                num = 0;
                while(a[i] >= '0') num = num * 10 + a[i] - '0',i++;
                i--;
                v[++vf].pr = MAX;
                v[vf].num = num;
            }
        }
    }
    PNod r = new Nod;

    magic(r);
    mache(1,vf,0,r);

    g << eval(r);

    return 0;
}