String Calculator


#1

EJFace

Not sure if the title accurately explains what this is.

Let me know if there are any issues/features you’d like. You’re free to use this with or without credit, so go mad!

In short, this will take any string input and output a number, such that "1" = 1, "1+1" = 2, "a=2;a+1" = 3 and "max(1,2)" = 2, useful when loadstring isn’t enabled.

This is useful for converting user-input into a number while supporting math functionality.

The following is supported:

  1. + - * / % ^ ! in the BIDMAS (BODMAS for non-UK?) order "(16*3)-8/4"=46
  2. Nested brackets "((1+1)*(2+2))*2"=16
  3. Math functions "max(1,2)"=2 – supports any function in the math. library, just put the name of the function without the math. before it
  4. Math variables "pi*2"=6.2831... – supports any variable in the math. library, just put the name of the variable without math. before it
  5. Supports variables "a=1;b=a*2;a+b"=3
  6. Supports functions "a(x,y)=x*5/y;a(5+1,2)"=15 "func(a)=a*pi/2;a(17)"=6.703537555513
  7. Has a set of default functions, Round, Truncate, Approach

You can get/require the following model ( It returns a function that you pass the string to ):

The code is also up on github:

Example of how I’m using it for number arguments in my admin:
image
image

local Calc = require( CalcModule )

function Calculate( String )
	
	local Ran, Num = pcall( Calc, String )
	
	if not Ran then return "Invalid formula" end
	
	return Num
	
end

print(Calculate("1+1*15")) --> 16

[LIVE] Upcoming changes to the Developer Forums
#2

Fixed issues with 0/0 and math.huge, now works correctly :slight_smile:


#3

Nice! I might use this. I wrote a slightly different implementation where functions with single arguments could be called just by sticking them together (e.g., cos x) and multiplications could be done by sticking them together (e.g., 5x). I also didn’t support the assignment operator, but that’s a nice feature. :slight_smile:

Could you add some documentation to the “Calculate” function so I can use it as-is? What’s Recursion? LocalVars? LocalFuncs?

EDIT: looks like I also support commas which are nice when you have a single text box to input values for vector3s.

Here’s my source:

Summary
function Debug() end

local PATTERNS = {
	hex = "^[ \t\r\n]*0x[0-9A-Fa-f]+";
	binary = "^[ \t\r\n]*0b[01]+";
	octal = "^[ \t\r\n]*0[0-7]+";
	decimal = "^[ \t\r\n]*[0-9]+%.?[0-9]*";
	decimal2 = "^[ \t\r\n]*%.?[0-9]+";
	operator = "^[ \t\r\n]*[-+*/^%%]";
	paren = "^[ \t\r\n]*[%(%)]";
	comma = "^[ \t\r\n]*[,]";
	variable = "^[ \t\r\n]*[a-zA-Z_][a-zA-Z_0-9]*";
};
local SPECIAL_FUNCTIONS = {
	cos = true;
	sin = true;
	tan = true;
	acos = true;
	asin = true;
	atan = true;
	atan2 = true;
	log2 = true;
	log10 = true;
	ln = true;
	exp = true;
};
local SPECIAL_VARIABLES = {
	pi = math.pi;
	inf = math.huge;
	e = 2.7182818284;
};

