algorithm - 括号查找算法lua？

Question

我正在制作一个 JSON 解析器，我正在寻找一种可以找到所有匹配括号 ([]) 和大括号 ({}) 的算法，并且将它们放入一个表中，其中包含该对的位置。

返回值示例:

table[x][firstPos][secondPos] = type

table[x] = {firstPos, secondPos, bracketType}

编辑:让 parse() 成为返回括号对的函数。设 table 为 parse() 函数返回的值。让 codeString 成为包含我要检测的括号的字符串。设 firstPos 为第一个括号在第 N 对括号中的位置。设 secondPos 为第 N 对括号中第二个括号的位置。设 bracketType 为括号对的类型(“bracket”或“brace”)。

例子:

如果你打电话:

table = parse(codeString)

table[N][firstPos][secondPos] 将等于 type。

Answer 1

嗯，在普通的 Lua 中，你可以做这样的事情，同时考虑嵌套括号:

function bm(s)
    local res ={}
    if not s:match('%[') then
            return s
    end
    for k in s:gmatch('%b[]') do
            res[#res+1] = bm(k:sub(2,-2))
    end
    return res
end

当然，您可以很容易地将其概括为大括号、圆括号等(请记住 patterns 中 [] 的必要转义，%b 模式后面除外)。

如果您不局限于普通的 Lua，您可以使用 LPeg 以获得更大的灵 active

如果您不是在寻找方括号的内容，而是在寻找位置，则递归方法更难实现，因为您应该跟踪自己的位置。更简单的是遍历字符串并在进行时匹配它们:

function bm(s,i)
    local res={}
    res.par=res      -- Root
    local lev = 0
    for loc=1,#s do
        if s:sub(loc,loc) == '[' then
            lev = lev+1
            local t={par=res,start=loc,lev=lev}   -- keep track of the parent
            res[#res+1] = t                       -- Add to the parent
            res = t                               -- make this the current working table
            print('[',lev,loc)
        elseif s:sub(loc,loc) == ']' then
            lev = lev-1
            if lev<0 then error('too many ]') end -- more closing than opening.
            print(']',lev,loc)                  
            res.stop=loc                          -- save bracket closing position
            res = res.par                         -- revert to the parent.
        end
    end
    return res
end

现在您已经有了所有匹配的括号，您可以遍历表格，提取所有位置。