Operator Precedence Climbing

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()