Cod sursa(job #880215)

Utilizator vgabi94Vaduva Gabriel vgabi94 Data 16 februarie 2013 15:02:36
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.37 kb
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;

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

char expr[100001]; int polish[100001];
int opcode[5] = { 0, 1e9 + 1, 1e9 + 2, 1e9 + 3, 1e9 + 4 };  //  + - * /
int iD = 0, iS = 0;

int op_prec(const char &op)
{
    switch (op)
    {
        case '*': case '/':
            return 2;
        case '+': case '-':
            return 1;
        case '(':
            return -1;
    }
    return 0;
}

int op_code(const char &op)
{
    switch (op)
    {
        case '+': return opcode[1];
        case '-': return opcode[2];
        case '*': return opcode[3];
        case '/': return opcode[4];
    }
    return 0;
}

void ShuntingYard(int *dest, char *source)
{
    int len = strlen(source);
    stack<char> ops;     // Stiva operatorilor
    while (iS < len)
    {
        if (isdigit(source[iS]))
        {
            int number = 0;
            while (isdigit(source[iS]))
            {
                number = number * 10 + (source[iS] - 48);
                iS++;
            }
            dest[iD++] = number; continue;
        }
        else if (source[iS] == '(') ops.push(source[iS]);
        else if (source[iS] == ')')
        {
            char op = ops.top(); ops.pop();
            while (op != '(')
            {
                dest[iD++] = op_code(op);
                op = ops.top(); ops.pop();
            }
        }
        else
        {
            char op1, op2;
            op1 = source[iS];
            if (!ops.empty())
            {
                op2 = ops.top();
                while (op_prec(op1) <= op_prec(op2))
                {
                    ops.pop();
                    dest[iD++] = op_code(op2);
                    if (ops.empty()) break;
                    op2 = ops.top();
                }
            }
            ops.push(op1);
        }
        iS++;  // next token
    }
    while (!ops.empty())
    {
        dest[iD++] = op_code(ops.top());
        ops.pop();
    }
}

int main()
{
    stack<int> eval;
    in.getline(expr, 100001);
    ShuntingYard(polish, expr);
    for (int i = 0; i < iD; i++)
    {
        if (polish[i] <= int(1e9)) eval.push(polish[i]);
        else
        {
            switch (polish[i] % int(1e9))
            {
                case 1: {
                    int ope1 = eval.top(); eval.pop();
                    int ope2 = eval.top(); eval.pop();
                    int res = ope1 + ope2;
                    eval.push(res);
                } break;
                case 2: {
                    int ope2 = eval.top(); eval.pop();
                    int ope1 = eval.top(); eval.pop();
                    int res = ope1 - ope2;
                    eval.push(res);
                } break;
                case 3: {
                    int ope2 = eval.top(); eval.pop();
                    int ope1 = eval.top(); eval.pop();
                    int res = ope1 * ope2;
                    eval.push(res);
                } break;
                case 4: {
                    int ope2 = eval.top(); eval.pop();
                    int ope1 = eval.top(); eval.pop();
                    int res = ope1 / ope2;
                    eval.push(res);
                } break;
            }
        }

    }
    out << eval.top();
    return 0;
}