isBalanced函數實作

原文：從一道面試題談起，作者：360奇舞團 劉觀宇

題目：

建立一個函數來判斷給定的表達式中的大括号是否閉合，傳回 true/false，對于空字元串，傳回 true

var expression = "{{}}{}{}"
var expressionFalse = "{}{{}"

function isBalanced (exp) {}
           

題目本身比較簡單。看完文章實作，感覺實作思路很重要，更要能舉一反三。

雖然大學的時候也學了資料結構，棧，但應用的很少，看完本文，對棧在實際工作中的應用，也有了全新的思路與看法。

實作

以下是應用資料結構棧的特點，先進先出，在 js 中用數組模拟實作的代碼。

function isBalanced (exp) {
  if (!(exp + '').trim()) {
    return true;
  }

  let stack = [];
  let arr = exp.trim().split('');
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    if (item === '{') {
      stack.push(item);
    } else if (item === '}') {
      if (!stack.length) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0
}

// test
var expT = '{{}}{}{}';
var expF = '{}{{}'

console.log(isBalanced('')); // true
console.log(isBalanced(expT)); // true
console.log(isBalanced(expF)); // false
           

利用棧先進先出的特點，找到一個 { ，就壓入棧中；而找到一個 } ，如棧中是空的，則直接傳回false，否則就從棧中彈出一個 { 。循環結束後，通過判斷棧是否為空，判斷字元中中 {} 是否閉合。

舉一反三

題目一：實作函數 isBalanced, 用 true/false 表示給定的字元串的括号是否平衡（一一對應）。注意要支援三種類型的括号，帶有交錯括号的字元串應該傳回false

isBalanced('(foo { bar (baz) [boo] })') // true
isBalanced('foo { bar { baz }') // false
isBalanced('foo { (bar [baz] } )') // true
           

實作思路和上面的是一緻的，也是利用棧的特性。

過濾無效字元，每一種有括号有一種唯一的左括号與之對應。

實作：

function isBalanced (exp) {
  if (!(exp + '').trim()) {
    return true;
  }

  let stack = [];
  let signObj = {
    '{': '}',
    '(': ')',
    '[': ']'
  };

  let arr = exp.trim().split('');
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    if (signObj.hasOwnProperty(item)) { // stack 中隻壓入指定符号
      stack.push(item);
    } else if (Object.values(signObj).includes(item)) { // 針對指定符号的值比對，得到對象key
      let leftSign;
      for(let key in signObj) {
        if (item === signObj[key]) {
          leftSign = key;
        }
      }
      if (stack[stack.length - 1] !== leftSign) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;
}

// test
console.log(isBalanced('')); // true
console.log(isBalanced('(foo { bar (baz) [boo] })')); // true
console.log(isBalanced('foo { bar { baz }')); // false
console.log(isBalanced('foo { (bar [baz] } )')); // false
           

通過對象的鍵值對過濾掉無效字元，再通過值找到對應的key，和棧中最後壓入的進行比較，不相等就是不比對直接false，相等就表示比對，然後把棧中的最後的彈出。

通過map和es6的文法，可以把代碼寫的

一氣呵成

。

function isBalanced (exp) {
  if (!(exp + '').trim()) {
    return true;
  }
  
  const map = new Map([
    ['{', '}'],
    ['(', ')'],
    ['[', ']']
  ]);

  let stack = [];
  let arr = exp.trim().split('');
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    if (map.has(item)) {
      stack.push(item);
    } else if ([...map.values()].includes(item)) {
      if (stack[stack.length - 1] !== [...map.entries()].filter(el => el[1] === item).pop().shift()) {
        return false;
      }
      stack.splice(stack.length - 1, 1);
    }
  }

  return stack.length === 0
}
           

說明：

[...map.entries()]

的結果是二維數組，這個看懂了，就比較容易了解了

[
  ['{', '}'],
  ['(', ')'],
  ['[', ']']
]
           

題目二：要求嚴格限制括号的順序，即中括号外圍隻能是大括号，内部隻能是小括号。也即：括号隻能以大括号、中括号、小括号的順序隻能前面的包含後面的，不能後面的包含前面的，用代碼來表示一下

isStrictBalanced('foo { bar (baz) [boo] }') // true

isStrictBalanced('(foo { bar (baz) [boo] })') // false
           

實作思路，在入棧的時候判斷優先級。

怎麼判斷優先級，利用字元比較。這是我沒想到的，都不知道這三個的具體charCodeAt值。(_)

"{".charCodeAt() === 123，"[".charCodeAt() === 91，"(".charCodeAt() === 40
           

function isBalanced (exp) {
  if (!(exp + '').trim()) {
    return true;
  }

  let stack = [];
  let signObj = {
    '{': '}',
    '[': ']',
    '(': ')'
  };
  let keys = Object.keys(signObj);

  let arr = exp.trim().split('');
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    if (signObj.hasOwnProperty(item)) {
      // stack 中隻壓入指定符号，并且判斷優先級
      // "{".charCodeAt() === 123，"[".charCodeAt() === 91，"(".charCodeAt() === 40
      if (stack.length) {
        let pop = stack.slice().pop()
        if (pop < item) {
          return false
        }
      }
      stack.push(item);
    } else if (Object.values(signObj).includes(item)) { // 針對指定符号的值比對
      let leftSign;
      for(let key in signObj) {
        if (item === signObj[key]) {
          leftSign = key;
        }
      }
      if (stack[stack.length - 1] !== leftSign) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;
}

// test
console.log(isBalanced('')); // true
console.log(isBalanced('foo { bar (baz) [boo] }')); // true
console.log(isBalanced('(foo { bar (baz) [boo] })')); // false
console.log(isBalanced('(foo [bar])')); // false
console.log(isBalanced('[foo (bar)]')); // true
console.log(isBalanced('[foo (bar)] {bar [boo] }')); // true
           

思路通了，用map和es6實作其實也很容易，就不浪費筆墨了。