More efficient way to implement Shunting-Yard?

Help and Feedback Code Review
#1

On a thread in scripting helpers someone posted this link to the shunting-yard algorithm: Shunting yard algorithm - Wikipedia

I thought it’d be a fun exercise to implement in Lua so I took a crack at it. I only got around to making a basic implementation, i.e. does not support special numbers and function calls. I had planned to but then lost steam by the time I got a basic implementation working.

My *basic* implementation 
local OPERATOR_PRECEDENCE = {
    -- [operator] = { [precedence], [is left assoc.] }
    ['-'] = { 2, true };
    ['+'] = { 2, true };
    ['/'] = { 3, true };
    ['*'] = { 3, true };
    ['^'] = { 4, false };   
}

local function shuntingYard(expression)
    local outputStack = { }
    local operatorStack = { }
    
    local number, operator, parenthesis, fcall

    while #expression > 0 do
        local nStartPos, nEndPos = string.find(expression, '(%d+%.?%d*)')
        
        if nStartPos == 1 and nEndPos > 0 then
            number, expression = string.sub(expression, nStartPos, nEndPos), string.sub(expression, nEndPos + 1)
            table.insert(outputStack, tonumber(number))
        else
            local oStartPos, oEndPos = string.find(expression, '([%-%+%*/%^])')
            
            if oStartPos == 1 and oEndPos > 0 then
                operator, expression = string.sub(expression, oStartPos, oEndPos), string.sub(expression, oEndPos + 1)
                
                if #operatorStack > 0 then
                    while operatorStack[1] ~= '(' do
                        local operator1Precedence = OPERATOR_PRECEDENCE[operator]
                        local operator2Precedence = OPERATOR_PRECEDENCE[operatorStack[1]]
                    
                        if operator2Precedence and ((operator2Precedence[1] > operator1Precedence[1]) or (operator2Precedence[1] == operator1Precedence[1] and operator1Precedence[2])) then
                            table.insert(outputStack, table.remove(operatorStack, 1))
                        else
                           break 
                        end
                    end
                end
                
                table.insert(operatorStack, 1, operator)
            else
                local pStartPos, pEndPos = string.find(expression, '[%(%)]')
                
                if pStartPos == 1 and pEndPos > 0 then
                    parenthesis, expression = string.sub(expression, pStartPos, pEndPos), string.sub(expression, pEndPos + 1)
                    
                    if parenthesis == ')' then
                        while operatorStack[1] ~= '(' do
                            assert(#operatorStack > 0)
                            table.insert(outputStack, table.remove(operatorStack, 1))
                        end
                        
                        assert(operatorStack[1] == '(')
                        table.remove(operatorStack, 1)
                    else
                        table.insert(operatorStack, 1, parenthesis)
                    end
                else
                    local wStartPos, wEndPos = string.find(expression, '%s+')
                    
                    if wStartPos == 1 and wEndPos > 0 then
                        expression = string.sub(expression, wEndPos + 1)
                    else
                        error('Invalid character set: '.. expression)
                    end
                end
            end
        end
    end
    
    while #operatorStack > 0 do
        assert(operatorStack[1] ~= '(')
        table.insert(outputStack, table.remove(operatorStack, 1))
    end
    
    return table.concat(outputStack, ' ')
end


local goodmath = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'

print('shunting yard:', shuntingYard(goodmath)) --> output: 3 4 2 * 1 5 - 2 3 ^ ^ / +

I’m sure there’s a more efficient way to implement it in Lua/Luau though, and I’d love for someone to show me up here (as I was not a Comp Sci major). Let me know your thoughts!

Edit:
I’ve posted my snippet to Rosetta Code upon finding out it (Shunting-Yard) has not yet been implemented in Lua there. You can view my page edit here:
https://rosettacode.org/mw/index.php?title=Parsing/Shunting-yard_algorithm&diff=337227&oldid=326760

4 Likes