Cod sursa(job #1328862)

Utilizator radarobertRada Robert Gabriel radarobert Data 28 ianuarie 2015 20:38:17
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.64 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

struct element
{
    char type;
    union value
    {
        char op;
        int nr;
    } val;
};

struct node
{
    element elem;
    struct node *left, *right;
};

stack<node*> stn;
stack<char> st;
vector<element> infix, postfix;
short priority[257];

bool isoperator (char x)
{
    if (x == '+' || x == '-' || x == '*' || x == '/' || x == '%')
        return true;
    return false;
}

bool isoperand (char x)
{
    if (x >= '0' && x <= '9')
        return true;
    return false;
}

void infix2postfix()
{
    element t;
    for (unsigned i = 0; i < infix.size(); ++i)
    {
        if (infix[i].type == '0')
        {
            t.type = '0';
            t.val.nr = infix[i].val.nr;
            postfix.push_back(t);
            continue;
        }
        if (infix[i].type == '(')
        {
            st.push('(');
            continue;
        }
        if (infix[i].type == ')')
        {
            while (!st.empty() && st.top() != '(')
            {
                t.type = 'o';
                t.val.op = st.top();
                st.pop();
                postfix.push_back(t);
            }
            st.pop();
            continue;
        }
        if (infix[i].type == 'o')
        {
            t.type = 'o';
            if (!st.empty())
            {
                while (!st.empty() && priority[(int)st.top()] >= priority[(int)infix[i].val.op])
                {
                    t.val.op = st.top();
                    st.pop();
                    postfix.push_back(t);
                }
            }
            st.push(infix[i].val.op);
        }
    }

    while (!st.empty())
    {
        t.type = 'o';
        t.val.op = st.top();
        st.pop();
        postfix.push_back(t);
    }
}

node *top()
{
    node *n;
    if (stn.empty())
        return NULL;
    n = stn.top();
    stn.pop();
    return n;
}

node * expr2tree ()
{
    node *op1, *op2, *newnode;
    for (unsigned i = 0; i < postfix.size(); ++i)
    {
        if (postfix[i].type == '0')
        {
            newnode = new node;
            newnode -> elem.type = '0';
            newnode -> elem.val.nr =  postfix[i].val.nr;
            newnode -> left = NULL;
            newnode -> right = NULL;
            stn.push(newnode);
        }
        else
        {
            op1 = top();
            op2 = top();
            newnode = new node;
            newnode -> elem.type = 'o';
            newnode -> elem.val.op = postfix[i].val.op;
            newnode -> left = op2;
            newnode -> right = op1;
            stn.push(newnode);
        }
    }

    return stn.top();
}

int evaluateTree (node *n)
{
    if (n == NULL)
        return 0;
    if (n -> elem.type == 'o')
    {
        int op1 = evaluateTree(n->left);
        int op2 = evaluateTree(n->right);
        switch (n -> elem.val.op)
        {
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            return op1 / op2;
        }
    }
    return n -> elem.val.nr;
}

void string2expr (string s)
{
    char *p = &s[0];
    element t;
    while (*p != 0 && *p != '\n')
    {
        if (isoperand(*p))
        {
            int x = *p - '0';
            ++p;
            while (isoperand(*p))
            {
                x = x * 10 + *p - '0';
                ++p;
            }
            t.type = '0';
            t.val.nr = x;
            infix.push_back(t);
        }
        if (isoperator(*p))
        {
            t.type = 'o';
            t.val.op = *p;
            infix.push_back(t);
            ++p;
        }
        if (*p == '(' || *p == ')')
        {
            t.type = *p;
            t.val.op = *p;
            infix.push_back(t);
            ++p;
        }
    }
}

void postorder (node *n)
{
    if (n == NULL)
        return;

    if (n->elem.type == 'o')
        cerr << n->elem.val.op;
    else
        cerr << n->elem.val.nr;
    postorder (n->left);
    postorder (n->right);
}

int main()
{
    ifstream in("evaluare.in");
    ofstream out("evaluare.out");

    string expr_string;
    in >> expr_string;
    string2expr(expr_string);
    expr_string.clear();

    priority['+'] = 1;
    priority['-'] = 1;
    priority['*'] = 2;
    priority['/'] = 2;
    priority['('] = 0;

    infix2postfix();
    node *root;
    root = expr2tree();

    out << evaluateTree(root) << '\n';

    return 0;
}