Cod sursa(job #2872055)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 16 martie 2022 11:37:16
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.92 kb
#include <cctype>
#include <fstream>
#include <optional>
#include <stack>
#include <variant>
#include <vector>

enum Operator { Add, Sub, Mul, Div, LeftParens, RightParens };
using Token = std::variant<Operator, int>;

unsigned precedence(Operator op) {
    switch (op) {
    case Add:
    case Sub:
        return 1;
        break;
    case Mul:
    case Div:
        return 2;
        break;
    default:
        return 0;
    }
}

std::vector<Token> tokenize(const std::string &str) {
    std::vector<Token> tokens;

    std::optional<int> num_builder = {};
    for (auto c : str) {
        if (isdigit(c)) {
            num_builder = num_builder.value_or(0) * 10 + (c - '0');
        } else {
            if (num_builder.has_value()) {
                tokens.push_back(num_builder.value());
                num_builder = {};
            }

            switch (c) {
            case '+':
                tokens.push_back(Add);
                break;
            case '-':
                tokens.push_back(Sub);
                break;
            case '*':
                tokens.push_back(Mul);
                break;
            case '/':
                tokens.push_back(Div);
                break;
            case '(':
                tokens.push_back(LeftParens);
                break;
            case ')':
                tokens.push_back(RightParens);
                break;
            }
        }
    }

    // Push remaining number
    if (num_builder.has_value()) {
        tokens.push_back(num_builder.value());
    }

    return tokens;
}

std::vector<Token> convert_to_rpn(const std::vector<Token> &infix) {
    std::stack<Operator> opstack;
    std::vector<Token> output;
    output.reserve(infix.size());

    for (auto token : infix) {
        if (std::holds_alternative<int>(token)) {
            output.push_back(token);
        } else {
            // Handle operator
            auto op = std::get<Operator>(token);
            if (op == LeftParens) {
                opstack.push(op);
            } else if (op == RightParens) {
                while (opstack.top() != LeftParens) {
                    output.push_back(opstack.top());
                    opstack.pop();
                }
                // Discard LeftParens
                opstack.pop();
            } else {
                while (!opstack.empty() && opstack.top() != LeftParens &&
                       precedence(opstack.top()) >= precedence(op)) {
                    output.push_back(opstack.top());
                    opstack.pop();
                }
                opstack.push(op);
            }
        }
    }

    // Push remaining operators to output
    while (!opstack.empty()) {
        output.push_back(opstack.top());
        opstack.pop();
    }

    return output;
}

long long compute_rpn(const std::vector<Token> &rpn) {
    std::stack<long long> num_stack;
    for (auto token : rpn) {
        if (std::holds_alternative<int>(token)) {
            num_stack.push(std::get<int>(token));
        } else {
            auto y = num_stack.top();
            num_stack.pop();
            auto x = num_stack.top();
            num_stack.pop();

            long long result;
            switch (std::get<Operator>(token)) {
            case Add:
                result = x + y;
                break;
            case Sub:
                result = x - y;
                break;
            case Mul:
                result = x * y;
                break;
            case Div:
                result = x / y;
                break;
            default:
                break;
            }
            num_stack.push(result);
        }
    }

    return num_stack.top();
}

int main() {
    std::ifstream is("evaluare.in");
    std::ofstream os("evaluare.out");

    std::string infix;
    std::getline(is, infix);

    auto infix_tokens = tokenize(infix);
    auto rpn_tokens = convert_to_rpn(infix_tokens);
    os << compute_rpn(rpn_tokens) << '\n';

    is.close();
    os.close();
    return 0;
}