--[[ @brief Convert a string expression into a list of tokens.
     @param expr The expression to convert.
     @return An array containing the tokens themselves.
     @return A parallel array containing the classes of tokens. Values include number, operator, function, paren, comma, and variable.
     @note If an error occurs, the value false & a string error code will be returned.
--]]
function Tokenize(expr)
	local TokenStream = {};
	local TokenType = {};
	while #expr > 0 do
		local len = #expr;
		Debug("Searching for pattern at %s", expr);
		for i, v in pairs(PATTERNS) do
			local token = expr:match(v);
			if token then
				expr = expr:sub(#token+1);
				token = token:gsub("^[ \t\r\n]+", "");
				Debug("Pattern match at %s (%s)", token, i);
				if i=="hex" then
					i = "number";
					token = tonumber(token:sub(3), 16);
				elseif i=="binary" then
					i = "number";
					token = tonumber(token:sub(3), 2);
				elseif i=="octal" then
					i = "number";
					token = tonumber(token:sub(2), 8);
				elseif i=="decimal" or i=="decimal2" then
					i = "number";
					token = tonumber(token);
				end
				if i=="variable" then
					if SPECIAL_FUNCTIONS[token] then
						i = "function";
					elseif SPECIAL_VARIABLES[token] then
						i = "number";
						token = SPECIAL_VARIABLES[token];
					end
				end
				table.insert(TokenStream, token);
				table.insert(TokenType, i);
			end
		end
		if len == #expr then
			return false, string.format("Bad token: %s", expr);
		end
	end
	return TokenStream, TokenType;
end


--[[ @brief Returns the priority level of an operator. Unary operators always take precedence over binary operators (except for unary minus).
     @param A token including any binary operator, unary operator ('unary-', functions).
     @return A priority level for this operator where 1 is low priority, 4 is highest.
--]]
function GetPriority(token)
	if token=='+' or token=='-' or token=='unary-' then
		return 1;
	elseif token=='*' or token=="/" or token=='^' then
		return 2;
	elseif token=="^" then
		return 3;
	else
		return 4;
	end
end

--[[ @brief Searches for an operand at a given location. Unary operators are also allowed.
     @param tokens A list of all tokens.
     @param types A list of the token classes.
     @param i The index at which we start searching.
     @return operand: a table which can be injected into the table as the subject of the current operator.
     @return isOperator: whether operand itself is an operator (as is the case for unary operators).
     @return tokensConsumed: how many tokens were read in order to attain this operator.
     @return isFunction: true if operand represents a function which will likely be followed by a parentheses.
     @note When this function fails, it returns false followed by an error message.
--]]
function ParseOperand(tokens, types, i)
	local token, typ = tokens[i], types[i];
	if typ == "operator" and token=='-' or typ == 'function' then
		--We instead got a unary operator. All unary operators take precedence over binary operators.
		local newOperator = {op = (typ=='function' and token or 'unary-')};
		return newOperator, true, 1, typ == 'function';
	elseif typ == "paren" then
		if token == ')' then return false, string.format("Got unexpected close parenthesis token at index %d", i); end
		--It is possible we instead get a parenthesized argument. This is A-OK! Parse it.
		local j = i;
		local openParens = 1;
		--local limit = Utils.WhileLoopLimiter(1000, "parenthesisSearcher");
		while openParens > 0 --[[and limit()]] do
			j = j + 1;
			if types[j] == 'paren' then
				if tokens[j] == '(' then
					openParens = openParens + 1;
				elseif tokens[j] == ')' then
					openParens = openParens - 1;
				else
					return false, string.format("Token of form %s unexpectedly given type 'paren' at index %d", tokens[j], j);
				end
			end
		end
		if j == i+1 then
			return false, string.format("Found parentheses with no inner contents at index %d", i);
		end
		local results = {TreeifyTokens(tokens, types, i + 1, j - 1)};
		if not results[1] then
			--If we have been returned something of the form false, ... we just hit an assertion. Pass it to the calling function.
			return unpack(results);
		else
			--A parenthesized statement may have any number of comma-separated values. These can be interpreted as arguments or a vector based on the parent operation. E.g., in the expression max(1, 2), max will interpret them as arguments. However, in the expression -(1, 2), the unary minus will interpret them as a vector.
			local newOperand = {op = 'identity', unpack(results)};
			return newOperand, false, j - i + 1, false;
		end
	elseif typ == 'comma' then
		return false, string.format("Unexpected comma at token %d", i), 1;
	elseif typ == 'number' then
		return {op = 'identity', [1] = token}, false, 1, false;
	elseif typ == 'variable' then
		return {op = 'variable', [1] = token}, false, 1, false;
	elseif typ == 'operator' then
		return false, string.format("Unexpected binary operator %s at token %d", token, i);
	end
end

--[[ @brief Injects an operation into the tree.
     @param opToken An operator (string) with value +, -, *, /, %, or ^.
     @return newOperation: the newly added operation.
     @return replaceRoot: true if the operation belongs at the root of the expression tree.
--]]
function InjectOperation(opToken, root)
	local newOperation = {op = opToken};
	--If it is equal* or lower priority than the current root, then we become the new root & move root to the left.
	--If it is greater priority than the previous root then we trace down the right side of the tree until we are equal* or lower priority.
	--* equal priority only matters if the operator is left-associative.
	local isLeftAssociative = opToken~='^';
	local tokenPriority = GetPriority(opToken);
	local rootPriority = GetPriority(root.op);
	if (tokenPriority < rootPriority) or (isLeftAssociative and tokenPriority == rootPriority) then
		table.insert(newOperation, root);
		return newOperation, true;
	else
		local seek = root[#root];
		local seekPriority = GetPriority(seek.op);
		local seekParent = root;
		while tokenPriority > seekPriority or (not isLeftAssociative and tokenPriority >= seekPriority) do
			seekParent = seek;
			seek = seek[#seek];
			seekPriority = GetPriority(seek.op);
		end
		table.insert(newOperation, seek);
		for i = 1, #seekParent do
			if seekParent[i] == seek then
				table.remove(seekParent, i);
				break;
			end
		end
		table.insert(seekParent, newOperation);
		return newOperation, false;
	end
end

--[[ @brief Converts a stream of tokens & their type into an expression tree.
     @param tokens A stream of tokens.
     @param types A parallel array of token types.
     @param low The lowest index we should parse from.
     @param high The highest index we should parse to.
     @return Several trees representing each comma-separated expression.
--]]
function TreeifyTokens(tokens, types, low, high)
	local roots = {};
	local function TreeToString(root, depth, s)
		if not root then return; end
		local PrintAtFinish = false;
		if not s then
			PrintAtFinish = true;
			s = {};
			depth = 0;
		end
		if type(root)=='table' then
			table.insert(s, string.rep(".   ", depth) .. root.op .. " (" .. #root .. " operands)")
			for i = 1, #root do
				TreeToString(root[i], depth + 1, s);
			end
		else
			table.insert(s, string.rep(".   ", depth) .. tostring(root));
		end
		if PrintAtFinish then
			return table.concat(s, "\n");
		end
	end
	local operation = nil; --A table which contains operands as its children and the key 'op' indicating how to evaluate it.
	local root = nil;
	local isFunction = false; --A flag set to true if the current operation is a prefix-parenthesized function.
	local i = low;
--	local limit = Utils.WhileLoopLimiter(2000, "treeifyer");
	while i <= high --[[and limit()]] do
		local token, typ = tokens[i], types[i];
		--typ may be 'number', 'operator', 'variable', 'function', or 'paren'. operator means a binary operator except for the case of '-'.
		Debug("%s; token, type: %s, %s", i, token, typ);

		--[[
			Control flow:
				Expecting operand
					--> Parse an operand
				Expecting first operand (root)
					--> Parse an operand
				Expecting binary operator/comma
					Got binary operator
						--> Inject operation into tree & expect succeeding operand.
					Got comma
						--> Add the current expression tree to a list & start a new one.
					Got parentheses, number, or variable:
						--> Inject implicit multiplication. Re-evaluate this token.

			Parse an operand:
				Got unary minus or function
					--> Expect succeeding operand
				Got parentheses
					--> Parse it as the operand.
				Got number
					--> Treat as the operand.
				Got variable
					--> Treat as the operand.
				Got comma
					--> Error!
				Got binary operator
					--> Error!
		--]]

		if operation then
			--In this state, we are waiting for the final operand for either a binary or unary operation.
			local newOp, isOperation, consumedTokens, isFunc = ParseOperand(tokens, types, i);
			Debug("ParseOperand(tokens, types, %s) = %s, %s, %s, %s", i, newOp, isOperation, consumedTokens, isFunc);
			--> We may have encountered an error. Pass it upward.
			if not newOp then
				return newOp, isOperation;
			end
			i = i + consumedTokens -1;
			if isFunction and newOp.op == 'identity' then
				--If the operation is a prefix-parenthesized function (e.g., max(x, y) ), we should unpack newOp if it takes the form of 'identity'.
				for i, v in ipairs(newOp) do
					table.insert(operation, v);
				end
			else
				table.insert(operation, newOp);
			end
			if isOperation then
				operation = newOp;
			else
				operation = nil;
			end
			isFunction = isFunc;
		elseif root==nil then
			--In this state, we are waiting for the first operand.
			local newOp, isOperation, consumedTokens, isFunc = ParseOperand(tokens, types, i);
			--> We may have encountered an error. Pass it upward.
			if not newOp then
				return newOp, isOperation;
			end
			i = i + consumedTokens - 1;
			root = newOp;
			if isOperation then
				operation = newOp;
			else
				operation = nil;
			end
			isFunction = isFunc;
		else
			--When operation is nil, we are expecting a binary operator.
			if typ=='operator' then
				local newOperation, isRoot = InjectOperation(token, root);
				operation = newOperation;
				if isRoot then
					root = newOperation;
				end
			elseif typ=='comma' then
				Debug("Got comma. Previous tree:\n===================\n%s\n===================", TreeToString(root));
				table.insert(roots, root);
				root = nil;
				operation = nil;
			else
				Debug("Got %s ('%s') when expected binary operator", typ, token);
				--Jamming several numbers/function calls/variables together should be interpreted as a string of multiplications.
				--E.g., 5x cos x ==> 5 * x * cos(x)
				local newOperation, isRoot = InjectOperation("*", root);
				operation = newOperation;
				if isRoot then
					root = newOperation;
				end
				--We wish to reinterpret this token.
				i = i - 1;
			end
		end
		i = i + 1;
	end
	Debug("Complete Tree:\n===================\n%s\n===================", TreeToString(root));
	table.insert(roots, root);
	return unpack(roots);
end


--[[ @brief Returns the numerical value of an expession tree.
     @param tree The expression tree obtained from TreeifyTokens
     @param variables A map indicating the numerical values of several variables.
     @return The value of the tree.
--]]
function EvaluateTree(tree, variables)
	if type(tree)=='number' then
		return tree;
	end
	if tree.op == 'identity' then
		return EvaluateTree(tree[1], variables);
	elseif tree.op == "+" then
		return EvaluateTree(tree[1], variables) + EvaluateTree(tree[2], variables);
	elseif tree.op == "-" then
		return EvaluateTree(tree[1], variables) - EvaluateTree(tree[2], variables);
	elseif tree.op == "*" then
		return EvaluateTree(tree[1], variables) * EvaluateTree(tree[2], variables);
	elseif tree.op == "/" then
		return EvaluateTree(tree[1], variables) / EvaluateTree(tree[2], variables);
	elseif tree.op == "%" then
		return EvaluateTree(tree[1], variables) % EvaluateTree(tree[2], variables);
	elseif tree.op == "^" then
		return EvaluateTree(tree[1], variables) ^ EvaluateTree(tree[2], variables);
	elseif tree.op == "unary-" then
		return -EvaluateTree(tree[1], variables);
	elseif tree.op == 'cos' then
		return math.cos(EvaluateTree(tree[1], variables));
	elseif tree.op == 'sin' then
		return math.sin(EvaluateTree(tree[1], variables));
	elseif tree.op == 'tan' then
		return math.tan(EvaluateTree(tree[1], variables));
	elseif tree.op == 'acos' then
		return math.acos(EvaluateTree(tree[1], variables));
	elseif tree.op == 'asin' then
		return math.asin(EvaluateTree(tree[1], variables));
	elseif tree.op == 'atan' then
		return math.atan(EvaluateTree(tree[1], variables));
	elseif tree.op == 'atan2' then
		return math.atan2(EvaluateTree(tree[1], variables), EvaluateTree(tree[2], variables));
	elseif tree.op == 'log2' then
		return math.log(EvaluateTree(tree[1], variables)) / math.log(2);
	elseif tree.op == 'log10' then
		return math.log10(EvaluateTree(tree[1], variables));
	elseif tree.op == 'ln' then
		return math.log(EvaluateTree(tree[1], variables));
	elseif tree.op == 'exp' then
		return math.exp(EvaluateTree(tree[1], variables));
	elseif type(tree.op)=='number' then
		return tree.op;
	elseif tree.op=='variable' then
		Debug("Looking up variable: %s", tree[1]);
		return variables[tree[1]];
	else
		assert(false, string.format("Unknown operation: %s", tree.op));
	end
end


--[[ @brief Interprets & returns the value(s) of an expression.
     @param expr The expression to compute.
     @param variables Variable substitutions to make in dictionary form.
     @return Several values indicating the numerical values of each comma-separated expression.
--]]
function InterpretExpression(expr, variables)
	local TokenStream, TokenType = Tokenize(expr);
	if not TokenStream then
		return false, TokenType;
	end

	Debug("Token Stream: ");
	for i, v in pairs(TokenStream) do
		Debug("%s", v);
	end

	--When this is done, create a tree.
	local trees = {TreeifyTokens(TokenStream, TokenType, 1, #TokenStream)};
	if not trees[1] then
		return false, trees[2];
	end
	if #trees==1 then
		return EvaluateTree(trees[1], variables);
	else
		local values = {};
		for i = 1, #trees do
			values[i] = EvaluateTree(trees[i], variables);
		end
		return unpack(values);
	end
end

return {Parse = InterpretExpression};

#4

I’ll document it when I get off work later.


#5

I’ve added documentation.

Sorry it took so long, I completely forgot about this thread last night!

Also, please note I am AWFUL at documentation so GOOD LUCK.


#6

Wait a gosh darn minute, that was this morning!
>.<


#7

If anyone actually uses this, I’ve just updated the OP with a few bug fixes and optimisations. Also the example screenshots appear to have broken and I don’t remember what they were so I’ve just added some basic examples.


#8

You should have made it a module and put it in the library for people to use.


#9

I’ve made it a module now. Honestly not sure why I didn’t originally.


#10

Good thing about using modules is that you’re the source code holder, also it’s easier for people to use & access.


#11

Just updated the module with a complete rewrite. The new system has the same features as before and is ran the exact same way however has a couple benefits:

  1. No more number to string inaccuracies as everything calculated is stored in a table as a number, instead of being appended to the string. ( means “(1/3)*3” will now equal 1 instead of 0.9999 )
  2. You can now use numbers in the names of variables / functions ( e.g. “a1=5!; a1+2” = 122 )
  3. Having a number directly in front of a bracket now acts as multiplication instead of requiring a “*” ( e.g. “(1+1)(3+3)” = 12 )

and the best part, it’s up to 2x faster