Operator Precedence Climbing
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
local opTable = {
["*"] = 2,
["+"] = 4,
}
function main()
--local a = lex("(4 + 9) * 2") -- failing
--local aP = parse(a)
--printParse(aP, "")
local b = lex("1 + 2 * (3 + 4 * 5 * 6) * 7")
local bP = parse(b)
printParse(bP, "")
end
function lex(c)
local result = {}
local i = 1
while string.sub(c, i, i + 1) ~= "" do
local chr = string.sub(c, i, i);
if chr == "*" then
table.insert(result, { t = "o", v = "*" })
elseif chr == "+" then
table.insert(result, { t = "o", v = "+" })
elseif chr == "(" then
table.insert(result, { t = "o", v = "(" })
elseif chr == ")" then
table.insert(result, { t = "o", v = ")" })
elseif chr == " " then
else
local v = string.byte(chr) - string.byte("0")
table.insert(result, { t = "n", v = v })
end
i = i + 1
end
return result
end
function parse(c)
local par = { c = c, i = 1 }
local l = pop(par)
return parseR(l, par, 2000)
end
function parseR(l, par, pre)
while true do
local op = peek(par)
if op == nil then
return l
elseif op.v == ")" then
consume(par)
return l, ")"
elseif opTable[op.v] >= pre then
return l
end
consume(par)
local r = pop(par)
local res
local closingInput
if r.v == "(" then
local nr = pop(par)
local currRes, currentlyClosingBracket = parseR(nr, par, 2000)
--print(currRes.op)
assert(currentlyClosingBracket == ")")
res = { op = "()", l = currRes }
else
res, closingInput = parseR(r, par, opTable[op.v])
end
l = { op = op.v, l = l, r = res}
if closingInput then
return l, closingInput
end
end
end
function peek(par)
return par.c[par.i]
end
function pop(par)
local v = par.c[par.i]
par.i = par.i + 1
return v
end
function consume(par)
par.i = par.i + 1
end
function printParse(t, indent)
if t.op ~= nil then
print(#indent.." "..indent.." "..t.op)
if t.op == "()" then
printParse(t.l, indent.." ")
else
printParse(t.l, indent.." ")
printParse(t.r, indent.." ")
end
else
print(#indent.." "..indent.." "..t.v)
end
end
main()
Lua
INFO