Cod sursa(job #2720736)

Utilizator LawrentiuTirisi Claudiu Lawrentiu Data 11 martie 2021 11:15:15
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define maxL 100000
using namespace std;
ifstream f("evaluare.in");
ofstream o("evaluare.out");

struct token
{
    bool isDig;
    union
    {
        int number;
        char op;
    } data;
};

int prec(char op)
{
    if (op == '+' || op == '-')
        return 0;
    return 1;
}

int greaterPrec(char op1, char op2)
{
    return prec(op1) - prec(op2);
}

bool isOp(char op)
{
    return op == '+' || op == '-' || op == '*' || op == '/';
}

bool isLeftAssoc(char op)
{
    return true; // all of our operators are left associative
}

void toRPN(char exp[], int len, vector<token> &output)
{
    vector<char> operators;
    token aux;
    int num;

    for (int i = 0; i < len; i++)
    {

        if (isdigit(exp[i]))
        {
            num = exp[i] - '0';
            while (isdigit(exp[++i]))
            {
                num = num * 10 + (exp[i] - '0');
            }
            aux.isDig = 1;
            aux.data.number = num;
            output.push_back(aux);
            i--;
        }
        else
        {

            // is an operator
            if (isOp(exp[i]))
            {
                while (!operators.empty() && ((greaterPrec(operators.back(), exp[i]) > 0) || (greaterPrec(operators.back(), exp[i]) == 0 && isLeftAssoc(exp[i]))) && (operators.back() != '('))
                {
                    aux.isDig = 0;
                    aux.data.op = operators.back();
                    output.push_back(aux);
                    operators.pop_back();
                }
                operators.push_back(exp[i]);
            }
            else
            {

                if (exp[i] == '(')
                {
                    operators.push_back('(');
                }
                else
                {
                    while (operators.back() != '(')
                    {
                        aux.isDig = 0;
                        aux.data.op = operators.back();
                        output.push_back(aux);
                        operators.pop_back();
                    }
                    operators.pop_back();
                }
            }
        }
    }

    aux.isDig = 0;
    while (!operators.empty())
    {
        aux.data.op = operators.back();
        output.push_back(aux);
        operators.pop_back();
    }
}

int eval(int a, int b, char op)
{
    if (op == '+')
        return a + b;
    if (op == '-')
        return a - b;
    if (op == '*')
        return a * b;
    return a / b;
}

int solveRPN(vector<token> polish)
{
    vector<int> stack;
    int a, b;
    for (vector<token>::iterator i = polish.begin(); i != polish.end(); ++i)
    {
        if (i->isDig)
        {
            stack.push_back(i->data.number);
        }
        else
        {
            a = stack.back();
            stack.pop_back();
            b = stack.back();
            stack.pop_back();
            stack.push_back(eval(b, a, i->data.op));
        }
    }
    return stack.back();
}

int main()
{

    char exp[maxL];
    int len;
    f >> exp;
    len = strlen(exp);

    vector<token> output;

    toRPN(exp, len, output);
    for (vector<token>::iterator i = output.begin(); i != output.end(); ++i)
    {
        if (i->isDig)
            cout << i->data.number;
        else
            cout << i->data.op;
        cout << " ";
    }

    o << solveRPN(output);
}