Creating a Math Evaluator (Interpreter)

Resources Community Tutorials
#1

Introduction

Parser

In the last tutorial we created a parser to convert our tokens from infix to postfix notation. Next we’ll use this notation to evaluate our expressions.

What is an interpreter?

An interpreter executes instructions. Since we’re evaluating math expressions our interpreter is a bit different than that you might see for programming languages or other use cases.

How do you evaluate postfix notation?

This is actually far simpler than you might think. Let’s say we have the following postfix and want to evaluate it: 9 4 +. To do so we read from left to right. We keep reading until we reach an operator. Once we reach an operator (in this case +) we evaluate the last two operands (9 and 4) using that operator. That then results in 13. All we have to do then is write this in code and it’s actually really simple.

Building the Interpreter

Unlike the parser and lexer we won’t apply OOP principles here. We’ll simply have an evaluate function. We’ll also be utilizing the stack module we made in the last tutorial. So let’s write this thing out!

function Interpreter.evaluate(postfix)
	local stack = Stack.new() -- This stack will hold our evaluated numbers

	for index, token in ipairs(postfix:get()) do
		if (typeof(token) == 'number') then
			stack:push(token)
		else
			local val1, val2 = stack:pop(), stack:pop() -- Grab the last two operands

			if (token[1] == 'PLUS') then
				stack:push(val1 + val2) -- Add then push onto stack
			elseif (token[1] == 'MINUS') then
				stack:push(val2 - val1) -- Subtract then push onto stack
			elseif (token[1] == 'ASTERIK') then
				stack:push(val1 * val2) -- Multiply then push onto stack
			elseif (token[1] == 'SLASH') then
				stack:push(val2 / val1) -- Divide then push onto stack
			else
				error('Unknown token')
			end
		end
	end

	return tonumber(stack:top()) -- Return the final evaluated number
end

That’s all the code! Notice how when subtracting and dividing we do val2 - val1 and val2 / val1 rather than the other way around. This is because when we actually grab the values we’re popping them from the stack. Rember that popping takes one at a time from the top so we’re grabbing the values in the opposite order. For division and subtraction where the operands are relative to the operator matters so we have to reverse the values.

Testing

Our final code for testing will be:

local lexer = Lexer.new('5 * 2 - (1 + 6)')
lexer:tokenize()

local postfix = Parser.new(lexer):parse()
local result = Interpreter.evaluate(postfix)

print(result)

When we run this you should see:

image

We just made a fully functioning math evaluator! Pretty cool, right?

Conclusion

I really enjoyed making this series and hope I contributed something useful and informative to the community. If you’re interested in seeing an example with more operators and even functions check out my MathEvaluator module. Thanks for reading!

If you want the .rbxm file for everything covered in this tutorial it’s available here: MathEval.rbxm (5.3 KB)

11 Likes
#2

So I made a simple math evaluator in class today inspired from your work, it’s like 90 lines of code and can only do addition and subtraction. You can only input single digit unsigned integers because of time limitations. One cool feature I added was whitespaces, you could have a million tabs, or spaces, or new lines in between each character, and it will ignore them. Here is the code:

local MathEval = {}

Whitespaces = {" ", "\n", "\t"}
Digits = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
Operators = {"+", "-"}

local function find(tab, val)
    for index, value in ipairs(tab) do
        if value == val then
            return true
        end
    end

    return false
end

local function IsWhiteSpace(Input)
    return Input == Whitespaces[1] or Input == Whitespaces[2] or Input == Whitespaces[3] 
end

local function IsOperator(Input)
    return Input == Operators[1] or Input == Operators[2]
end

local function IsDigit(Input)
    for c in Input:gmatch"." do
        if not find(Digits, c) then break end
    end

    return find(Digits, true)
end

local function GetOperator(Input)
    for index, value in ipairs(Operators) do
        if value == Input then
            return value
        end
    end

    return nil
end

