Cod sursa(job #2639577)

Utilizator vali_27Bojici Valentin vali_27 Data 2 august 2020 22:37:38
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.71 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Node{
    bool operand;
    union {
        char op;
        int nr;
    };
    Node *left,*right;

    Node(char x) : operand(false), op(x), left(nullptr), right(nullptr){}
    Node(int x)  : operand(true),  nr(x), left(nullptr), right(nullptr){}
    Node(){}
};


int precedence(char x)
{
    if(x == '^')return 3;
    else if(x == '*' || x == '/')return 3;
    else if(x == '+' || x == '-')return 1;
    return -1;
}

void delete_spaces(string &s)
{
    int n = s.size(),j=0;
    for(int i=0;i<n;++i)
        if(s[i] != ' ')s[j++] = s[i];
    s[j] = '\0';
    s.resize(j);
    s.shrink_to_fit();
}

Node* infix_to_prefix(string in)
{
    delete_spaces(in);

    in = '(' + in + ')';

    int n = in.size();

    stack <char> st;
    stack <Node*> noduri;

    for(int i=0;i<n;++i)
    {
        if(isdigit(in[i]))
        {
            string nr;
            while(i < n && isdigit(in[i]) )
            {
                nr += in[i];
                i++;
            }
            i--;
            noduri.push(new Node( stoi(nr) ) );
        }
        else
        if(in[i] == '(') st.push('(');
        else
        if(in[i] == ')')
        {
            while(!st.empty() && st.top() != '(')
            {
                Node *t = new Node(st.top());
                Node *t1 = nullptr, *t2 = nullptr;

                if(!noduri.empty())
                {
                    t1 = noduri.top();
                    noduri.pop();
                }


                if(!noduri.empty())
                {
                    t2 = noduri.top();
                    noduri.pop();
                }

                t->left = t2;
                t->right = t1;
                noduri.push(t);

                st.pop();
            }
            if(st.top() == '(')st.pop();
        }
        else
        {
            while(!st.empty() && in[i] != '^' && precedence(in[i]) <= precedence(st.top()))
            {
                Node *t = new Node(st.top());
                Node *t1 = nullptr, *t2 = nullptr;

                if(!noduri.empty())
                {
                    t1 = noduri.top();
                    noduri.pop();
                }
                if(!noduri.empty())
                {
                    t2 = noduri.top();
                    noduri.pop();
                }

                t->left = t2;
                t->right = t1;
                noduri.push(t);

                st.pop();
            }
            st.push(in[i]);
        }

    }
    return noduri.top();
}


//void inordine(Node *&root)
//{
//    if(root == nullptr)return;
//
//    if(root->left || root->right)cout << '(';
//    inordine(root->left);
//    if(root->operand == true)
//        cout << root->nr << ' ';
//    else
//        cout << root->op << ' ';
//    inordine(root->right);
//    if(root->left || root->right)cout << ')';
//}

int calcul(Node *&root)
{
    if(root->operand == true)
        return root->nr;
    else
    {
        int t1 = calcul(root->left);
        int t2 = calcul(root->right);
        switch(root->op)
        {
            case '+' : return t1 + t2;
                break;
            case '-' : return t1 - t2;
                break;
            case '*' : return t1 * t2;
                break;
            case '/' : return t1 / t2;
                break;
            case '^' : return pow(t1,t2);
                break;
        }
    }
}

int main()
{
    string in;
    getline(f,in);
    Node *root = infix_to_prefix(in);
    g << calcul(root);
    return 0;
}