/*
 *  Hornwitser's silly calculator app v0.1
 */

#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
#include <iostream>


struct pass {
    template <typename... Ts> pass(Ts&...) {}
};

// useful function for creating a string out of variables
template <typename... Ts>
std::string compose(Ts... parts) {
    std::ostringstream result;
    pass{result << parts...};
    return result.str();
}


struct Token;

typedef std::string::size_type StringPos;
typedef std::vector<Token>::size_type TokenPos;

struct Token {
    enum Type {
        Number,
        Pluss,
        Minus,
        Multiply,
        Divide,
        ParenOpen,
        ParenClose,
        EndOfInput,
    } type;
    StringPos pos;
    int value;

    Token(Type type, StringPos pos, int value = 0)
        : type(type), pos(pos), value(value)
    {}
};


class InputError: public std::runtime_error
{
public:
    const StringPos pos;

    InputError(std::string what, StringPos pos)
        : runtime_error(what), pos(pos)
    {}
};

class ParseError: public InputError
{
public:
    ParseError(std::string what, StringPos pos)
        : InputError(compose("ParseError: ", what), pos)
    {}
};

class SyntaxError: public InputError
{
public:
    SyntaxError(std::string what, StringPos pos)
        : InputError(compose("SyntaxError: ", what), pos)
    {}
};

class DivideByZeroError: public InputError
{
public:
    DivideByZeroError(std::string what, StringPos pos)
        : InputError(compose("DivideByZeroError: ", what), pos)
    {}
};

std::ostream& operator<<(std::ostream& os, Token::Type t)
{
    switch (t) {
    case Token::Number: os << "number"; break;
    case Token::Pluss: os << "'+'"; break;
    case Token::Minus: os << "'-'"; break;
    case Token::Multiply: os << "'*'"; break;
    case Token::Divide: os << "'/'"; break;
    case Token::ParenOpen: os << "'('"; break;
    case Token::ParenClose: os << "')'"; break;
    case Token::EndOfInput: os << "end of input"; break;
    default: os << "[unkown id " << (int)t << "]"; break;
    }

    return os;
}

int parse_number(const std::string& in, StringPos* p_pos)
{
    StringPos& pos = *p_pos;

    int num = 0;
    while (pos < in.size()) {
        char c = in[pos];
        if (c >= '0' && c <= '9') {
            num = num * 10 + c - '0';

        } else {
            pos--; // put the char back in the stream
            return num;
        }

        pos++;
    }

    pos--; // don't ask..
    return num;
}

std::vector<Token> tokenize(const std::string& in)
{
    std::vector<Token> tokens;

    StringPos pos = 0;
    while (pos < in.size()) {
        char c = in[pos];
        switch (c) {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            {
                auto start_pos = pos;
                int num = parse_number(in, &pos);
                tokens.emplace_back(Token::Number, start_pos, num);
                break;
            }

        case '+':
            tokens.emplace_back(Token::Pluss, pos);
            break;

        case '-':
            tokens.emplace_back(Token::Minus, pos);
            break;

        case '*':
            tokens.emplace_back(Token::Multiply, pos);
            break;

        case '/':
            tokens.emplace_back(Token::Divide, pos);
            break;

        case '(':
            tokens.emplace_back(Token::ParenOpen, pos);
            break;

        case ')':
            tokens.emplace_back(Token::ParenClose, pos);
            break;

        case ' ':
        case '\t':
            break; // ignore whitespace

        default:
            throw ParseError(compose("Unknown character '", c, "'"), pos);
        }

        pos++;
    }

    tokens.emplace_back(Token::EndOfInput, pos);
    return tokens;
}

/* The following code is a manually put together parser of the language
 * expressed bellow in BNF.
 *
 * <experssion> ::= <add-expr> [end of input]
 * <add-expr>   ::= <add-expr> '+' <mul-expr>
 *                | <add-expr> '-' <mul-expr>
 *                | <mul-expr>
 * <mul-expr>   ::= <mul-expr> '*' <paren-expr>
 *                | <mul-expr> '/' <paren-expr>
 *                | <paren-expr>
 * <paren-expr> ::= '(' <add-expr> ')'
 *                | <unary-expr>
 * <unary-expr> ::= '-' <number>
 *                | <number>
 */


