Cod sursa(job #2866785)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 9 martie 2022 23:16:43
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.01 kb
#include <bits/stdc++.h>

using namespace std;

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

struct element
{
    int val;
    bool op;
    element()
    {

    }
    element(int val,bool op)
    {
        this->val=val;
        this->op=op;
    }
};

bool isop(char c)
{
    return c=='+'||c=='-'||c=='/'||c=='*'||c=='('||c==')';
}

int priority(element e)
{
    if(!e.op)return 0;
    if(e.val=='('||e.val==')')return 0;
    if(e.val=='+'||e.val=='-')return 1;
    if(e.val=='/'||e.val=='*')return 2;
    return 3;
}

vector<element> parse()
{
    string line;
    getline(in,line);
    int n=line.size();
    vector<element> res;
    for(int i=0;i<n;)
    {
        if(isop(line[i]))
        {
            res.push_back(element(line[i],1));
            i++;
        }
        else
        {
            int val=0;
            for(;i<n&&!isop(line[i]);i++)
            {
                val=val*10+line[i]-'0';
            }
            res.push_back(element(val,0));
        }
    }
    return res;
}

vector<element> topost(vector<element> v)
{
    stack<element> s;
    vector<element> res;
    for(auto e:v)
    {
        if(!e.op)
        {
            res.push_back(e);
        }
        else
        {
            if(e.val=='(')s.push(e);
            else if(e.val==')')
            {
                element t=s.top();
                s.pop();
                while (!(t.op&&t.val=='('))
                {
                    res.push_back(t);
                    t=s.top();
                    s.pop();
                }
            }
            else 
            {
                while(!s.empty()&&priority(s.top())>=priority(e))
            {
                res.push_back(s.top());
                s.pop();
            }
            s.push(e);
            }
        }
    }
    while(!s.empty())
    {
        res.push_back(s.top());
        s.pop();
    }
    return res;
}

struct node
{
    element e;
    node *l,*r;
    node(element e,node *l=nullptr, node *r=nullptr)
    {
        this->e=e;
        this->l=l;
        this->r=r;
    }
    int evaluate()
    {
        if(e.op)
        {
            switch (e.val)
            {
            case '+':
                return l->evaluate()+r->evaluate();
                break;
            case '-':
                return l->evaluate()-r->evaluate();
                break;
            case '*':
                return l->evaluate()*r->evaluate();
                break;
            case '/':
                return l->evaluate()/r->evaluate();
                break;
            }
        }
        else
        {
            return e.val;
        }
    }
};

node * getroot(vector<element> v)
{
    stack<node*> s;
    for(auto e:v)
    {
        if(e.op)
        {
            node* tmp1=s.top();
            s.pop();
            node* tmp2 =s.top();
            s.pop();
            s.push(new node(e,tmp2,tmp1));
        }
        else
        {
            s.push(new node(e));
        }
    }
    return s.top();
}

int main()
{
    auto v=getroot(topost(parse()));
    out<<v->evaluate();
}