3

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

返回值示例：

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

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

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

例子：

如果您致电：

table = parse(codeString)

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

4

2 回答 2

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

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

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

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

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

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

于 2013-10-15T11:23:53.803 回答
0

我想出了自己的算法。

function string:findAll(query)
    local firstSub = 1
    local lastSub = #query
    local result = {}
    while lastSub <= #self do
        if self:sub(firstSub, lastSub) == query then
            result[#result + 1] = firstSub
        end
        firstSub = firstSub + 1
        lastSub = lastSub + 1
    end
    return result
end

function string:findPair(openPos, openChar, closeChar)
    local counter = 1
    local closePos = openPos
    while closePos <= #self do
        closePos = closePos + 1
        if self:sub(closePos, closePos) == openChar then
            counter = counter + 1
        elseif self:sub(closePos, closePos) == closeChar then
            counter = counter - 1
        end
        if counter == 0 then
            return closePos
        end
    end
    return -1
end

function string:findBrackets(bracketType)
    local openBracket = ""
    local closeBracket = ""
    local openBrackets = {}
    local result = {}
    if bracketType == "[]" then
        openBracket = "["
        closeBracket = "]"
    elseif bracketType == "{}" then
        openBracket = "{"
        closeBracket = "}"
    elseif bracketType == "()" then
        openBracket = "("
        closeBracket = ")"
    elseif bracketType == "<>" then
        openBracket = "<"
        closeBracket = ">"
    else
        error("IllegalArgumentException: Invalid or unrecognized bracket type "..bracketType.."\nFunction: findBrackets()")
    end
    local openBrackets = self:findAll(openBracket)
    if not openBrackets[1] then
        return {}
    end
    for i, j in pairs(openBrackets) do
        result[#result + 1] = {j, self:findPair(j, openBracket, closeBracket)}
    end
    return result
end

将输出：

5   14
6   13
7   12
8   11
9   10
于 2013-11-04T00:38:20.920 回答