Cod sursa(job #3352482)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 28 aprilie 2026 11:04:15
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.9 kb
#include <fstream>
#include <cstring>
#include <cstdint>

using namespace std;

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

const int LMAX = 100005;

char expr[LMAX + 1];

template<typename T>
struct Node
{
    T inf;
    Node *next;
    Node(): inf(0), next(NULL) {}
};

template<typename T>
struct Stack
{
    Node<T> *top;
    Stack(): top() {}
    void Push(T x)
    {
        if(top == NULL)
        {
            top = new Node<T>;
            top->inf = x;
            top->next = NULL;
            return;
        }
        Node<T> *node = new Node<T>;
        node->inf = x;
        node->next = top;
        top = node;
    }
    void Pop()
    {
        Node<T> *node = top;
        top = top->next;
        delete node;
    }
    inline T Top()
    {
        return top == NULL ? 0 : top->inf;
    }
    inline bool Empty()
    {
        return top == NULL;
    }
    friend ostream& operator << (ostream& out, const Stack<T>& stack)
    {
        Node<T> *crt = stack.top;
        while(crt != NULL)
        {
            out << crt->inf << ' ';
            crt = crt->next;
        }
        return out;
    }
};

inline bool Operator(char ch)
{
    return (ch == '*' || ch == '/' || ch == '+' || ch == '-');
}

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

void Process(Stack<int64_t>& st, Stack<char>& op)
{
    char ch = op.Top(); op.Pop();
    int64_t right = st.Top(); st.Pop();
    int64_t left = st.Top(); st.Pop();
    switch(ch)
    {
    case '*':
        st.Push(left * right);
        break;
    case '/':
        st.Push(left / right);
        break;
    case '+':
        st.Push(left + right);
        break;
    case '-':
        st.Push(left - right);
        break;
    }
}

int64_t Evaluate(char expr[LMAX + 1])
{
    Stack<int64_t> st;
    Stack<char> op;
    for(char *crt = expr; *crt != '\0'; )
    {
        if(*crt == ' ') crt++;
        else if(*crt == '(')
        {
            op.Push('(');
            crt++;
        }
        else if(Operator(*crt))
        {
            while(!op.Empty() && Priority(op.Top()) >= Priority(*crt))
                Process(st, op);
            op.Push(*crt);
            crt++;
        }
        else if(*crt == ')')
        {
            while(!op.Empty() && op.Top() != '(')
                Process(st, op);
            crt++;
            op.Pop();
        }
        else
        {
            int64_t val = 0;
            while(isdigit(*crt))
            {
                val = val * 10 + (*crt - '0');
                crt++;
            }
            st.Push(val);
        }
    }
    while(!op.Empty())
        Process(st, op);
    return st.Top();
}

int main()
{
    f.getline(expr, LMAX + 1);
    g << Evaluate(expr) << '\n';
    return 0;
}