# Thread: [LUA] Shunting Yard Algorithm

1. ## [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.

#### Posting Permissions

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