JavaScript 中解析和平衡尖括號問題

---

在給定的問題陳述中，我們必須藉助 Javascript 功能來確定程式碼中的尖括號是否平衡。因此，為了解決此問題，我們將使用基於棧的方法，並使用 Javascript 方法。

什麼是基於棧的方法？

基於棧的方法是一種演算法技術，它涉及使用稱為棧的資料結構。因此，棧是支援兩個主要操作的專案集合：push 和 pop。Push 操作將專案新增到棧的頂部，pop 從棧中刪除頂部專案。

棧的主要特性是它遵循 LIFO（後進先出）原則。這意味著最後推入棧的專案將是第一個被彈出的專案。或者我們可以說，專案僅從稱為頂部的棧的一端新增和刪除。

例如，棧類似於一疊書或盤子。我們可以將新書或盤子新增到頂部，當我們必須移除一個時，我們可以從最上面的那個移除。

理解問題

眼前的問題是解析和平衡給定字串中的尖括號。尖括號通常用於 HTML 和 XML 語言中，用於表示開始和結束標籤。但必須記住，這些括號是平衡且巢狀的，以避免語法錯誤。

因此，我們的目標是確定給定字串中的尖括號是否平衡。這意味著對於每個開始尖括號“<”都應該有一個對應的結束尖括號“>”。並且我們必須確保它們彼此正確巢狀。

給定問題的邏輯

為了解決此問題，我們將使用基於棧的方法。在演算法中，我們將遍歷給定輸入字串中的每個字元，當我們遇到開始尖括號時，我們將將其壓入棧中。當找到結束尖括號時，我們將針對棧的頂部進行檢查，以確保開始括號是否存在。如果括號匹配，則開始括號將從棧中彈出。

因此，在執行所有這些操作後，該函式將檢查棧是否為空。如果棧為空，則表示所有括號都處於平衡狀態，結果將為真。在其他情況下，如果棧不為空，則表明存在不匹配的開始括號，我們將結果返回為假。

演算法

步驟 1：在演算法中，第一步是建立一個函式並將其命名為 isBalanced。在此函式內部，我們將傳遞一個輸入作為引數。此函式將主要檢查括號是否平衡。

步驟 2：現在我們需要使用一個空棧來儲存輸入。push 和 pop 操作將在該棧上執行。

步驟 3：為了迭代輸入的專案，我們將使用 for 迴圈。在此迴圈內部，我們將使用另一個名為 char 的變數。此 char 變數將跟蹤當前輸入。

步驟 4：檢查 char 變數是否包含開始括號的條件。如果條件為真，則在塊內我們將開始括號壓入棧中。

步驟 5：如果上述條件不成立，我們將檢查另一個條件。如果 char 變數包含結束括號，並且如果發現棧長度為零，我們將返回 false。如果它不滿足第二個條件，我們將從棧中彈出匹配的開始尖括號。

步驟 6：最後，我們將檢查棧是否為空的條件。如果為真，則我們確保括號是平衡的。

示例

function isBalanced(input) {
   const stack = [];

   for (let i = 0; i < input.length; i++) {
      const char = input[i];

      if (char === '<') {
         // Push opening angle bracket onto the stack
         stack.push(char);
      } else if (char === '>') {
         if (stack.length === 0) {
            // Found a closing angle bracket without opening bracket
            return false;
         }
         // Pop the matching opening angle bracket
         stack.pop();
      }
   }

   return stack.length === 0;
}

console.log(isBalanced("<div>"));
console.log(isBalanced("<div"));
console.log(isBalanced("<<div>>>"));
console.log(isBalanced("<div></div>"));

輸出

true
false
false
true

複雜度

解析和平衡尖括號的程式碼的複雜度為 O(n)，其中 n 是輸入字串的大小。由於程式碼遍歷輸入字串中的字元一次，並且對每個字元執行恆定數量的操作。這就是為什麼時間複雜度與輸入字串的大小成正比。並且在最壞情況下，程式碼的空間複雜度也是 O(n)。如果輸入字串中的所有字元都是開始尖括號。

結論

因此，我們已成功建立了一個函式來檢查輸入字串是否已解析並使用開始和結束尖括號平衡，沒有任何錯誤。它使用基於棧的方法實現，以獲得有效的時間和空間複雜度。