Cod sursa(job #2457244)

Utilizator igsifvevc avb igsi Data 16 septembrie 2019 23:04:11
Problema Evaluarea unei expresii Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.71 kb
#include <cctype>
#include <fstream>
#include <map>
#include <stack>
#include <string>
#include <vector>

std::map<std::string, int> precedence{
    {"(", -1}, {"-", 0}, {"+", 0}, {"*", 1}, {"/", 1}};

std::string read();

void write(int results);

std::vector<std::string> parse(const std::string &E);

std::vector<std::string>
reversePolishNotation(const std::vector<std::string> &tokens);

int evaluate(const std::vector<std::string> &tokens);

int solve(const std::string &E)
{
    auto tokens = parse(E);
    auto rpnTokens = reversePolishNotation(tokens);
    auto result = evaluate(rpnTokens);

    return result;
}

int main()
{
    auto e = read();
    auto result = solve(e);
    write(result);

    return 0;
}

std::vector<std::string>
reversePolishNotation(const std::vector<std::string> &tokens)
{
    std::stack<std::string> operators;
    std::vector<std::string> rpnTokens;

    for (auto &token : tokens)
    {
        if (token == "-" || token == "+" || token == "*" || token == "/")
        {
            while (!operators.empty() &&
                   precedence[operators.top()] >= precedence[token])
            {
                rpnTokens.push_back(operators.top());
                operators.pop();
            }

            operators.push(token);
        }
        else if (token == "(")
        {
            operators.push(token);
        }
        else if (token == ")")
        {
            while (operators.top() != "(")
            {
                rpnTokens.push_back(operators.top());
                operators.pop();
            }

            operators.pop();
        }
        else
        {
            rpnTokens.push_back(token);
        }
    }

    while (!operators.empty())
    {
        rpnTokens.push_back(operators.top());
        operators.pop();
    }

    return rpnTokens;
}

int evaluate(const std::vector<std::string> &tokens)
{
    std::stack<int> operands;

    for (auto &token : tokens)
    {
        if (token == "-" || token == "+" || token == "*" || token == "/")
        {
            int a, b;
            b = operands.top();
            operands.pop();
            a = operands.top();
            operands.pop();

            switch (token[0])
            {
            case '-':
                operands.push(a - b);
                break;
            case '+':
                operands.push(a + b);
                break;
            case '*':
                operands.push(a * b);
                break;
            case '/':
                operands.push(a / b);
                break;
            }
        }
        else
        {
            int x = std::stoi(token);
            operands.push(x);
        }
    }

    return operands.top();
}

std::vector<std::string> parse(const std::string &E)
{
    std::vector<std::string> tokens;

    for (int i = 0; i < E.size();)
    {
        switch (E[i])
        {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
            tokens.push_back(std::string(1, E[i]));
            i++;
            break;

        case ' ':
            i++;
            break;

        default:
            std::string token;

            while (i < E.size() && std::isdigit(E[i]))
            {
                token += E[i];
                i++;
            }

            tokens.push_back(token);
            break;
        }
    }

    return tokens;
}

std::string read()
{
    std::ifstream fin("evaluare.in");

    std::string s;
    fin >> s;

    return s;
}

void write(int result)
{
    std::ofstream fout("evaluare.out");

    fout << result << '\n';
}