#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <typeinfo>
#include <sstream>
#include <vector>
#include <stack>
#include <map>
#include <numeric>
#include <climits>
#include <cstdint>
#include <cctype>
#include <ctime>

#ifdef _WIN32
#define snprintf _snprintf
#endif

namespace CPlusPlusDice
{
	/* This class and the next 3 functions are used to convert between strings and other data types */
	/* Comes from the C++ FAQ, item 39.3: http://www.parashift.com/c++-faq/convert-string-to-any.html */
	class BadConversion : public std::runtime_error
	{
	public:
		BadConversion(const std::string &s) : std::runtime_error(s)
		{
		}
	};

	template<typename T> inline std::string stringify(const T &x)
	{
		std::ostringstream o;
		if (!(o << x))
			throw BadConversion(std::string("stringify(") + typeid(x).name() + ")");
		return o.str();
	}

	template<typename T> inline void convert(const std::string &s, T &x, bool failIfLeftoverChars = true)
	{
		std::istringstream i((s));
		char c;
		if (!(i >> x) || (failIfLeftoverChars && i.get(c)))
			throw BadConversion(s);
	}

	template<typename T> inline T convertTo(const std::string &s, bool failIfLeftoverChars = true)
	{
		T x;
		convert(s, x, failIfLeftoverChars);
		return x;
	}

	enum DICE_ERRS /* Error codes */
	{
		DICE_ERR_NONE,
		DICE_ERR_PARSE,
		DICE_ERR_DIV0,
		DICE_ERR_UNDEFINED,
		DICE_ERR_UNACCEPT_DICE,
		DICE_ERR_UNACCEPT_SIDES,
		DICE_ERR_UNACCEPT_TIMES,
		DICE_ERR_OVERUNDERFLOW,
		DICE_ERR_STACK
	};

	/* The following is for a case-insensitive string comparison */
	struct eq_str : std::binary_function<std::string, std::string, bool>
	{
		struct eq_char
		{
			const char *tab;
			eq_char(const char *t) : tab(t) { }
			bool operator()(char x, char y) const
			{
				return this->tab[x - CHAR_MIN] == this->tab[y - CHAR_MIN];
			}
		};

		char tab[CHAR_MAX - CHAR_MIN + 1];

		eq_str(const std::locale &L = std::locale::classic())
		{
			for (int i = CHAR_MIN; i <= CHAR_MAX; ++i)
				this->tab[i - CHAR_MIN] = static_cast<char>(i);
			std::use_facet<std::ctype<char> >(L).toupper(this->tab, this->tab + (CHAR_MAX - CHAR_MIN + 1));
		}

		bool operator()(const std::string &x, const std::string &y) const
		{
			return x.length() == y.length() && std::equal(x.begin(), x.end(), y.begin(), eq_char(this->tab));
		}

		size_t find(const std::string &x, const std::string &y) const
		{
			std::string::const_iterator found = std::search(x.begin(), x.end(), y.begin(), y.end(), eq_char(this->tab));
			if (found == x.end())
				return std::string::npos;
			else
				return found - x.begin();
		}
	};

	struct DiceServData
	{
		DICE_ERRS errCode;

		DiceServData() : errCode(DICE_ERR_NONE)
		{
		}
	};

	static const int DICE_MAX_TIMES = 25;
	static const unsigned DICE_MAX_DICE = 99999;
	static const unsigned DICE_MAX_SIDES = 99999;

	eq_str eqstr;

	/** sepstream allows for splitting token seperated lists.
	 * Each successive call to sepstream::GetToken() returns
	 * the next token, until none remain, at which point the method returns
	 * an empty string.
	 */
	class sepstream
	{
		/** Original string.
		 */
		std::string tokens;
		/** Seperator value
		 */
		char sep;
		/** Current string position
		 */
		size_t pos;
		/** If set then GetToken() can return an empty string
		 */
		bool allow_empty;
	public:
		/** Create a sepstream and fill it with the provided data
		 */
		sepstream(const std::string &source, char seperator, bool allowempty = false) : tokens(source), sep(seperator), pos(0), allow_empty(allowempty)
		{
		}

