 # More efficient way to implement Shunting-Yard?

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 ~= '(' do
local operator1Precedence = OPERATOR_PRECEDENCE[operator]
local operator2Precedence = OPERATOR_PRECEDENCE[operatorStack]

if operator2Precedence and ((operator2Precedence > operator1Precedence) or (operator2Precedence == operator1Precedence and operator1Precedence)) 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 ~= '(' do
assert(#operatorStack > 0)
table.insert(outputStack, table.remove(operatorStack, 1))
end

assert(operatorStack == '(')
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 ~= '(')
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

5 Likes