#include <iostream>
#include <vector>
#include <list>
#include <math.h>

class Token
{
public:
    Token(const char);
    Token(std::string num);
    enum Type { RBracket, LBracket, Num, Space, Dot, Add, Sub, Div, Mul, Pow, Undefined };
    enum Priority { Low, Average, High, Braces };
    std::string symbol();
    Type type();
    Priority priority();

private:
    std::string _symbol;
    Type _type;
    Priority _priority;

};

// TODO: add Undefined
Token::Token(char ch)
{
    _symbol = ch;

    if (isdigit(ch))
        _type = Num;

    switch (ch) {
    case ' ':
        _type = Space;
        break;
    case '.':
        _type = Dot;
        break;
    case '+':
        _type = Add;
        _priority = Low;
        break;
    case '-':
        _type = Sub;
        _priority = Low;
        break;
    case '/':
        _type = Div;
        _priority = Average;
        break;
    case '*':
        _type = Mul;
        _priority = Average;
        break;
    case '^':
        _type = Pow;
        _priority = High;
        break;
    case '(':
        _type = LBracket;
        _priority = Braces;
        break;
    case ')':
        _type = RBracket;
        _priority = Braces;
        break;
    }
}

// It is always number
Token::Token(std::string num)
{
    _type = Num;
    _symbol = num;
}

std::string Token::symbol()
{
    return _symbol;
}

Token::Type Token::type()
{
    return _type;
}

Token::Priority Token::priority()
{
    return _priority;
}

std::vector<Token> toRPN(std::string str)
{
    size_t len = str.length();
    std::string number; // glue number
    bool glueNumber = false;  // we are alrady gluing?
    int prevType;
    std::vector<Token> tokens;
    std::vector<Token> result;

    for (unsigned i = 0; i < len; ++i) {
        Token tok(str[i]);
        if (tok.type() == Token::Undefined)
            fprintf(stderr, "Undefined token <%s>\n", tok.symbol().c_str());
        if (tok.type() == Token::Space) {
            if (glueNumber) {
                result.push_back(Token(number));
                glueNumber = false;
                number.clear();
            }
            continue;
        }

        if (tok.type() == Token::Sub) {
            if (prevType != Token::Num) {
                if (!glueNumber) {
                    number += tok.symbol();
                } else {
                    fprintf(stderr, "Undefined token <%s>\n", tok.symbol().c_str());
                }
                continue;
            }
        }

        // For determine if minus (-) is '-3' or '5 - 3'
        prevType = tok.type();

        // It is dot without number .4 + 3
        if (tok.type() == Token::Dot) {
            if (glueNumber) {
                number += tok.symbol();
            } else {
                fprintf(stderr, "Undefined token <%s>\n", tok.symbol().c_str());
            }
            continue;
        }

        if (tok.type() == Token::Num) {
            number += tok.symbol();
            glueNumber = true;
            if (i == len - 1) {
                result.push_back(Token(number));
            }
        } else {
            if (glueNumber) {
                result.push_back(Token(number));
                glueNumber = false;
                number = "";
            }

            while(tokens.size() > 0 && tok.type() != Token::RBracket) {
                Token prev = tokens.back();
                if (prev.priority() >= tok.priority() && prev.priority() != Token::Braces) {
                    result.push_back(prev);
                    tokens.pop_back();
                } else {
                    break;
                }
            }

            if (tok.type() != Token::RBracket)
                tokens.push_back(tok);
        }

        if (tok.type() == Token::RBracket) {
            Token prev = tokens.back();
            while (prev.type() != Token::LBracket) {
                result.push_back(prev);
                tokens.pop_back();
                prev = tokens.back();
            }
            tokens.pop_back(); // delete LBracket
        }
    }

    // Reverse iteration. Add remaining tokens to result
    for (std::vector<Token>::reverse_iterator rit = tokens.rbegin(); rit!= tokens.rend(); ++rit) {
        result.push_back(*rit);
    }

    return result;
}

// If exspression will ended with error we'll show it!
std::string calculateError;
double calculate(std::vector<Token> tokens)
{
    std::vector<double> stack;
    double val1;
    double val2;
    double result;

    // If it was any error we have to clear it!
    calculateError.clear();

    for (Token &tok : tokens) {

        if (tok.type() == Token::Num) {
            stack.push_back(atof(tok.symbol().c_str()));
            continue;
        }

        // Minimum for operation
        if (stack.size() > 1) {

            // Get last two numbers from stack
            val2 = stack.back();
            stack.pop_back();
            val1 = stack.back();
            stack.pop_back();

            switch (tok.type()) {
            case Token::Add:
                stack.push_back(val1 + val2);
                break;
            case Token::Sub:
                stack.push_back(val1 - val2);
                break;
            case Token::Mul:
                stack.push_back(val1 * val2);
                break;
            case Token::Div:
                if (val2 == 0) {
                    calculateError.append("Divided by zero");
                }
                stack.push_back(val1 / val2);
                break;
            case Token::Pow:
                stack.push_back(pow(val1, val2));
                break;
            default:
                break;
            }
        } else {
            calculateError.append("Does not correct expression");
            break;
        }
    }

    if (stack.size() == 1) {
        double temp = stack.back();
        result = temp;
    } else {
        calculateError.append("Does not correct expression");
    }

    return result;
}

void test_calculate()
{
    std::list<std::string> lst;
    lst.push_back("2 + 3");
    lst.push_back("4 - 3");
    lst.push_back("2 + (-3)");
    lst.push_back("4 * 5");
    lst.push_back("6/4");
    lst.push_back("1.2 + 1/2");
    lst.push_back("1/(-3)");
    lst.push_back("0.5 + 0.2");
    lst.push_back("3 ^ 2 ^ 2");
    lst.push_back("17654/342");
    lst.push_back("2/3 ^ 2");
    lst.push_back("(2/3) ^ 2");
    lst.push_back("(2 + 3) / (2 - 2) ");
    lst.push_back("2 + 345 + + + + 6 ");

    std::vector<Token> tokens;
    double result;
    std::string resultOfRPN;
    for (std::string &item : lst) {
        tokens = toRPN(item);
        for (Token &tok : tokens) {
            resultOfRPN.append(tok.symbol() + " ");
        }
        result = calculate(tokens);

        if (calculateError.size() == 0)
            printf("%-18s %.6g\n", resultOfRPN.c_str(), result);
        else
            printf("%-18s %s\n", resultOfRPN.c_str(), calculateError.c_str());

        // reset
        resultOfRPN.clear();
    }
}

int main()
{
    test_calculate();

    return 0;
}