Cod sursa(job #1029089)

Utilizator cbanu96Banu Cristian cbanu96 Data 15 noiembrie 2013 00:01:25
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 5.58 kb
#include <cstdio>
#include <stack>
#include <cstring>

#define FILEIN "evaluare.in"
#define FILEOUT "evaluare.out"
#define NMAX 100005

using namespace std;

int op[256];
int prio[256];
char sir[NMAX];
stack<int> op_stack;
stack<long long int> r_stack;

long long int solve()
{
    op['+'] = 1;
    op['-'] = 2;
    op['*'] = 3;
    op['/'] = 4;
    op['('] = 5;

    prio[1] = prio[2] = 1;
    prio[3] = prio[4] = 2;

    int i;
    int len;
    len = strlen(sir);
    if (sir[len-1] == '\n')
    {
        sir[len-1] = '\0';
        len--;
    }

    for ( i = 0; i < len; i++ )
    {
        switch(sir[i])
        {
            case ')':
                while (op_stack.top() != op['('])
                {
                    int operatie = op_stack.top(); op_stack.pop();
                    int a, b;
                    b = r_stack.top(); r_stack.pop();
                    a = r_stack.top(); r_stack.pop();
                    if (operatie == op['+'])
                        r_stack.push(a+b);
                    if (operatie == op['-'])
                        r_stack.push(a-b);
                    if (operatie == op['*'])
                        r_stack.push(a*b);
                    if (operatie == op['/'])
                        r_stack.push(a/b);
                }
                op_stack.pop();
                break;
            case '(':
                op_stack.push(op['(']);
                break;
            case '+':
                while (!op_stack.empty() && prio[op_stack.top()] >= prio[op['+']])
                {
                    int operatie = op_stack.top(); op_stack.pop();
                    int a, b;
                    b = r_stack.top(); r_stack.pop();
                    a = r_stack.top(); r_stack.pop();
                    if (operatie == op['+'])
                        r_stack.push(a+b);
                    if (operatie == op['-'])
                        r_stack.push(a-b);
                    if (operatie == op['*'])
                        r_stack.push(a*b);
                    if (operatie == op['/'])
                        r_stack.push(a/b);
                }
                op_stack.push(op['+']);
                break;
            case '-':
                while (!op_stack.empty() && prio[op_stack.top()] >= prio[op['-']])
                {
                    int operatie = op_stack.top(); op_stack.pop();
                    int a, b;
                    b = r_stack.top(); r_stack.pop();
                    a = r_stack.top(); r_stack.pop();
                    if (operatie == op['+'])
                        r_stack.push(a+b);
                    if (operatie == op['-'])
                        r_stack.push(a-b);
                    if (operatie == op['*'])
                        r_stack.push(a*b);
                    if (operatie == op['/'])
                        r_stack.push(a/b);
                }
                op_stack.push(op['-']);
                break;
            case '*':
                while (!op_stack.empty() && prio[op_stack.top()] >= prio[op['*']])
                {
                    int operatie = op_stack.top(); op_stack.pop();
                    int a, b;
                    b = r_stack.top(); r_stack.pop();
                    a = r_stack.top(); r_stack.pop();
                    if (operatie == op['+'])
                        r_stack.push(a+b);
                    if (operatie == op['-'])
                        r_stack.push(a-b);
                    if (operatie == op['*'])
                        r_stack.push(a*b);
                    if (operatie == op['/'])
                        r_stack.push(a/b);
                }
                op_stack.push(op['*']);
                break;
            case '/':
                while (!op_stack.empty() && prio[op_stack.top()] >= prio[op['/']])
                {
                    int operatie = op_stack.top(); op_stack.pop();
                    int a, b;
                    b = r_stack.top(); r_stack.pop();
                    a = r_stack.top(); r_stack.pop();
                    if (operatie == op['+'])
                        r_stack.push(a+b);
                    if (operatie == op['-'])
                        r_stack.push(a-b);
                    if (operatie == op['*'])
                        r_stack.push(a*b);
                    if (operatie == op['/'])
                        r_stack.push(a/b);
                }
                op_stack.push(op['/']);
                break;
            case ' ':
                break;
            default:
                int sign = 1;
                if ( sir[i] == '-' )
                    sign = -1, i++;

                if ( sir[i] >= '0' && sir[i] <= '9')
                {
                    int val = 0;
                    while (sir[i] >= '0' && sir[i] <= '9')
                    {
                        val = val * 10 + sir[i] - '0';
                        ++i;
                    }
                    val *= sign;
                    r_stack.push(val);
                    --i;
                }
                break;
        }
    }

    while (!op_stack.empty())
    {
        int operatie = op_stack.top(); op_stack.pop();
        int a, b;
        b = r_stack.top(); r_stack.pop();
        a = r_stack.top(); r_stack.pop();
        if (operatie == op['+'])
            r_stack.push(a+b);
        if (operatie == op['-'])
            r_stack.push(a-b);
        if (operatie == op['*'])
            r_stack.push(a*b);
        if (operatie == op['/'])
            r_stack.push(a/b);
    }

    return r_stack.top();
}

int main()
{
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    gets(sir);
    printf("%lld\n", solve());

    return 0;
}