Cod sursa(job #3332066)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 3 ianuarie 2026 19:41:36
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.37 kb
/// Varianta 2
#include <iostream>
#include <cstring>
#include <fstream>
#include <stack>
#include <algorithm>
using namespace std;

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

string expr;

struct nod {
    bool isOp;
    int val;
    char op;
    nod *st, *dr;
    //
    nod(char ii) : isOp(true), op(ii), st(NULL), dr(NULL) {}
    nod(int vv) : isOp(false), val(vv), st(NULL), dr(NULL) {}
};

nod *Arb;

int rang(char c) {
    if(c == '*' || c == '/') return 2;
    if(c == '+' || c == '-') return 1;
    return 0;
}

void buildSubTree(stack<nod*> &Noduri, stack<char> &Operatori) {
    char op = Operatori.top();
    Operatori.pop();
    //
    nod *operand1 = Noduri.top(); Noduri.pop();
    nod *operand2 = Noduri.top(); Noduri.pop();
    //
    nod *r = new nod(op);
    r->st = operand2;
    r->dr = operand1;
    //
    Noduri.push(r);
}

nod* buildTree() {
    stack<nod*> Noduri;
    stack<char> Operatori;
    //
    int len = expr.size();
    for (int i=0; i<len; i++) {
        //
        if(isdigit(expr[i])) {
            int val = 0;
            //
            while(i < len && isdigit(expr[i])) {
                val = val * 10 + expr[i] - '0';
                i++;
            }
            //
            i--;
            Noduri.push(new nod(val));
        } else if (expr[i] == '(')
            Operatori.push(expr[i]);
        else if (expr[i] == ')') {
            while(!Operatori.empty() && Operatori.top() != '(')
                buildSubTree(Noduri, Operatori);
            Operatori.pop();
        } else {
            while(!Operatori.empty() && rang(Operatori.top()) >= rang(expr[i]))
                buildSubTree(Noduri, Operatori);
            Operatori.push(expr[i]);
        }
    }
    //
    while(!Operatori.empty())
        buildSubTree(Noduri, Operatori);
    //
    return Noduri.top();
}

int evaluare(nod *r) {
    if(!r->isOp) return r->val;
    //
    switch(r->op) {
        case '+': return evaluare(r->st) + evaluare(r->dr);
        case '-': return evaluare(r->st) - evaluare(r->dr);
        case '*': return evaluare(r->st) * evaluare(r->dr);
        case '/': return evaluare(r->st) / evaluare(r->dr);
    }
    return 0;
}

int main(){
    f >> expr;
    Arb = buildTree();
    //
    g << evaluare(Arb);
    //
    f.close();
    g.close();
    return 0;
}