Infix to Postfix (Reverse Polish Notation)

infix2postfix.cpp

#include <iostream>
#include <cstring>
#include <stack>

uint8_t precedence[256];

bool HasHigherPrecedence(char a, char b) {
    return precedence[(uint8_t)a] < precedence[(uint8_t)b];
}

template<class T>
T pop(std::stack<T>& t) {
    T res = t.top();
    t.pop();
    return std::move(res);
}

bool isOperator(char c) {
    return c == '+' || c == '-' ||
           c == '/' || c == '*' ||
           c == '^';
}

bool isOperand(char c) {
    return std::isdigit(c) || std::isalpha(c);
}

void setup() {
    precedence['*'] = 1;
    precedence['/'] = 1;
    precedence['+'] = 2;
    precedence['-'] = 2;
    precedence['^'] = 4;
}

std::string InfixToPostfix(std::string const& infix) {
    setup();
    std::stack<char> operators;
    std::string postfix;
    for (unsigned int i = 0; i < infix.size(); ++i) {
        char c = infix[i];

        if (isOperand(c)) {
            postfix += c;
        }
        else if (isOperator(c)) {
            while (!operators.empty() && HasHigherPrecedence(c, operators.top()))
                postfix += pop(operators);
            operators.push(c);
        }
        else if (c == '(') {
            operators.push(c);
        }
        else if (c == ')') {
            while (!operators.empty() && operators.top() != '(') {
                postfix += pop(operators);
            }
            operators.pop();
        }
    }
    while (!operators.empty())
        postfix += pop(operators);
    return std::move(postfix);
}

int main() {
    int test_cases;
    std::cin >> test_cases;
    
    for (std::string str; test_cases-- && std::getline(std::cin >> std::ws, str); std::cout << InfixToPostfix(str) << '\n')
    {};
}