		/** Fetch the next token from the stream
		 * @param token The next token from the stream is placed here
		 * @return True if tokens still remain, false if there are none left
		 */
		bool GetToken(std::string &token)
		{
			if (this->StreamEnd())
			{
				token.clear();
				return false;
			}

			if (!this->allow_empty)
			{
				this->pos = this->tokens.find_first_not_of(this->sep, this->pos);
				if (this->pos == std::string::npos)
				{
					this->pos = this->tokens.length() + 1;
					token.clear();
					return false;
				}
			}

			size_t p = this->tokens.find(this->sep, this->pos);
			if (p == std::string::npos)
				p = this->tokens.length();

			token = this->tokens.substr(this->pos, p - this->pos);
			this->pos = p + 1;

			return true;
		}

		/** Gets token number 'num' from the stream
		 * @param token The token is placed here
		 * @param num The token number to featch
		 * @return True if the token was able to be fetched
		 */
		bool GetToken(std::string &token, int num)
		{
			int i;
			for (i = 0; i < num + 1 && this->GetToken(token); ++i);
			return i == num + 1;
		}

		/** Gets every token from this stream
		 * @param token Tokens are pushed back here
		 */
		template<typename T> void GetTokens(T &token)
		{
			token.clear();
			std::string t;
			while (this->GetToken(t))
				token.push_back(t);
		}

		/** Gets token number 'num' from the stream and all remaining tokens.
		 * @param token The token is placed here
		 * @param num The token number to featch
		 * @return True if the token was able to be fetched
		 */
		bool GetTokenRemainder(std::string &token, int num)
		{
			if (this->GetToken(token, num))
			{
				if (!this->StreamEnd())
					token += this->sep + this->GetRemaining();

				return true;
			}

			return false;
		}

		/** Determines the number of tokens in this stream.
		 * @return The number of tokens in this stream
		 */
		int NumTokens()
		{
			int i;
			std::string token;
			for (i = 0; this->GetToken(token); ++i);
			return i;
		}

		/** Fetch the entire remaining stream, without tokenizing
		 * @return The remaining part of the stream
		 */
		std::string GetRemaining() const
		{
			return !this->StreamEnd() ? this->tokens.substr(this->pos) : "";
		}

		/** Returns true if the end of the stream has been reached
		 * @return True if the end of the stream has been reached, otherwise false
		 */
		bool StreamEnd() const
		{
			return this->pos > this->tokens.length();
		}
	};

	/** A derived form of sepstream, which seperates on spaces
	 */
	class spacesepstream : public sepstream
	{
	public:
		/** Initialize with space seperator
		 */
		spacesepstream(const std::string &source) : sepstream(source, ' ') { }
	};

	/** Determine if the double-precision floating point value is infinite or not.
	 * @param num The double-precision floating point value to check
	 * @return true if the value is infinite, false otherwise
	 */
	static bool is_infinite(double num)
	{
#ifdef _WIN32
		int fpc = _fpclass(num);
		return fpc == _FPCLASS_NINF || fpc == _FPCLASS_PINF;
#else
		return std::isinf(num);
#endif
	}

	/** Determine if the double-precision floating point value is NaN (Not a Number) or not.
	 * @param num The double-precision floating point value to check
	 * @return true if the value is NaN, false otherwise
	 */
	static bool is_notanumber(double num)
	{
#ifdef _WIN32
		int fpc = _fpclass(num);
		return fpc == _FPCLASS_SNAN || fpc == _FPCLASS_QNAN;
#else
		return std::isnan(num);
#endif
	}

