Results 1 to 1 of 1

Thread: [LUA] Shunting Yard Algorithm

  1. #1

    Thread Starter
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    11,495

    [LUA] Shunting Yard Algorithm

    The following code represents how to implement the shunting yard algorithm in LUA:
    Code:
    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:
    Code:
    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.
    Last edited by dday9; Aug 11th, 2023 at 10:43 AM.
    "Code is like humor. When you have to explain it, itís bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width