Cod sursa(job #3294759)

Utilizator EricDimiericdc EricDimi Data 27 aprilie 2025 22:08:25
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_LEN = 100'000;
const int MAX_LVL = 2; /// nivel maxim de prioritate

const char op[MAX_LVL + 1][3] = {"+-", "*/", ""};

char s[MAX_LEN + 10], *p;
/// *p este pointer la inceputul expresiei s

struct Node {
    int val;
    char op;
    Node *st;
    Node *dr;
    
    Node(int a = 0, char b = 0, Node *c = 0, Node *d = 0): val(a), op(b), st(c), dr(d) {}
} *A;
/// *A este pointer la radacina arborelui

///  expresie = termen +- termen +- ... +- termen
///  termen = factor */ factor */ ... */ factor
///  fie factor = (expresie), fie factor = constanta 
  
Node *expresie(int lvl) {
    Node *x, *y;
    
    if (lvl == MAX_LVL) {
        if (*p == '(') {
            p++;
            x = expresie(0); /// expresie de nivel 0 (E(0))
            p++;
        } else {
            for (x = new Node(); *p >= '0' && *p <= '9'; p++)
                x->val = x->val * 10 + (*p - '0');
        }
    } else {
        /// Evaluam expresia E[1](lvl + 1) op(lvl) E[2](lvl + 1) op(lvl) ...
        /// Initial, x = E[1](lvl + 1). La al i-lea operator op(lvl), avem
        ///    - x = E[1](lvl + 1) op(lvl) ... op(lvl) E[i](lvl + 1)
        ///    - y = x op(lvl) E[i + 1](lvl + 1)
        for (x = expresie(lvl + 1); strchr(op[lvl], *p); x = y) {
            char c = *p; p++;
            y = new Node(0, c, x, expresie(lvl + 1));
        }
    }
    
    return x;
}

int evaluare(Node *nod) {
    switch (nod->op) {
        case '+': return evaluare(nod->st) + evaluare(nod->dr);
        case '-': return evaluare(nod->st) - evaluare(nod->dr);
        case '*': return evaluare(nod->st) * evaluare(nod->dr);
        case '/': return evaluare(nod->st) / evaluare(nod->dr);
        default: return nod->val;
    }
}

int main() {
    ifstream f("evaluare.in");
    ofstream g("evaluare.out");
    
    f.>> s;
    int n = strlen(s);
    s[n++] = '+';
    s[n++] = '0';
    s[n] = 0;
    p = s;
    
    A = expresie(0);
    g << evaluare(A) << "\n";
    
    f.close();
    g.close();
    return 0;
}