	/** Determine if the given character is a number.
	 * @param chr Character to check
	 * @return true if the character is a number, false otherwise
	 */
	static inline bool is_number(char chr) { return (chr >= '0' && chr <= '9') || chr == '.'; }
	/** Determine if the given character is a multiplication or division operator.
	 * @param chr Character to check
	 * @return true if the character is a multiplication or division operator, false otherwise
	 */
	static inline bool is_muldiv(char chr) { return chr == '%' || chr == '/' || chr == '*'; }
	/** Determine if the given character is an addition or subtraction operator.
	 * @param chr Character to check
	 * @return true if the character is an addition or subtraction operator, false otherwise
	 */
	static inline bool is_plusmin(char chr) { return chr == '+' || chr == '-'; }
	/** Determine if the given character is an operator of any sort, except for parenthesis.
	 * @param chr Character to check
	 * @return true if the character is a non-parenthesis operator, false otherwise
	 */
	static inline bool is_op_noparen(char chr) { return is_plusmin(chr) || is_muldiv(chr); }
	/** Determine if the given character is an operator of any sort.
	 * @param chr Character to check
	 * @return true if the character is an operator, false otherwise
	 */
	static inline bool is_operator(char chr) { return chr == '(' || chr == ')' || is_op_noparen(chr); }
	/** Determine if the given operator has a higher precendence than the operator on the top of the stack during infix to postfix conversion.
	 * @param adding The operator we are adding to the stack, or an empty string if nothing is being added and we just want to remove
	 * @param topstack The operator that was at the top of the operator stack
	 * @return 0 if the given operator has the same or lower precendence (and won't cause a pop), 1 if the operator has higher precendence (and will cause a pop)
	 *
	 * In addition to the above in regards to the return value, there are other situations. If the top of the stack is an open parenthesis,
	 * or is empty, a 0 will be returned to stop the stack from popping anything else. If nothing is being added to the stack and the previous
	 * sitation hasn't occurred, a 1 will be returned to signify to continue popping the stack until the previous sitation occurs. If the operator
	 * being added is a function, we return 0 to signify we aren't popping. If the top of the stack is a function, we return 1 to signify we are
	 * popping. A -1 is only returned if an invalid operator is given, hopefully that will never happen.
	 */
	static inline int would_pop(const std::string &adding, const std::string &topstack)
	{
		if (adding.empty())
			return topstack.empty() || topstack == "(" ? 0 : 1;
		if (topstack.empty() || topstack == "(")
			return 0;
		if (topstack == adding && adding != "^")
			return 1;
		switch (adding[0])
		{
			case 'd':
				return 0;
			case '^':
				return /*topstack == "^" || */eqstr(topstack, "d") ? 1 : 0;
			case '%':
			case '/':
			case '*':
				return topstack == "^" || eqstr(topstack, "d") || is_muldiv(topstack[0]) ? 1 : 0;
			case '+':
			case '-':
				return is_op_noparen(topstack[0]) ? 1 : 0;
		}
		return -1;
	}

	/** Tokenize an infix notation equation by adding spaces between operators.
	 * @param infix The original infix notation equation to tokenize
	 * @return A new infix notation equation with spaces between operators
	 */
	static std::string TokenizeInfix(const std::string &infix)
	{
		std::string newinfix;
		for (unsigned x = 0, len = infix.length(); x < len; ++x)
		{
			char curr = infix[x];
			if (is_operator(curr))
			{
				if (x && !newinfix.empty() && newinfix[newinfix.length() - 1] != ' ')
					newinfix += ' ';
				newinfix += curr;
				if (x != len - 1)
					newinfix += ' ';
			}
			else
				newinfix += curr;
		}
		return newinfix;
	}

	/** Enumeration for PostfixValue to determine it's type */
	enum PostfixValueType
	{
		POSTFIX_VALUE_NONE,
		POSTFIX_VALUE_DOUBLE,
		POSTFIX_VALUE_STRING
	};

	/** Base class for values in a postfix equation */
	class PostfixValueBase
	{
		PostfixValueType type;
	protected:
		virtual void Clear() = 0;
	public:
		PostfixValueBase() : type(POSTFIX_VALUE_NONE) { }
		PostfixValueBase(PostfixValueType Type) : type(Type) { }
		virtual ~PostfixValueBase() { }
		PostfixValueType Type() const { return this->type; }
		virtual PostfixValueBase *Clone() const = 0;
		virtual bool operator==(const PostfixValueBase &) const = 0;
		bool operator!=(const PostfixValueBase &Val) const { return !this->operator==(Val); }
	};

