enum TokenType {
    Plus,
    Minus,
    Multiply,
    Divide,
    Number,
    OpenBracket,
    CloseBracket
};
struct Token {
    TokenType type;
    std::string data;
    // other useful things
};
std::vector<Token> lex(std::string input) {
    std::unordered_map<char, TokenType> singles;
    singles['+'] = TokenType::Plus;
    singles['-'] = TokenType::Minus;
    singles['('] = TokenType::OpenBracket;
    singles[')'] = TokenType::CloseBracket;
    singles['*'] = TokenType::Multiply;
    singles['/'] = TokenType::Divide;
    std::unordered_set<char> whitespace;
    whitespace.insert(' ');
    whitespace.insert('\t');
    whitespace.insert('\r');
    whitespace.insert('\n');
    std::unordered_set<char> nums;
    for(int i = 0; i < 10; i++)
        nums.insert('0' + i);
    std::vector<Token> out;
    for(auto it = input.begin(); it != input.end(); ++it) {
        if (singles.find(*it) != singles.end()) {
            Token t;
            t.type = singles[*it];
            out.push_back(t);
            continue;
        }
        if (whitespace.find(*it) != whitespace.end()) {
            continue;
        }
        if (nums.find(*it) != nums.end()) {
            Token t;
            t.type = TokenType::Number;
            while(nums.find(*it) != nums.end()) {
                t.data.push_back(*it);
                ++it;
                if (it == input.end())
                    break;
            }
            out.push_back(t);
            continue;
        }
        // error
    }
    return out;
};
class Expression {
    virtual ~Expression() {}
};
class BinaryExpression : public Expression {
public:
     std::unique_ptr<Expression> lhs;
     std::unique_ptr<Expression> rhs;
     virtual char GetType() const = 0; // +,-,/,*
};
class MultiplyExpression : public BinaryExpression {
public:
    virtual char GetType() const { return '*'; }
};
class DivideExpression : public BinaryExpression {
public:
    virtual char GetType() const { return '/'; }
};
class PlusExpression : public BinaryExpression {
public:
    virtual char GetType() const { return '+'; }
};
class SubExpression : public BinaryExpression {
public:
    virtual char GetType() const { return '-'; }
};
class NumExpression : public Expression {
public:
    unsigned int num;
};
class Parser {
    std::vector<Token::iterator begin, end;
    std::unique_ptr<Expression> operator()() {
        return ParseMultiplicativeExpression();
    }
    void CheckedIncrement() {
        ++begin;
        if (begin == end) // fuck
    }
    std::unique_ptr<Expression> ParseMultiplicativeExpression() {
        // mul_expression ('*' '/') add_expression (left-associative)
        // add_expression
        auto lhs = ParseAdditiveExpression();
        while(true) {
            if (begin->type == TokenType::Multiply) {
                CheckedIncrement();
                auto rhs = ParseAdditiveExpression();
                auto expr = make_unique<MulExpression>();
                expr->lhs = lhs;
                expr->rhs = rhs;
                lhs = expr;
            }
            if (begin->type == TokenType::Divide) {
                CheckedIncrement();
                auto rhs = ParseAdditiveExpression();
                auto expr = make_unique<DivideExpression>();
                expr->lhs = lhs;
                expr->rhs = rhs;
                lhs = expr;
            }
            break; // not a valid mul expr anymore
        }
        return lhs;
    }
    std::unique_ptr<Expression> ParseAdditiveExpression() {
        // primary_expression ('+' '-') add_expression (right-associative)
        // primary_expression
        auto lhs = ParsePrimaryExpression();
        if (begin->type == TokenType::Plus) {
            CheckedIncrement();
            auto expr = make_unique<PlusExpression>();
            auto rhs = ParseAdditiveExpression();
            expr->lhs = lhs; expr->rhs = rhs;
            return expr;
        }
        if (begin->type == TokenType::Minus) {
            CheckedIncrement();
            auto expr = make_unique<SubExpression>();
            auto rhs = ParseAdditiveExpression();
            expr->lhs = lhs; expr->rhs = rhs;
            return expr;
        }
        // not avalid add expression
        return lhs;
    }
    std::unique_ptr<Expression> ParsePrimaryExpression() {
        if (begin->type == TokenType::Number) {
            // parse number from data here
            CheckedIncrement();
            return make_unique<NumExpression>();
        }
        if (begin->type == TokenType::OpenBracket) {
            CheckedIncrement();
            auto expr = ParseMultiplicativeExpression();
            if (begin->type != TokenType::CloseBracket) { } // fuck
            CheckedIncrement();
            return expr;
        }
    }
};
std::unique_ptr<Expression> Parse(std::vector<Token> tokens) {
    Parser p;
    p.begin = tokens.begin();
    p.end = tokens.end();
    return p();
}