int unary_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
    TokenPos& pos = *p_pos;

    Token t = tokens[pos];

    switch (t.type) {
    case Token::Number:
        pos++;
        return t.value;

    case Token::Minus:
        pos++;
        t = tokens[pos];
        if (t.type == Token::Number) {
            pos++;
            return -t.value;
        } else {
            throw SyntaxError(
                compose("Expected number but got ", t.type),
                t.pos
            );
        }

    case Token::ParenOpen:
    case Token::Pluss:
    case Token::Multiply:
    case Token::Divide:
    case Token::ParenClose:
    case Token::EndOfInput:
    default:
        throw SyntaxError(
            compose("Expected '-' or number but got ", t.type),
            t.pos
        );
    }
}

int add_expr(const std::vector<Token>& tokens, TokenPos* p_pos);

int paren_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
    TokenPos& pos = *p_pos;

    Token t = tokens[pos];

    switch (t.type) {
    case Token::Number:
    case Token::Minus:
        return unary_expr(tokens, &pos);
        break;

    case Token::ParenOpen:
        {
            pos++;
            int result = add_expr(tokens, &pos);
            t = tokens[pos];
            if (t.type == Token::ParenClose) {
                pos++;
                return result;
            } else {
                throw SyntaxError(
                    compose("Expected ')' but got ", t.type),
                    t.pos
                );
            }

            break;
        }

    case Token::Pluss:
    case Token::Multiply:
    case Token::Divide:
    case Token::ParenClose:
    case Token::EndOfInput:
    default:
        throw SyntaxError(
            compose("Expected number, '-' or '(', but got ", t.type),
            t.pos
        );
    }
}


int mul_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
    TokenPos& pos = *p_pos;

    int lhs = paren_expr(tokens, &pos);

    while (true) {
        Token t = tokens[pos];

        switch (t.type) {
        case Token::Multiply:
            pos++;
            lhs *= paren_expr(tokens, &pos);
            break;

        case Token::Divide:
            {
                pos++;
                int rhs = paren_expr(tokens, &pos);
                if (rhs == 0) {
                    throw DivideByZeroError("Divide by zero", t.pos);
                }
                lhs /= rhs;
                break;
            }

        case Token::Number:
        case Token::ParenOpen:
            throw SyntaxError(
                compose(
                    "Expected '+', '-', '*', '/' or end of input but got ",
                    t.type
                ),
                t.pos
            );


        case Token::Minus:
        case Token::Pluss:
        case Token::ParenClose:
        case Token::EndOfInput:
        default:
            return lhs;
        }
    }
}

int add_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
    TokenPos& pos = *p_pos;

    int lhs = mul_expr(tokens, &pos);

    while (true) {
        Token t = tokens[pos];

        switch (t.type) {
        case Token::Pluss:
            pos++;
            lhs += mul_expr(tokens, &pos);
            break;

        case Token::Minus:
            pos++;
            lhs -= mul_expr(tokens, &pos);
            break;

        case Token::Number:
        case Token::ParenOpen:
        case Token::Multiply:
        case Token::Divide:
            throw SyntaxError(
                compose(
                    "This cannot possibly happen, how did you get ", t.type,
                    " to trigger this?!?"),
                t.pos
            );

        case Token::ParenClose:
        case Token::EndOfInput:
        default:
            return lhs;
        }
    }
}

int expression(const std::vector<Token>& tokens)
{
    TokenPos pos = 0;

    int value = add_expr(tokens, &pos);
    Token t = tokens[pos];

    if (t.type == Token::EndOfInput) {
        return value;
    } else {
        throw SyntaxError(
            compose("Expected end of input but got ", t.type),
            t.pos
        );
    }
}

int main() {
    std::cout << "=== Hornwitser's silly calculator app v0.1 ===\n"
                 "\n"
                 "Supported operands are + - * / ( ) and unary -\n"
                 "Exit with \"quit\" or \"exit\".\n"
                 "\n";

    while (true) {
        std::cout << "> ";

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

        if (input == "quit" || input == "exit")
            break;

        std::vector<Token> tokens;
        try {
            tokens = tokenize(input);
        } catch (InputError e) {
            std::cout << std::string(e.pos+2, ' ') << "^\n";
            std::cout << e.what() << std::endl;
            continue;
        }

        if (tokens[0].type == Token::EndOfInput)
            continue;

        int result;

        try {
            result = expression(tokens);
        } catch (InputError e) {
            std::cout << std::string(e.pos+2, ' ') << "^\n";
            std::cout << e.what() << std::endl;
            continue;
        }

        std::cout << "= " << result << std::endl;
    }
}