	/** Version of PostfixValue for double */
	class PostfixValueDouble : public PostfixValueBase
	{
		double *val;
	protected:
		void Clear()
		{
			delete val;
		}
	public:
		PostfixValueDouble() : PostfixValueBase(POSTFIX_VALUE_DOUBLE), val(NULL) { }
		PostfixValueDouble(double Val) : PostfixValueBase(POSTFIX_VALUE_DOUBLE), val(new double(Val)) { }
		PostfixValueDouble(const PostfixValueDouble &Val) : PostfixValueBase(POSTFIX_VALUE_DOUBLE),
			val(Val.val ? new double(*Val.val) : NULL) { }
		~PostfixValueDouble() { this->Clear(); }
		PostfixValueDouble &operator=(const PostfixValueDouble &Val)
		{
			if (this != &Val && Val.val)
			{
				if (this->val)
					*this->val = *Val.val;
				else
					this->val = new double(*Val.val);
			}
			return *this;
		}
		const double *Get() const
		{
			return this->val;
		}
		PostfixValueDouble *Clone() const { return new PostfixValueDouble(*this); }
		bool operator==(const PostfixValueBase &Val) const
		{
			auto DblVal = dynamic_cast<const PostfixValueDouble *>(&Val);
			if (!DblVal)
				return false;

			if (!this->val || !DblVal->val)
				return false;

			return *this->val == *DblVal->val;
		}
	};

	/** Version of PostfixValue for Anope::string */
	class PostfixValueString : public PostfixValueBase
	{
		std::string *val;
	protected:
		void Clear()
		{
			delete val;
		}
	public:
		PostfixValueString() : PostfixValueBase(POSTFIX_VALUE_STRING), val(NULL) { }
		PostfixValueString(const std::string &Val) : PostfixValueBase(POSTFIX_VALUE_STRING),
			val(new std::string(Val)) { }
		PostfixValueString(const PostfixValueString &Val) : PostfixValueBase(POSTFIX_VALUE_STRING),
			val(Val.val ? new std::string(*Val.val) : NULL) { }
		~PostfixValueString() { this->Clear(); }
		PostfixValueString &operator=(const PostfixValueString &Val)
		{
			if (this != &Val && Val.val)
			{
				if (this->val)
					*this->val = *Val.val;
				else
					this->val = new std::string(*Val.val);
			}
			return *this;
		}
		const std::string *Get() const
		{
			return this->val;
		}
		PostfixValueString *Clone() const { return new PostfixValueString(*this); }
		bool operator==(const PostfixValueBase &Val) const
		{
			auto StrVal = dynamic_cast<const PostfixValueString *>(&Val);
			if (!StrVal)
				return false;

			if (!this->val || !StrVal->val)
				return false;

			return *this->val == *StrVal->val;
		}
	};

	/** Container for the list of Postfix values */
	class Postfix
	{
		std::vector<PostfixValueBase *> values;
		size_t valueSize;
	public:
		Postfix() : values(), valueSize(0) { }
		Postfix(const Postfix &postfix) : values(), valueSize(0)
		{
			this->append(postfix);
		}
		Postfix &operator=(const Postfix &postfix)
		{
			if (this != &postfix)
			{
				this->clear();
				this->append(postfix);
			}
			return *this;
		}
		~Postfix() { this->clear(); }
		void clear()
		{
			for (size_t y = 0; y < this->valueSize; ++y)
				delete this->values[y];
			this->values.clear();
		}
		void add(double dbl)
		{
			this->values.push_back(new PostfixValueDouble(dbl));
			++this->valueSize;
		}
		void add(const std::string &str)
		{
			this->values.push_back(new PostfixValueString(str));
			++this->valueSize;
		}
		void append(const Postfix &postfix)
		{
			for (size_t y = 0; y < postfix.valueSize; ++y)
				this->values.push_back(postfix.values[y]->Clone());
			this->valueSize += postfix.valueSize;
		}
		bool empty() const
		{
			return !this->valueSize;
		}
		size_t size() const
		{
			return this->valueSize;
		}
		PostfixValueBase *operator[](unsigned index)
		{
			if (index >= this->valueSize)
				return NULL;
			return this->values[index];
		}
		const PostfixValueBase *operator[](unsigned index) const
		{
			if (index >= this->valueSize)
				return NULL;
			return this->values[index];
		}
		bool operator==(const Postfix &postfix) const
		{
			if (this->valueSize != postfix.valueSize)
				return false;

			for (size_t x = 0; x < this->valueSize; ++x)
				if (*this->values[x] != *postfix.values[x])
					return false;

			return true;
		}
	};

