Cod sursa(job #2608769)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 1 mai 2020 18:40:43
Problema Evaluarea unei expresii Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("evaluare.in");
ofstream fout ("evaluare.out");

struct nod
{
    char op;
    int value;

    nod *st;
    nod *dr;

    nod()
    {
        op = '!';
        value = 0;
    }
};

const int N = 100005, oo = INT_MAX;
char e[N], expr[N];
int pr[N];
int n;

nod *makeTree(int lft, int rgt)
{
    int minPr = pr[lft], bestPos = lft;
    int mid = (lft + rgt) / 2;

    for (int i = lft; i <= rgt; i++)
    {
        if (minPr > pr[i])
        {
            minPr = pr[i];
            bestPos = i;
        }
        else if (minPr == pr[i])
            if (abs(mid - i) < abs(mid - bestPos))
                bestPos = i;
    }

    nod *p = new nod;
    if (minPr == oo)
    {
        p -> st = p -> dr = NULL;
        for (int i = lft; i <= rgt; i++)
            p -> value = p -> value * 10 + (expr[i] - '0');
    }
    else
    {
        p -> op = expr[bestPos];

        p -> st = makeTree(lft, bestPos - 1);
        p -> dr = makeTree(bestPos + 1, rgt);
    }

    return p;
}


int eval(nod *p)
{
	switch(p -> op)
	{
		case '+': return eval(p -> st) + eval(p -> dr);
		case '-': return eval(p -> st) - eval(p -> dr);
		case '*': return eval(p -> st) * eval(p -> dr);
		case '/': return eval(p -> st) / eval(p -> dr);
		default: return p -> value;
	}
}

int main()
{
    fin >> (e + 1);

    int val = 0;
    for (int i = 1; e[i]; i++)
    {
        pr[i] = oo;
        switch(e[i])
        {
            case '(':
                val += 10;
                break;
            case ')':
                val -= 10;
                break;
            case '+':
                pr[i] = val + 1;
                break;
            case '-':
                pr[i] = val + 1;
                break;
            case '*':
                pr[i] = val + 5;
                break;
            case '/':
                pr[i] = val + 5;
                break;
            case '%':
                pr[i] = val + 5;
                break;
        }

    }


    for (int i = 1; e[i]; i++) ///expresia fara paramteze
    {
        if (e[i] != '(' && e[i] != ')')
        {
            expr[++n] = e[i];
            pr[n] = pr[i];
        }
    }

    nod *p = makeTree(1, n);
    fout << eval(p);

    return 0;
}