Cod sursa(job #879180)

Utilizator dan.lincanDan Lincan dan.lincan Data 15 februarie 2013 02:23:18
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.75 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <stack>

using namespace std;

struct node
{
    enum NodeType
    {
        Operator,
        Operand
    };

    NodeType Type;
    union
    {
        char Operator;
        long Operand;
    } Value;

    node(char Operator)
    {
        Type = node::Operator;
        this->Value.Operator = Operator;
    }

    node(long Operand)
    {
        Type = node::Operand;
        this->Value.Operand = Operand;
    }

};

void redirectInput(const char *in, const char *out)
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
}

void redirectInput(const char *in, const char *out, int argc, char **argv)
{
    if( argc == 3 )
    {
        redirectInput(argv[1], argv[2]);
    }
    else if( argc == 2 )
    {
        redirectInput(argv[1], out);
    }
    else
    {
        redirectInput(in, out);
    }
}

long getNumber(char *&expr)
{
    int number = 0;
    while(*expr >= '0' && *expr <= '9' )
    {
        number = number * 10 + *expr - '0';
        ++expr;
    }
    --expr;
    return number;
}

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

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

void printPostFix(vector<node> &postfix)
{
    for(int i = 0; i < (int) postfix.size(); ++i)
    {
        if(postfix[i].Type == node::Operand)
            printf("%ld ", postfix[i].Value.Operand);
        else
            printf("%c " , postfix[i].Value.Operator);
    }
    printf("\n");
}

void buildPostfix(char *expr, vector<node> &postfix)
{
    stack<char> s;
    while(*expr != '\0')
    {
        if(isNumber(*expr))
        {
            long number = getNumber(expr);
            postfix.push_back(node(number));
        } else if(*expr == '(')
        {
            s.push('(');
        } else if(*expr == ')')
        {
            for(char op = s.top(); op != '('; op = s.top())
            {
                postfix.push_back(node(op));
                s.pop();
            }
            s.pop();
        } else
        {
            char Operator = *expr;
            while(!s.empty()
            && priority(Operator) <= priority(s.top()))
            {
                postfix.push_back(node(s.top()));
                s.pop();
            }
            s.push(Operator);
        }
        ++expr;
    }
    while(!s.empty())
    {
        postfix.push_back(node(s.top()));
        s.pop();
    }
}

inline long compute(char Operator, stack<long> &s)
{
    long r = s.top();
    s.pop();
    switch(Operator)
    {
        case '+':
            r += s.top();
            break;
        case '-':
            r = s.top() - r;
            break;
        case '*':
            r *= s.top();
            break;
        case '/':
        {
            r = s.top() / r;
            break;
        }
        default:
            break;
    }
    s.pop();
    return r;
}

long evalPostFix(vector<node> &postfix)
{
    stack<long> s;
    for(int i = 0; i < (int) postfix.size(); ++i)
    {
        if(postfix[i].Type == node::Operand)
            s.push(postfix[i].Value.Operand);
        else
        {
            char Operator = postfix[i].Value.Operator;
            s.push(compute(Operator, s));
        }
    }
    return s.top();
}

void solve()
{
    long result = 0;
    char *expr = (char*) calloc (100000, sizeof(char));
    scanf("%s", expr);
    vector<node> postfix;
    buildPostfix(expr, postfix);
    result = evalPostFix(postfix);
    printf("%ld\n", result);
}

int main(int argc, char *argv[])
{
    redirectInput("evaluare.in", "evaluare.out", argc, argv);
    solve();
    return 0;
}