Cod sursa(job #2971940)

Utilizator HandoMihnea-Vicentiu Hando Data 28 ianuarie 2023 13:11:03
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.79 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x); re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void wr(array <T, N> x);
template <class T> 
void wr(vt <T> x);

template <class T> 
void wr(T x) {
    cout << x;
}

template <class T, class ...M>  void wr(T x, M... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(vt <T> x) {
    for(auto it : x)
        wr(it, ' ');
}

template <class T, size_t N>
void wr(array <T, N> x) {
    for(auto it : x)
        wr(it, ' ');
}


inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

void solve() {
    /* The simplest way to solve the evaluation of an expression is using recursion.
        All we need to is to divide the expresion into multiple recursive functions to calculate the result, 
        for that we need to sort the operators out by their priority (important to mention that terms of the expression will have the highest priority).

        For this problem the division of functions will look like this:
        term(position i) :- get's the term that is starting from position i
        parenthesis(position i) :- goes to the lowest priority operator in the expression
        operator_mul_div(position i) :- evaluates multiplication or division of terms
        operator_add_sub(position i) :- evaluates addition or subtraction of terms
    */

    function <int(int&)> term, parenthesis, operator_mul_div, operator_add_sub;
    string s; re(s);
    s += '$';
    int p = 0;

    term = [&](int& i) {
        int nr = 0;
        while (s[i] >= '0' and s[i] <= '9') {
            nr = nr * 10 + (s[i] - '0');
            ++i;
        }
        return nr;
    };

    parenthesis = [&](int& i) {
        if (s[i] == '(') {
            ++i;
            int nr = operator_add_sub(i);
            ++i; // s[i] == ')'
            return nr;
        }

        return term(i);
    };

    operator_mul_div = [&](int& i) {
        int nr = parenthesis(i);
        while (s[i] == '*' or s[i] == '/') {
            switch (s[i]) {
                case '*': nr = nr * parenthesis(++i); break;
                case '/': nr = nr / parenthesis(++i); break;
            }
        }
        return nr;
    };

    operator_add_sub = [&](int& i) {
        int nr = operator_mul_div(i);
        while (s[i] == '+' or s[i] == '-') {
            switch (s[i]) {
                case '+': nr = nr + operator_mul_div(++i); break;
                case '-': nr = nr - operator_mul_div(++i); break;
            }
        }
        return nr;
    };

    wr(operator_add_sub(p));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("evaluare");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}