shunting_yard.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <deque>

using namespace std;


class Operator
{
public:
    static map<string, int> operators;
    
    static bool has(const string& token) {
        return operators.count(token) > 0;
    }
};

map<string, int> Operator::operators = {
    {"+", 2},
    {"-", 2},
    {"*", 4},
    {"/", 4}
};


auto shunting_yard(const vector<string>& infix)
{
    deque<string> stack;
    vector<string> list;
    
    for(auto& token: infix) {
        if(Operator::has(token)){
            if(list.empty()){
                list.push_back(token);
            }else{
                auto prio = Operator::operators[token];
                auto prev_prio = Operator::operators[list.back()];
                
                if(prio > prev_prio){
                    while(!stack.empty()) 
                        list.push_back(stack.back()), stack.pop_back(); // yes this is ugly but it's a quick & dirty test
                        
                }
                stack.push_back(token);
            }
            
        }else{
            list.push_back(token);
        }
    }
    
    while(!stack.empty()) 
        list.push_back(stack.back()), stack.pop_back();
    
    return list;
}

int main()
{
    string input = "1*2*3+4+5";
    vector<string> infix;
    for(auto c: input)
        infix.push_back(string(1, c));
            

    auto postfix = shunting_yard(infix);
    cout << input << " = ";
    for(auto& t: postfix)
        cout << t << " "; 
    cout << endl;
    
    return 0;
}