	/** Convert an infix notation equation to a postfix notation equation, using the shunting-yard algorithm.
	 * @param infix The infix notation equation to convert
	 * @return A postfix notation equation
	 *
	 * Numbers are always stored in the postfix notation equation immediately, and operators are kept on a stack until they are
	 * needed to be added to the postfix notation equation.
	 * The conversion process goes as follows:
	 * - Iterate through the infix notation equation, doing the following on each operation:
	 *   - When a number is encountered, add it to the postfix notation equation.
	 *   - When an operator is encountered:
	 *     - Check if we had any numbers prior to the operator, and fail if there were none.
	 *     - Always add open parentheses to the operator stack.
	 *     - When a close parenthesis is encountered, pop all operators until we get to an open parenthesis or the stack becomes empty, failing on the latter.
	 *     - For all other operators, pop the stack if needed then add the operator to the stack.
	 *   - If anything else is encountered, fail as it is an invalid value.
	 * - If there were operators left on the operator stack, pop all of them, failing if anything is left on the stack (an open parenthesis will cause this).
	 */
	static Postfix InfixToPostfix(const std::string &infix)
	{
		Postfix postfix;
		unsigned len = infix.length(), x = 0;
		bool prev_was_close = false, prev_was_number = false;
		std::stack<std::string> op_stack;
		spacesepstream tokens(infix);
		std::string token, lastone;
		while (tokens.GetToken(token))
		{
			if (is_number(token[0]))
			{
				double number = atof(token.c_str());
				postfix.add(number);
				prev_was_number = true;
			}
			else if (is_operator(token[0]))
			{
				lastone = op_stack.empty() ? "" : op_stack.top();
				prev_was_number = false;
				if (token == "(")
				{
					op_stack.push(token);
					prev_was_close = false;
				}
				else if (token == ")")
				{
					while (would_pop(token, lastone))
					{
						postfix.add(lastone);
						op_stack.pop();
						lastone = op_stack.empty() ? "" : op_stack.top();
					}
					op_stack.pop();
					prev_was_close = true;
				}
				else
				{
					if (!would_pop(token, lastone))
						op_stack.push(token);
					else
					{
						while (would_pop(token, lastone))
						{
							postfix.add(lastone);
							op_stack.pop();
							lastone = op_stack.empty() ? "" : op_stack.top();
						}
						op_stack.push(token);
					}
					prev_was_close = false;
				}
			}
			x += token.length() + (x ? 1 : 0);
		}
		if (!op_stack.empty())
		{
			lastone = op_stack.top();
			while (would_pop("", lastone))
			{
				postfix.add(lastone);
				op_stack.pop();
				if (op_stack.empty())
					break;
				else
					lastone = op_stack.top();
			}
		}
		return postfix;
	}

	/** Evaluate a postfix notation equation.
	 * @param The postfix notation equation to evaluate
	 * @return The final result after calcuation of the equation
	 *
	 * The evaluation pops 2 values from the operand stack for an operator. The result
	 * of either one is placed back on the operand stack, hopefully leaving a single result at the end.
	 */
	static double EvaluatePostfix(DiceServData &data, const Postfix &postfix)
	{
		double val = 0;
		std::stack<double> num_stack;
		for (unsigned x = 0, len = postfix.size(); x < len; ++x)
		{
			if (postfix[x]->Type() == POSTFIX_VALUE_STRING)
			{
				const PostfixValueString *str = dynamic_cast<const PostfixValueString *>(postfix[x]);
				const std::string *token_ptr = str->Get();
				std::string token = token_ptr ? *token_ptr : "";
				if (is_operator(token[0]) && token.length() == 1)
				{
					double val2 = num_stack.top();
					num_stack.pop();
					double val1 = num_stack.top();
					num_stack.pop();
					switch (token[0])
					{
						case '+':
							val = val1 + val2;
							break;
						case '-':
							val = val1 - val2;
							break;
						case '*':
							val = val1 * val2;
							break;
						case '/':
							if (!val2)
							{
								data.errCode = DICE_ERR_DIV0;
								return 0;
							}
							// Forcefully doing integer division
							val = static_cast<int>(val1) / static_cast<int>(val2);
							break;
					}
					num_stack.push(val);
				}
			}
			else
			{
				const PostfixValueDouble *dbl = dynamic_cast<const PostfixValueDouble *>(postfix[x]);
				const double *val_ptr = dbl->Get();
				num_stack.push(*val_ptr);
			}
		}
		val = num_stack.top();
		num_stack.pop();
		return val;
	}

