JS括號匹配問題

lordharrd 發布于2019-08-20 11:38 / 1065人閱讀

摘要：在上做了一道括號匹配的題目。題目判斷字符串中的三種括號是否匹配，需要考慮嵌套的情況。是，則表示完全匹配，否則，比匹配。

在codewars上做了一道括號匹配的題目。

題目

判斷字符串中的{}、[]、()三種括號是否匹配，需要考慮嵌套的情況。

例子：

validBraces("(){}[]")     // true 
validBraces("(}")         // false 
validBraces("[(])")       // false 
validBraces("([{}])")     // true

Solution

這個問題的最根本只有兩種情況，一種是并列的，即沒有嵌套的情況，如()[]{};另一種情況就是嵌套的情況，如{[()]}。第一種情況是比較簡單的，有難度的是第二種情況。存在嵌套的情況的解決方法，是首先匹配最里面的括號對，即我們常說的從內部開始瓦解。

第一種方法：

function validBraces(braces){
  while(/()|[]|{}/g.test(braces)){
    braces = braces.replace(/()|[]|{}/g,"")
  }
  return !braces.length;
}

這種方法，查找成對的括號，然后將成對相鄰的括號替換成空字符串，也就是說刪除。最后判斷字符串的長度是否為0。是，則表示完全匹配，否則，比匹配。
其實，這種方案就是典型的“從內部開始瓦解”。我們以{[()]}為例，你觀察一下，現在只有最里面的()才是成對且相鄰的，當把()替換成空字符串之后，[]變成了成對且相鄰的，然后再將其替換成空字符串。就這樣一直循環地查找，直到再也找不到成對且相鄰的括號為止。

第二種方法：

function validBraces(braces){
  let leftBraReg = /[({[]/, 
    // 棧
      stack = [],
      bracket, rightBracket
  braces = braces.split("")
  for(bracket of braces) {
    if(leftBraReg.test(bracket)) {
      stack.push(bracket)
    }
    else {
      switch (bracket) {
          case ")":
          rightBracket = stack.pop()
          if(rightBracket !=="(") {
              return false
          }
          break
        case "]":
          rightBracket = stack.pop()
          if(rightBracket !=="[") {
              return false
          }
          break
        case "}":
          rightBracket = stack.pop()
          if(rightBracket !=="{") {
              return false
          }
          break
      }
    }
  }
  return stack.length === 0 ? true : false
}

這種方法，是將左半邊括號，即(、[、{存入棧stack中，當遍歷到右半邊括號，即)、]、}的時候，stack執行出棧操作，然后將出棧的左半邊括號與遍歷到的有半邊括號匹配，看是否為與其相匹配的另半邊括號。如果遍歷完了，則判斷棧的長度，為0，則匹配，否則，比匹配。
我們同樣以{[()]}為例，前三項，即{、[、(入棧，當遍歷到)的時候，位于棧頂的"("后出棧與)比較，看是否匹配。后面的]、}也是一樣道理。

結語

現在漸漸發現，數據結構和正則表達式非常重要（這里的解決方法就分別用到了），雖然平時用得少，到一道有應用場景，你就會發現數據結構和正則表達式的強大了。

云服務器 GPU云服務器 java匹配括號里的二括號匹配c語言 php版本匹配問題穩定匹配問題c語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/80675.html

JS正則表達式一條龍講解，從原理和語法到JS正則、ES6正則擴展，最后再到正則實踐思路

摘要：控制權和傳動這兩個詞可能在搜一些博文或者資料的時候會遇到，這里做一個解釋先控制權是指哪一個正則子表達式可能為一個普通字符元字符或元字符序列組成在匹配字符串，那么控制權就在哪。溫馨提示：文章很長很長，保持耐心，必要時可以跳著看，當然用來查也是不錯的。正則啊，就像一座燈塔，當你在字符串的海洋不知所措的時候，總能給你一點思路；正則啊，就像一臺驗鈔機，在你不知道用戶提交的鈔票真假的時候，...

Michael_Lin 2019-08-20 13:39 評論0 收藏0
正則之基本入門

摘要：忽略大小寫全文查找出現的所有匹配字符多行查找全文查找忽略大小寫所以使用之后可以這樣寫表示忽略大小寫匹配或者正式入門正則正則其實就是用來匹配字符串的。惰性量詞使用方法基本量詞該量詞和貪婪量詞就像，一個是消極怠工，一個是積極工作。以前看了許許多多的正則教程，收貨并不多，往往都是蜻蜓點水，一點就過。事實上，正則用處真的超級大，比如匹配innerHTML的內容，以及表單驗證，也是非他莫屬。這...

ormsf 2019-08-19 17:31 評論0 收藏0
讀《精通正則表達式》-- 網上 js 正則基礎教程沒有涉及的一些知識

摘要：正則起源最近看完了精通正則表達式，收獲頗豐，略過了一些晦澀難懂的理論部分，主要看了實戰和教程部分。然后下面說一下以上兩個基礎教程里沒說到的知識點。最后以上是我在精通正則表達式一書中得到的一些收獲，希望能分享給大家，如有錯誤歡迎指正。正則起源最近看完了《精通正則表達式》，收獲頗豐，略過了一些晦澀難懂的理論部分，主要看了實戰和教程部分。下面引用一下百度百科里的內容。正則表達式的鼻...

GT 2019-08-23 10:42 評論0 收藏0
JS正則表達式元字符

摘要：表示非單詞字符，等效于正則教程返回完整的字符串，因為，中文算作是非單詞字符。行首行尾，修飾符形式修飾符的作用是修改和在正則表達式中的作用，讓它們分別表示行首和行尾。正則描述正則描述 f 匹配換頁符匹配制表符匹配換行符 v 匹配垂直制表符匹配回車 s 匹配單個空格，等同于[f v]; S...

CODING 2019-08-22 10:55 評論0 收藏0
正則表達式

摘要：正則表達式產生回溯的地方貪婪量詞前面的匹配的是，后面的匹配的是惰性量詞惰查看原文站點，更多擴展內容及更佳閱讀體驗！查看原文：正則表達式正則表達式正則表達式是匹配模式，要么匹配字符，要么匹配位置。字符匹配兩種模糊匹配正則表達式能實現模糊匹配模糊匹配，有兩個方向上的模糊：橫向和縱向橫向模糊匹配橫向模糊指的是，一個正則可匹配的字符串的長度不是固定的實現方式是使用...

Dean 2019-08-22 18:09 評論0 收藏0