支架寻找算法lua？

Question

我正在制作一个JSON解析器，我正在寻找一种算法，它可以找到所有匹配的括号（[]）和大括号（{}），并将它们放到一个表中，并且将它们放在一个表中。返回的值

实例：

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

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

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

例子：

如果你叫：

table = parse(codeString) 

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

Answer 1

我想出了我自己的算法。

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 

Answer 2

那么，在普通的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 

现在你有所有匹配的支架，可以遍历表，提取的所有位置。