	/** Parse an infix notation expression and convert the expression to postfix notation.
	 * @param infix The original expression, in infix notation, to convert to postfix notation
	 * @return A postfix notation expression equivilent to the infix notation expression given, or an empty string if the infix notation expression could not be parsed or converted
	 */
	static Postfix DoParse(const std::string &infix)
	{
		return InfixToPostfix(TokenizeInfix(infix));
	}

	/** Evaluate a postfix notation expression.
	 * @param postfix The postfix notation expression to evaluate
	 * @return The final result after evaluation
	 */
	static double DoEvaluate(DiceServData &data, const Postfix &postfix)
	{
		return EvaluatePostfix(data, postfix);
	}
}

/* Prime constants for each spell level */
int primes[][3] =
{
	{ 3, 5, 7 }, // Level 1
	{ 11, 13, 17 }, // Level 2
	{ 19, 23, 29 }, // Level 3
	{ 31, 37, 41 }, // Level 4
	{ 43, 47, 53 }, // Level 5
	{ 59, 61, 67 }, // Level 6
	{ 71, 73, 79 }, // Level 7
	{ 83, 89, 97 }, // Level 8
	{ 101, 103, 107 }, // Level 9
};

/* A structure to hold which parentheses level was used in a combination as well as the index from that level within the vector.
 * Mainly used to filter out things when we get to 3 or more parentheses in a single combination. */
struct Combine
{
	int parens, index;

	Combine() : parens(0), index(0)
	{
	}
	Combine(int p, int i) : parens(p), index(i)
	{
	}

	bool operator==(const Combine &other) const
	{
		return this->parens == other.parens && this->index == other.index;
	}
};

/* Structure to store the number of open parentheses and close parentheses at a given spot */
struct Parens
{
	int opens, closes;

	Parens() : opens(0), closes(0)
	{
	}
	Parens(int o, int c) : opens(o), closes(c)
	{
	}

	bool operator==(const Parens &other) const
	{
		return this->opens == other.opens && this->closes == other.closes;
	}
};

/* Structure to hold the map of parentheses as well as what was combined to make the map */
struct ParensMap
{
	typedef std::map<int, Parens> Map;
	Map map;
	Combine combine1, combine2;

	ParensMap() : map(), combine1(), combine2()
	{
	}
	ParensMap(Map m) : map(m), combine1(), combine2()
	{
	}
	ParensMap(Map m, int c1p, int c1i, int c2p, int c2i) : map(m), combine1(c1p, c1i), combine2(c2p, c2i)
	{
	}
};

