Reverse polish notation

reverse_polish.cc

#include <iostream>
#include <fstream>
#include <string>
#include <cmath>


template <typename T>
class Element
{
public:
    Element (T data): data (data), link (nullptr) {};
   
    T data;
    Element* link;
};


template <typename T>
class Stack
{
public:
    Stack (): first (nullptr) {};

    Element <T>* first;

    void push (T data)
    {
        Element <T>* new_first = new Element <T> (data);
        new_first -> link = first;
        first = new_first;
    }

    T pop ()
    {
        T data = first -> data;
        Element <T>* tmp = first;

        first = first -> link;
        delete tmp;

        return data;
    }

    bool empty () { return (first == nullptr); }
};


bool is_op (char data) { return (data == '+' || data == '-' || data == '*' || data == '/'); }
bool priority (char op) { return (op == '*' || op == '/'); }


int main ()
{
    Stack <char> stack;

    std::string expr;
    std::getline (std::cin, expr);

    std::string res = "";

    for (size_t i = 0; i < expr.size(); i++)
    {
        if (std::isdigit (expr [i])) res += expr [i];

        else if (expr [i] == '(') stack.push ('(');

        else if (expr [i] == ')')
        {
            char tmp = stack.pop ();
            while (is_op (tmp))
            {
                res += tmp;
                tmp = stack.pop ();
            }
        }

        else if (is_op (expr [i]))
        {
            if (stack.empty ())
            {
                stack.push (expr [i]);
                continue;
            }

            char tmp = stack.pop ();
            while (is_op(tmp) && priority (tmp) && !stack.empty())
            {
                res += tmp;
                tmp = stack.pop ();
            }

            stack.push (tmp);
            stack.push (expr [i]);
        }
    }

    while (!stack.empty ())
        res += stack.pop ();

    std::cout << res << std::endl;
    return 0;
}