[LUA] Shunting Yard Algorithm

[dday9]

The following code represents how to implement the shunting yard algorithm in LUA:

local function isWhitespace(char)
    local whitespaceAscii = {
        [32] = true, -- space
        [9] = true,  -- tab
        [10] = true, -- newline (LF)
        [13] = true, -- carriage return (CR)
    }
    local charAscii = char:byte()
    return whitespaceAscii[charAscii]
end

local function isOperator(char)
    local operators = {"+", "-", "*", "/", "^"}
    for i = 1, #operators do
        if operators[i] == char then
            return true
        end
    end
    return false
end

local function getPrecedence(operator)
    if operator == "+" or operator == "-" then
        return 1
    elseif operator == "*" or operator == "/" then
        return 2
    elseif operator == "^" then
        return 3
    end
    return 0
end

local function shuntingYardAlgorithm(expression)
    local outputQueue = {}
    local operatorStack = {}

    local i = 1
    while i <= #expression do
        local token = expression:sub(i, i)
        if (isWhitespace(token)) then
            goto continue
        elseif (token == "+" or token == "-") and (i == 1 or isOperator(expression:sub(i - 1, i - 1)) or expression:sub(i - 1, i - 1) == "(") then
            local number = token
            i = i + 1
            while i <= #expression and (tonumber(expression:sub(i, i)) or expression:sub(i, i) == ".") do
                token = expression:sub(i, i)
                number = number .. token
                i = i + 1
            end
            i = i - 1
            table.insert(outputQueue, number)
        elseif tonumber(token) or token == "." then
            local number = ""
            while i <= #expression and (tonumber(expression:sub(i, i)) or expression:sub(i, i) == ".") do
                token = expression:sub(i, i)
                number = number .. token
                i = i + 1
            end
            i = i - 1
            table.insert(outputQueue, number)
        elseif isOperator(token) then
            while #operatorStack > 0 and isOperator(operatorStack[#operatorStack]) and
                  getPrecedence(token) <= getPrecedence(operatorStack[#operatorStack]) do
                table.insert(outputQueue, table.remove(operatorStack))
            end
            table.insert(operatorStack, token)
        elseif token == "(" then
            table.insert(operatorStack, token)
        elseif token == ")" then
            while #operatorStack > 0 and operatorStack[#operatorStack] ~= "(" do
                table.insert(outputQueue, table.remove(operatorStack))
            end
            if operatorStack[#operatorStack] == "(" then
                table.remove(operatorStack)
            end
        end
        ::continue::
        i = i + 1
    end

    while #operatorStack > 0 do
        table.insert(outputQueue, table.remove(operatorStack))
    end

    return outputQueue
end

The idea behind the shunting-yard algorithm is that it takes expressions using infix notation (i.e. how we were taught to write mathematical expressions) to postfix notation (i.e. a grammar that is more efficient but harder for humans to read).

Here is an example of using it:

local expressions = {
    "1 + 2",
    "(3 + 4) / 5",
    "6.025 * (7 - 8)",
    "(-10 + 2) * (7 - 3) / 2 ^ 4"
}
for i = 1, #expressions do
    local expression = expressions[i]
    local output = shuntingYardAlgorithm(expression)
    print("Infix:", expression)
    print("Postfix:", table.concat(output, " "))
    print("")
end

Github Repository: https://github.com/dday9/lua-shunting-yard-algorithm

Change Log
2023-08-11: Added greater support for parsing numbers, i.e. support for optional unary operator and decimals.