exercises/dsa/ch3_stack_queue/dsa_0302_calculator.cpp

#include <iostream>
#include <stack>
#include <vector>
#include <variant>
#include <cassert>

class Token {
protected:
    std::variant<char, int> token_variant_;

public:
    explicit Token(char c) : token_variant_(c) {}
    explicit Token(int x) : token_variant_(x) {}

    [[nodiscard]] bool is_operator() const {
        return std::holds_alternative<char>(token_variant_);
    }

    [[nodiscard]] char get_operator() const {
        if (!is_operator()) { throw std::invalid_argument("Not an operator"); }
        return std::get<char>(token_variant_);
    }

    [[nodiscard]] int get_number() const {
        if (is_operator()) { throw std::invalid_argument("Is an operator"); }
        return std::get<int>(token_variant_);
    }

    [[nodiscard]] int get_priority() const {
        if (get_operator() == '+' || get_operator() == '-') { return 1; }
        if (get_operator() == '*' || get_operator() == '/') { return 2; }
        throw std::invalid_argument("Unknown priority");
    }

    template <typename T1, typename T2>
    [[nodiscard]] auto calc_operator(T1 a, T2 b) const {
        switch (get_operator()) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: throw std::invalid_argument("Uncalculatable operator");
        }
    }

    bool operator==(char c) const {
        if (!is_operator()) { return false; }
        return get_operator() == c;
    }

    bool operator==(int x) const {
        if (is_operator()) { return false; }
        return get_number() == x;
    }

    template <typename T>
    bool operator!=(T x) {
        return !(*this == x);
    }

    friend std::ostream& operator<<(std::ostream& os, Token token) {
        if (token.is_operator()) {
            os << token.get_operator();
        } else {
            os << '[' << token.get_number() << ']';
        }
        return os;
    }
};

using Expression = std::vector<Token>;

std::ostream& operator<<(std::ostream& os, const Expression& expression) {
    for (const auto& token : expression) {
        os << token;
    }
    return os;
}

Expression parse_string(const std::string& str) {
    Expression expression;
    std::string temp_token;
    for (char c : str) {
        if (!(c >= '0' && c <= '9')) {
            if (!temp_token.empty()) {
                expression.emplace_back(std::stoi(temp_token));
                temp_token.clear();
            }
            expression.emplace_back(c);
        } else {
            temp_token += c;
        }
    }
    if (!temp_token.empty()) { expression.emplace_back(std::stoi(temp_token)); }
    return expression;
}

Expression convert_to_postfix(const Expression& infix_expression) {
    Expression postfix_expression;
    std::stack<Token> operators;

    for (const auto& token : infix_expression) {
        if (!token.is_operator()) {
            postfix_expression.push_back(token);
            continue;
        }
        if (token.get_operator() == '(') {
            operators.push(token);
            continue;
        }
        if (token.get_operator() == ')') {
            while (operators.top().get_operator() != '(') {
                postfix_expression.push_back(operators.top());
                operators.pop();
            }
            operators.pop();
            continue;
        }
        while (!operators.empty() && operators.top() != '('
            && token.get_priority() <= operators.top().get_priority()) {
            postfix_expression.push_back(operators.top());
            operators.pop();
        }
        operators.push(token);
    }
    while (!operators.empty()) {
        postfix_expression.push_back(operators.top());
        operators.pop();
    }
    return postfix_expression;
}

int calculate_postfix(const Expression& postfix_expression) {
    std::stack<int> numbers;
    for (const auto& token : postfix_expression) {
        if (!token.is_operator()) {
            numbers.push(token.get_number());
            continue;
        }
        int b = numbers.top();
        numbers.pop();
        int a = numbers.top();
        numbers.pop();
        numbers.push(token.calc_operator(a, b));
    }
    assert(numbers.size() == 1);
    return numbers.top();
}

std::string s;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> s;
    while (std::cin >> s) {
        Expression infix_expression = parse_string(s);
        std::clog << infix_expression << std::endl;
        Expression postfix_expression = convert_to_postfix(infix_expression);
        std::cout << calculate_postfix(postfix_expression) << std::endl;
    }

    return 0;
}