Cod sursa(job #3363745)

Utilizator marelucaMare Luca Ghita mareluca Data 21 august 2026 22:36:29
Problema Evaluarea unei expresii Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <bits/stdc++.h>

const int NMAX = (1 << 17);
const int LMAX = 2; 

std::string str; 
size_t idx;

char op[4][4] = { "+-", "*/", "^", "" };

struct node 
{
    int val;
    char op;
    node *l, *r;
    
    node(int _val = 0, char _op = 0, node *_l = 0, node *_r = 0) : val(_val), op(_op), l(_l), r(_r) {};
} *arb;

// Construction of the expression tree
node *expr(int lev)
{
    node *x, *y;
    
    // Treat each operation on a different level
    // 0 -> addition and subtraction
    // 1 -> multiplication and division
    // 2 -> exponentiation or, in this case, the last level
    
    if(lev == LMAX) // Reached the last level, so it's either
    {
        if(str[idx] == '(') // 1. A new expression defined by the '('
        {
            ++idx; // Skip the '('
            x = expr(0); // Evaluate the expression
            ++idx; // Skip the ')'
        }
        else // 2. A number (or a variable in other cases)
        {
            // Parsing and storing the number
            for(x = new node(); str[idx] >= '0' && str[idx] <= '9'; ++idx)
            {
                x->val = x->val * 10 + str[idx] - '0';
            }
        }
    }
    else // Still on an operator's level
    {
        // Parsing each subexpression and checking if we are 
        // at the current operator's level (loop condition)
        // We first parse through the expressions with higher
        // priority i. e. higher level (so firstly exponentiation, then multiplication, ...)
        for(x = expr(lev + 1); str[idx] && strchr(op[lev], str[idx]); x = y)
        {
            // Storing the operator with it's left
            // child as the current value, and it's right
            // as the new operator/value
            y = new node(0, str[idx], x, expr(lev + 1));
            ++idx;
        }
    }

    return x;
}

// Evaluation function

int eval(node *_arb) 
{
    switch (_arb->op)
    {
    case '+':
        return (eval(_arb->l) + eval(_arb->r)); 
        break;
    case '-':
        return (eval(_arb->l) - eval(_arb->r)); 
        break;
    case '*':
        return (eval(_arb->l) * eval(_arb->r)); 
        break;
    case '/':
        return (eval(_arb->l) / eval(_arb->r)); 
        break;
    default:
        return _arb->val; 
        break;
    }
}

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

int main()
{
    std::getline(fin, str);
    arb = expr(0);
    fout << eval(arb);
    return 0;
}