function MathEval.Evaluate(Input)
    local RevisedInput = {}
    local LocalOperators = {}
    local LocalDigits = {}

    for c in Input:gmatch"." do
        if not IsWhiteSpace(c) then
            RevisedInput[#RevisedInput + 1] = c
        end

    end

    for _, v in pairs(RevisedInput) do
        if IsOperator(v) then
            LocalOperators[#LocalOperators + 1] = v
        elseif IsDigit(v) then
            LocalDigits[#LocalDigits + 1] = v
        end
    end

    return RevisedInput
end

function MathEval.Calculate(Input)
    local x = 0

    for index, value in pairs(Input) do
        if IsOperator(value) then
            if GetOperator(value) == "+" then
                if x ~= 0 then
                    x = x + Input[index + 1]
                else 
                    x = x + Input[index - 1] + Input[index + 1]
                end
            elseif GetOperator(value) == "-" then
                if x ~= 0 then
                    x = x - Input[index + 1]
                else 
                    x = x + Input[index - 1] - Input[index + 1]
                end
            end
        end

        -- if IsOperator(value) then
            
        -- end
    end

    return x
end

-- local e = Evaluate("1 + 1 + 9 - 8")
-- print(Calculate(e))

return MathEval

There’s a bit of commented code for no real reason.

example of using the script:

local mathEval = require(game.ReplicatedStorage.MathEval)

local expression = mathEval.Evaluate("1 + 9 - 2 + 1")
print(mathEval.Calculate(expression))

Yes I made this in VSCODE with Lua 5.4.3, so some of the code might not work, I never tested that. Another thing I would’ve implemented was using LuaU type checking for the parameters since it just looks way nicer.

EDIT: I am currently making the script accept two digits numbers, the main issue is that the evaluate function splits two digit numbers into two parts, so 11 would turn into 1 1, which isn’t good at all if I am try to make it accept multidigit numbers.

EDIT: I did it…

local MathEval = {}

Whitespaces = {" ", "\n", "\t"}
Digits = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
Operators = {"+", "-"}

local function find(tab, val)
	for index, value in ipairs(tab) do
		if value == val then
			return true
		end
	end

	return false
end

local function IsWhiteSpace(Input)
	return Input == Whitespaces[1] or Input == Whitespaces[2] or Input == Whitespaces[3] 
end

local function IsOperator(Input)
	return Input == Operators[1] or Input == Operators[2]
end

local function IsDigit(Input)
	for c in Input:gmatch"." do
		if not find(Digits, c) then
			return false
		else 
			return true
		end
	end

	return false
end

local function GetOperator(Input)
	for index, value in ipairs(Operators) do
		if value == Input then
			return value
		end
	end

	return nil
end

function MathEval.Evaluate(Input)
	local RevisedInput = {}
	local LocalOperators = {}
	local LocalDigits = {}
	
	local p = "[^"..table.concat(Whitespaces).."]+"
	
	for w in Input:gmatch(p) do
		RevisedInput[#RevisedInput + 1] = w
	end

	for _, v in pairs(RevisedInput) do
		if IsOperator(v) then
			LocalOperators[#LocalOperators + 1] = v
		elseif IsDigit(v) then
			LocalDigits[#LocalDigits + 1] = v
		end
	end

	return RevisedInput
end

function MathEval.Calculate(Input)
	local x = 0

	for index, value in pairs(Input) do
		if IsOperator(value) then
			if GetOperator(value) == "+" then
				if x ~= 0 then
					x = x + Input[index + 1]
				else 
					x = x + Input[index - 1] + Input[index + 1]
				end
			elseif GetOperator(value) == "-" then
				if x ~= 0 then
					x = x - Input[index + 1]
				else 
					x = x + Input[index - 1] - Input[index + 1]
				end
			end
		end
	end

	return x
end

return MathEval

I created this useless function that took of bit of time to get working, but I found this StackOverflow topic that basically solves my issue, so that’s cool!

EDIT: So I rewrote it in C# just for the fun of it, and I realized that both the C# version and the Lua version have a very critical issue. If there is no whitespace in the starting input, it will always output 0, which is pretty bad. The reason is because I’m splitting the string by each whitespace, but if there is no whitespace, it will just return the entire string, which is pretty bad.

C# code for the splitter:

// Whitespace array:

public static string[] Whitespaces = new string[] { " ", "\n", "\t" };
public static string[] Digits = new string[] { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
public static string[] Operators = new string[] { "+" };

// Evaluate method:

public static string[] Evaluate(string Input) => Input.Split(Whitespaces, StringSplitOptions.RemoveEmptyEntries);

// Calculate method:

public static float Calculate(string[] Input) {
	var x = 0f;
	var index = 0;

	foreach (string v in Input) {
		if (IsOperator(v)) {
			if (v == "+") {
				if (x != 0f) {
					x += float.Parse(Input[index - 1]);
				}
				else {
					x = float.Parse(Input[index - 1]) + float.Parse(Input[index + 1]);
				}
			}
		}

		index++;
	}

	return x;
}

// There are only small portions of the code I made.

Edit 2:

I am now working on my own simple programming language in C#, I am using your topics as references for parsers and lexers, which is where I am at in my language. I am not sure what to call it, but I’ll figure something out eventually.

Edit 3:

I just finished the basics of the lexer for my language! Since I’m using a more advanced language than Lua this time, I can use enums for each token type!

		public enum TokenTypes {
			Keyword,
			Identifier,
			String,
			Int,
			Bool,
			Operator,
			Params,
			Punctuator,
			Undefined,
			LexGarbage,
			EOF
		}
2 Likes