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