支架尋找算法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 

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