shunting_yard.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <iterator>
#include <algorithm>
#include <string>
#include <unordered_map>

const std::unordered_map<char, unsigned> OPERATORS = {
    {'*', 2},
    {'/', 2},
    {'+', 1},
    {'-', 1},
};

std::string
convert_to_rpn(const std::string& in_str) {
    std::string rpn_str;

    std::stack<char> stk;
    for (auto&& c : in_str) {
        if (std::isdigit(c)) {
            rpn_str.push_back(c);
        }
        else if (OPERATORS.count(c) != 0) {
            // First on stack?
            if (stk.empty()) {
                stk.push(c);
                continue;
            }

            // Token's precedence is less than or equal to that of stack's top
            if (OPERATORS.at(c) <= OPERATORS.at(stk.top())) {
                rpn_str.push_back(stk.top());
                stk.pop();
            }
            // At the end of iteration push token onto operator stack
            stk.push(c);
        }
        else {
            throw std::runtime_error{"Something went wrong"};
        }
    }

    while (!stk.empty()) {
        rpn_str.push_back(stk.top());
        stk.pop();
    }

    return rpn_str;
}

int
main(int argc, char const* argv[]) {
    std::string in_str;
    std::copy(std::istream_iterator<char>(std::cin),
              std::istream_iterator<char>(),
              std::back_inserter(in_str));

    std::cout << "Input" << std::endl;
    for (auto&& c : in_str) {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    auto rpn_str = convert_to_rpn(in_str);

    std::cout << "Reverse Polish Notation" << std::endl;
    for (auto&& c : rpn_str) {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    return 0;
}