/* Calculates the parentheses combinations for the given number of operands */
std::vector<ParensMap> CalculateParentheses(int operands)
{
	/* The maximum number of parentheses that can exist over all combinations will always be 2 less than the number of operands */
	int maxParens = operands - 2;
	std::vector<ParensMap> parens;
	std::map<int, std::vector<ParensMap>> prevParens;
	/* Iterate from 1 set of parentheses up to the maximum number of parentheses */
	for (int currParens = 1; currParens <= maxParens; ++currParens)
	{
		/* Special case for 1 set of parentheses. We basically go from the first operand to the second to last operand for
		 * the open parentheses, and for each of those operands, we go from the next operand to the last one (or second to
		 * last in the case of the first operand) and put a close parentheses there. */
		if (currParens == 1)
		{
			for (int i = 0; i < operands - 1; ++i)
				for (int j = i + 1; j < operands - (i ? 0 : 1); ++j)
				{
					ParensMap::Map thisParens;
					thisParens.insert(std::make_pair(i, Parens(1, 0)));
					thisParens.insert(std::make_pair(j, Parens(0, 1)));
					parens.push_back(ParensMap(thisParens));
					prevParens[1].push_back(ParensMap(thisParens));
				}
		}
		else
		{
			/* We will be iterating over previous numbers of parentheses and combining them to form combinations containing
			 * more parentheses. This is basically combining the parentheses combinations for 1 less than the number we want
			 * with the parentheses combinations for 1 set of parentheses.
			 *
			 * Special case when we have 2 sets of parentheses, though, since we are combining from the 1 set of parentheses
			 * lists, the outer loop will exclude the last combination while the inner loop will only look at all combinations
			 * after the start of the outer loop. */
			int prevLevelLen = prevParens[currParens - 1].size();
			if (currParens == 2)
				--prevLevelLen;
			int firstLevelLen = prevParens[1].size();
			/* Outer loop for the previous number of parentheses combinations */
			for (int prev = 0; prev < prevLevelLen; ++prev)
			{
				auto prevParen = prevParens[currParens - 1][prev];
				/* To try to prevent some forms of combinations that would duplicate parentheses too much,
				 * skip over this one if that would happen. */
				if (prevParen.combine1 == Combine(1, prev) || prevParen.combine2 == Combine(1, prev))
					continue;
				/* Inner loop for the 1 set of parentheses combinations */
				for (int first = (currParens == 2 ? prev + 1 : 0); first < firstLevelLen; ++first)
				{
					/* Similar check to the one above, except using the inner loop's value instead */
					if (prevParen.combine1 == Combine(1, first) || prevParen.combine2 == Combine(1, first))
						continue;
					auto firstParen = prevParens[1][first];
					int i = 0;
					ParensMap::Map thisParens;
					/* Iterate over the operands and figure out the number of open parentheses and close parentheses that we
					 * get from combining the two sets. We stop processing (and thus skip the combination) if any operand
					 * ends up with both open and close parentheses on it, and we only add the operand's combination if
					 * at least 1 open or 1 close parentheses was created. */
					for (; i < operands; ++i)
					{
						int opens = prevParen.map[i].opens + firstParen.map[i].opens;
						int closes = prevParen.map[i].closes + firstParen.map[i].closes;
						if (opens && closes)
							break;
						if (opens || closes)
							thisParens.insert(std::make_pair(i, Parens(opens, closes)));
					}
					if (i != operands)
						continue;
					/* This is a special case check, if the first operand contains an open parentheses and the last operand
					 * contains a close parentheses, then we will remove the outer-most ones and check the combinations over. */
					if (thisParens.count(0) && thisParens.count(operands - 1))
					{
						auto thisParensCopy = thisParens;
						if (thisParensCopy[0].opens == 1)
							thisParensCopy.erase(0);
						else
							--thisParensCopy[0].opens;
						if (thisParensCopy[operands - 1].closes == 1)
							thisParensCopy.erase(operands - 1);
						else
							--thisParensCopy[operands - 1].closes;
						/* If, after the outer parenthese removal, this causes the parentheses combination to match one
						 * of the previous level's combinations, then we won't be using it as it can be considered a duplicate. */
						auto foundParens = std::find_if(prevParens[currParens - 1].begin(), prevParens[currParens - 1].end(), [&](const ParensMap &prev) { return prev.map == thisParensCopy; });
						if (foundParens != prevParens[currParens - 1].end())
							continue;
						/* This section is to check if removing those outer parentheses would cause there to be an imbalance
						 * in the parentheses, like going from (1+2)+(1+2) to 1+2)+(1+2. If that happens, then the combination
						 * can be considered valid, otherwise, we'll just skip it as it probably won't be required. */
						int totalOpens = 0;
						int j = 1;
						for (; j < operands - 2; ++j)
						{
							totalOpens += thisParensCopy[j].opens;
							totalOpens -= thisParensCopy[j].closes;
							if (totalOpens < 0)
								break;
						}
						if (j == operands - 2)
							continue;
					}
					/* Finally, we check to make sure that the combination we finally have hasn't already been a combination
					 * for this number of parentheses, and if it isn't found, we add it to the list. */
					auto foundPrevParens = std::find_if(prevParens[currParens].begin(), prevParens[currParens].end(), [&](const ParensMap &prev) { return prev.map == thisParens; });
					if (foundPrevParens == prevParens[currParens].end())
					{
						parens.push_back(ParensMap(thisParens, currParens - 1, prev, 1, first));
						prevParens[currParens].push_back(ParensMap(thisParens, currParens - 1, prev, 1, first));
					}
				}
			}
		}
	}
	return parens;
}

