Cod sursa(job #2180692)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 21 martie 2018 01:48:15
Problema Evaluarea unei expresii Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <bits/stdc++.h>

using namespace std;

const int NMax = 100005;
ifstream f("evaluare.in");
ofstream g("evaluare.out");

struct NODE{
    int op;
    int key;
    struct NODE *leftC, *rightC;
};

char x[NMax];
NODE * root;
stack<char> st;
vector<pair<int,int> > ans;
stack<NODE *> node_stack;

int eval(NODE *node){
    if(node->op == '+'){
        return eval(node->leftC) + eval(node->rightC);
    }
    if(node->op == '-'){
        return eval(node->leftC) - eval(node->rightC);
    }
    if(node->op == '*'){
        return eval(node->leftC) * eval(node->rightC);
    }
    if(node->op == '/'){
        return eval(node->leftC) / eval(node->rightC);
    }
    return node->key;
}
int main()
{
    f.getline(x,NMax);
    //g << x << '\n';
    int l = strlen(x);

    for(int i = 0; i < l; ++i){
        if(x[i] == '('){
            st.push(x[i]);
        }else
        if(x[i] == '+' || x[i] == '-'){
            while(st.top() == '/' || st.top() == '*'){
                ans.push_back({st.top(), 1});
                st.pop();
                if(st.empty()){
                    break;
                }
            }
            st.push(x[i]);
        }else
        if(x[i] == '/' || x[i] == '*'){
            st.push(x[i]);
        }else
        if(x[i] == ')'){
            while(st.top() != '('){
                ans.push_back({st.top(), 1});
                st.pop();
                if(st.empty()){
                    break;
                }
            }
            st.pop();
        }else{
            int numar = 0;
            while(x[i] >= '0' && x[i] <= '9'){
                numar = numar * 10 + x[i] - '0';
                i++;
            }
            i--;
            ans.push_back({numar, 0});
        }
    }
    while(!st.empty()){
        ans.push_back({st.top(),1});
        st.pop();
    }
    for(int i = 0; i < ans.size(); ++i){
        if(ans[i].second == 0){
            NODE *aux;
            aux = new NODE;
            aux->key = ans[i].first;
            aux->op = 0;
            aux->leftC = NULL;
            aux->rightC = NULL;

            node_stack.push(aux);
        }else{
            NODE *aux;
            aux = new NODE;
            aux->op = ans[i].first;
            aux->key = 0;
            aux->rightC = node_stack.top();
            node_stack.pop();
            aux->leftC = node_stack.top();
            node_stack.pop();

            node_stack.push(aux);

            root = aux;
        }
    }
    g << eval(root);
    return 0;
}