// Example program
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <cmath>
#include <utility>
#include <memory>

template <typename T>
bool is_any_of(T str, std::vector<T> valid)
{
	for (auto &v: valid)
		if (str == v)
			return true;

	return false;
}

bool is_number(std::string str)
{
	if (!str.size())
		return false;

	for (auto c: str)
		if (!isdigit(c) && c != '.')
			return false;

	return true;
}

std::vector<char> OP_AS_CHAR = {'+', '-', '*', '/', '^'};
std::vector<std::string> OP_AS_STR = {"+", "-", "*", "/", "^"};

class Expr;
class Literal;
class Nud;
class Op;

struct Source {
	std::string line, buffer;
	unsigned int cursor, start;

	Source(std::string line)
	: line(line), cursor(0), start(0), buffer("")
	{ };

	void accept() { buffer.clear(); };
	std::string peek_next()
	{
		return (buffer = get_next());
	}

	std::string get_next() {
		if (!buffer.empty()) {
			std::string tmp = buffer;
			buffer.clear();
			return tmp;
		}

		while(cursor < line.size() && isspace(line[cursor]))
			cursor++;

		if (cursor >= line.size())
			return "";

		start = cursor;
		if (is_any_of(line[cursor], {OP_AS_CHAR}) || line[cursor] == '(' || line[cursor] == ')') {
			cursor++;
		} else if (isdigit(line[cursor])) {
			do {
				cursor++;
			} while(cursor < line.size() && (isdigit(line[cursor]) || line[cursor] == '.'));
		}

		return std::string(line.begin() + start, line.begin() + cursor);
	};
};

class IExpr {
public:
	virtual float visit() = 0;
};

class Literal: public IExpr {
	std::string lexeme;

public:
	Literal(std::string lexeme) {
		this->lexeme = lexeme;
	};
	~Literal() { };

	float visit() { return std::stod(lexeme); };
};

class Nud: public IExpr {
	IExpr *expr;

public:
	Nud(IExpr *expr) : expr(expr) { };
	~Nud() {
		if (expr) delete expr;
	};
	float visit() { return -expr->visit(); };
};

class Op: public IExpr {
	IExpr *lval;
	std::string lexeme;
	IExpr *rval;

public:
	Op(IExpr *lval, std::string op, IExpr *rval) : lval(lval), rval(rval), lexeme(op) { };
	~Op() {
		if (lval) delete lval;
		if (rval) delete rval;
	};

	float visit() {
		float l = lval->visit();
		float r = rval->visit();

		if (lexeme == "+") return (l + r);
		if (lexeme == "-") return (l - r);
		if (lexeme == "*") return (l * r);
		if (lexeme == "/") return (l / r);
		if (lexeme == "^") return pow(l, r);
	};
	bool parse(Source &src, int lbp);
};

std::vector<std::pair<int, std::vector<std::string>>> OpPrec = {
	{0, {"+", "-"}},
	{0, {"*", "/"}},
	{1, {"^"}},
};

std::pair<int, int> get_binding(std::string op)
{
	int power = 0;
	for (auto &entry: OpPrec) {
		power++;
		if (is_any_of(op, entry.second))
			return {power, entry.first};
	}

	return {-1, 0};
}

IExpr *parse_expr(Source &src, int lbp);
IExpr *parse_nud(Source &src);

IExpr *parse_nud(Source &src)
{
	int neg = 0;
	std::unique_ptr<IExpr> nud;
	std::string token = src.get_next();
	if (token == "-") {
		neg = 1;
		token = src.get_next();
	}

	if (token == "(") {
		nud = std::unique_ptr<IExpr>(parse_expr(src, 0));
		if (!nud)
			return NULL;

		if (src.get_next() != ")") {
			std::cout << "Unbalanced parenthesis.\n";
			return NULL;
		}
	} else if (is_number(token)) {
		nud = std::unique_ptr<IExpr>(new Literal(token));
	}

	if (neg)
		return new Nud(nud.release());
	else
		return nud.release();
}

IExpr *parse_expr(Source &src, int lbp)
{
	std::unique_ptr<IExpr> lval;
	IExpr *rval = NULL;
	std::string lookahead;

	lval = std::unique_ptr<IExpr>(parse_nud(src));
	if (!lval)
		return NULL;

	for (;;) {
		lookahead = src.peek_next();

		if (is_any_of(lookahead, OP_AS_STR)) {
			auto bp = get_binding(lookahead);

			if (bp.first + bp.second > lbp) {
				src.accept();
				rval = parse_expr(src, bp.first);
				if (!rval)
					return NULL;

				lval = std::unique_ptr<IExpr>(new Op(lval.release(), lookahead, rval));
			}
			else {
				return lval.release();
			}
		} else {
			return lval.release();
		}
	}

	return lval.release();
}

#define M(c) {#c, c},
std::vector<std::pair<std::string, float>> test_suite = {
	M(10)
	M(10 + 10)
	M(-(10) + 10)
	{"2+2*3^2", 2+2*pow(3,2)},
	{"2^2*2-2", pow(2,2)*2-2},
	M(2 - 2 / 3.0 + 3 * -(2+2))
	M(2*3/2-1+7+2/2+3+3-3-2/3.0)
	M(2*3/2)
	{"11 - (13 - 13) ^ 2 + 13 + 10 + 7 + 6", 47},
	{"(5+15) + 6 / 15 + 9 ^ 2 + 11 ^ 2 + 9", 231.4},
	{"8 + 10 ^ 2 + 5 * (12 - 10) * 6 / 7", 116.571428571},
	{"2^3^4 / 100", pow(2,pow(3,4)) / 100}
};
#undef M

int main(int argc, char *argv[])
{
	for (auto p: test_suite)
	{
		Source src(p.first);

		std::unique_ptr<IExpr> expr(parse_expr(src, 0));
		if (!expr) {
			std::cout << "parse failed for \"" << p.first << "\"." << std::endl;
			continue;
		}

		float ret = expr->visit();
		std::cout << p.first << " = " << ret << " " << (ret == p.second ? "(ok)": "(failed)") << " => " << p.second <<  std::endl;
	}
}