int main(int argc, char *argv[])
{
	/* Requires at least 2 arguments */
	if (argc < 3)
	{
		std::cerr << "Syntax: " << argv[0] << " <spell level, 1-9> <dice rolls>\n";
		return 1;
	}
	/* Get the spell level and the dice rolls */
	int spellLevel = CPlusPlusDice::convertTo<int>(argv[1]) - 1;
	std::vector<int> ints;
	for (int x = 2; x < argc; ++x)
		ints.push_back(CPlusPlusDice::convertTo<int>(argv[x]));

	std::cout << "Attempting to match to prime constants of spell level " << (spellLevel + 1) << ":\n";
	std::cout << "  " << primes[spellLevel][0] << ' ' << primes[spellLevel][1] << ' ' << primes[spellLevel][2] << '\n';

	int operands = ints.size();

	/* When we have only 1 dice roll, the check is very simple, just compare to the prime constants of the spell level */
	if (operands == 1)
	{
		if (ints[0] != primes[spellLevel][0] && ints[0] != primes[spellLevel][1] && ints[0] != primes[spellLevel][2])
			std::cout << "No match found.";
		else
			std::cout << "Mach found! " << ints[0] << " -> " << ints[0] << '\n';
		return 0;
	}

	/* The dice rolls need to be sorted before we start, so permutations can be found correctly */
	std::sort(ints.begin(), ints.end());

	/* This is just to make it easier to get the next operator when iterating through the operators */
	std::map<char, char> nextOperator;
	nextOperator['+'] = '-';
	nextOperator['-'] = '*';
	nextOperator['*'] = '/';

	/* Calculate the possible parentheses combinations for the number of dice rolls we have */
	auto parens = CalculateParentheses(operands);

	bool foundMatch = false;
	auto finalOperators = std::vector<char>(operands - 1, '/');
	int numParens = parens.size();
	/* Iterate over all the permutations of the dice rolls */
	do
	{
		/* We start off with all plus operators and will end this permutation when all the operators end up being division operators */
		std::vector<std::pair<std::string, CPlusPlusDice::Postfix>> equations;
		auto operators = std::vector<char>(operands - 1, '+');
		do
		{
			/* Iterate over all the parentheses combinations, including an additional loop for no parentheses */
			for (int paren = -1; paren < numParens; ++paren)
			{
				/* Build the expression string */
				std::ostringstream str;
				for (int i = 0; i < operands; ++i)
				{
					if (i)
						str << operators[i - 1];
					if (paren != -1 && parens[paren].map.count(i) && parens[paren].map[i].opens)
						str << std::string(parens[paren].map[i].opens, '(');
					str << ints[i];
					if (paren != -1 && parens[paren].map.count(i) && parens[paren].map[i].closes)
						str << std::string(parens[paren].map[i].closes, ')');
				}

				/* Parse the infix-notation expression into a postfix-notation expression */
				std::string diceStr = str.str();

				auto postfix = CPlusPlusDice::DoParse(diceStr);

				/* As long as the postfix-notation expression isn't empty (which shouldn't happen), add it to the list of expressions, unless it is a duplicate */
				/*if (!postfix.empty())
				{
					auto exists = std::find_if(equations.begin(), equations.end(), [&](const std::pair<std::string, CPlusPlusDice::Postfix> &equation) { return equation.second == postfix; });
					if (exists == equations.end())*/
						equations.push_back(std::make_pair(diceStr, postfix));
				/*}*/
			}

			/* Once we reach a point where all the operators are division operators, we break from this loop */
			if (operators == finalOperators)
				break;

			/* Go to the next operator combination, by finding the first non-division operator from the end,
			 * and changing all operators after that one to plus operators (which will happen when they were division operators) */
			for (int i = operands - 2; i >= 0; --i)
			{
				if (operators[i] == '/')
					continue;
				operators[i] = nextOperator[operators[i]];
				for (int j = i + 1; j < operands - 1; ++j)
					operators[j] = '+';
				break;
			}
		} while (true);

		/* Iterate over the non-duplicated equations to evaluate them */
		std::for_each(equations.begin(), equations.end(), [&](const std::pair<std::string, CPlusPlusDice::Postfix> &postfix)
		{
			CPlusPlusDice::DiceServData data;
			double v = CPlusPlusDice::DoEvaluate(data, postfix.second);
			/* We consider the evaluation a match if it matches any of the prime constants for the spell level */
			if (data.errCode == CPlusPlusDice::DICE_ERR_NONE && (v == primes[spellLevel][0] || v == primes[spellLevel][1] || v == primes[spellLevel][2]))
			{
				std::cout << "Match: " << postfix.first << " -> " << v << '\n';
				foundMatch = true;
			}
		});
	} while (std::next_permutation(ints.begin(), ints.end()));
	
	/* Just another message to show if no matches were found */
	if (!foundMatch)
		std::cout << "No matches found.\n";

	return 0;
}