tree.lua
· 2.3 KiB · Lua
原始檔案
Playground
local function table_stream(t)
return coroutine.wrap(function()
for _, v in ipairs(t) do
coroutine.yield(v)
end
end)
end
local function push(t, v)
table.insert(t, v)
end
local function show_tree(tree)
local buffer = {}
for node in table_stream(tree) do
if type(node) == "table" then
local subtree = ("(%s)"):format(show_tree(node))
push(buffer, subtree)
else
push(buffer, tostring(node))
end
end
return table.concat(buffer, " ")
end
local function build_symbol(bits)
local symbol = table.concat(bits)
if tonumber(symbol) then return tonumber(symbol)
elseif symbol == "true" then return true
elseif symbol == "false" then return false
else return symbol
end
end
local function build_tree(stream)
local tree = {}
local symbol = {}
for char in stream do
if char == "(" then
push(tree, build_tree(stream))
elseif char == ")" then
break
elseif char == " " and #symbol ~= 0 then
push(tree, build_symbol(symbol))
symbol = {}
elseif char:match("%s") then
-- no op
else
push(symbol, char)
end
end
if #symbol ~= 0 then
push(tree, build_symbol(symbol))
end
return tree
end
local function parse(string)
return build_tree(string:gmatch("."))
end
local function reduce(tree)
if type(tree) ~= "table" then
return tree
end
local index = 1
local target = nil
local node_stream = coroutine.wrap(function()
for _, node in ipairs(tree) do
coroutine.yield(node)
end
end)
for node in node_stream do
if not target then
target = reduce(node)
elseif type(target) == "number" then
local next = reduce(node_stream())
if node == "+" then
target = target + next
elseif node == "-" then
target = target - next
elseif node == "*" then
target = target * next
elseif node == "/" then
target = target / next
else
error("Object does not respond to " .. node)
end
end
end
return target
end
print(show_tree(parse(arg[1])))
print(reduce(parse(arg[1])))
| 1 | local function table_stream(t) |
| 2 | return coroutine.wrap(function() |
| 3 | for _, v in ipairs(t) do |
| 4 | coroutine.yield(v) |
| 5 | end |
| 6 | end) |
| 7 | end |
| 8 | |
| 9 | local function push(t, v) |
| 10 | table.insert(t, v) |
| 11 | end |
| 12 | |
| 13 | local function show_tree(tree) |
| 14 | local buffer = {} |
| 15 | for node in table_stream(tree) do |
| 16 | if type(node) == "table" then |
| 17 | local subtree = ("(%s)"):format(show_tree(node)) |
| 18 | push(buffer, subtree) |
| 19 | else |
| 20 | push(buffer, tostring(node)) |
| 21 | end |
| 22 | end |
| 23 | return table.concat(buffer, " ") |
| 24 | end |
| 25 | |
| 26 | |
| 27 | local function build_symbol(bits) |
| 28 | local symbol = table.concat(bits) |
| 29 | if tonumber(symbol) then return tonumber(symbol) |
| 30 | elseif symbol == "true" then return true |
| 31 | elseif symbol == "false" then return false |
| 32 | else return symbol |
| 33 | end |
| 34 | end |
| 35 | |
| 36 | local function build_tree(stream) |
| 37 | local tree = {} |
| 38 | local symbol = {} |
| 39 | for char in stream do |
| 40 | if char == "(" then |
| 41 | push(tree, build_tree(stream)) |
| 42 | elseif char == ")" then |
| 43 | break |
| 44 | elseif char == " " and #symbol ~= 0 then |
| 45 | push(tree, build_symbol(symbol)) |
| 46 | symbol = {} |
| 47 | elseif char:match("%s") then |
| 48 | -- no op |
| 49 | else |
| 50 | push(symbol, char) |
| 51 | end |
| 52 | end |
| 53 | |
| 54 | if #symbol ~= 0 then |
| 55 | push(tree, build_symbol(symbol)) |
| 56 | end |
| 57 | |
| 58 | return tree |
| 59 | end |
| 60 | |
| 61 | local function parse(string) |
| 62 | return build_tree(string:gmatch(".")) |
| 63 | end |
| 64 | |
| 65 | local function reduce(tree) |
| 66 | if type(tree) ~= "table" then |
| 67 | return tree |
| 68 | end |
| 69 | |
| 70 | local index = 1 |
| 71 | local target = nil |
| 72 | local node_stream = coroutine.wrap(function() |
| 73 | for _, node in ipairs(tree) do |
| 74 | coroutine.yield(node) |
| 75 | end |
| 76 | end) |
| 77 | |
| 78 | for node in node_stream do |
| 79 | if not target then |
| 80 | target = reduce(node) |
| 81 | elseif type(target) == "number" then |
| 82 | local next = reduce(node_stream()) |
| 83 | if node == "+" then |
| 84 | target = target + next |
| 85 | elseif node == "-" then |
| 86 | target = target - next |
| 87 | elseif node == "*" then |
| 88 | target = target * next |
| 89 | elseif node == "/" then |
| 90 | target = target / next |
| 91 | else |
| 92 | error("Object does not respond to " .. node) |
| 93 | end |
| 94 | end |
| 95 | end |
| 96 | return target |
| 97 | end |
| 98 | |
| 99 | print(show_tree(parse(arg[1]))) |
| 100 | print(reduce(parse(arg[1]))) |
| 101 |