人生无根蒂，飘如陌上尘。分散逐风转，此已非常身。落地为兄弟，何必骨肉亲！得欢当作乐，斗酒聚比邻。盛年不重来，一日难再晨。及时当勉励，岁月不待人。 晋.陶渊明《杂诗》

笔者做面试官时候，除了考察常规的前端技能、框架的特性外，经常会出一些很简单的算法题目。这种经典题目的好处是言简意赅，在很短的时间就可以完成。但却能考察出工程师的基本计算机功力，以及知识储备。特别对于Javascript而言，还可以避免技术栈不同对于工程师能力的误判。

下面就是一道笔者经常考核的题目：

创建一个函数来判断给定的表达式中的大括号是否闭合，返回True/False，对于空字串，返回True：

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

function isBalanced(exp) {}

题目本身比较简单。不同的同学拿到题目会有不同的第一反应。

有的同学仅仅查找各种括号的个数，这种是不可以的，这种括号是不匹配的：}{。

有很多同学试图使用正则表达式解决问题。其思路是找到所有邻接的匹配的括号对，然后将其替换为空，直到不能替换为止。此时如果最后得到的字符串为空即为匹配，否则不匹配，代码很简洁，如下：

function isBalanced(exp) {
  var reg =  /\{\}/g, len;
  do{
      len  = exp.length;
      exp = exp.replace(reg, "")
  } while (len != exp.length)
  return exp.length === 0
}

好像也是可以的。但是问题点至少有二：

第一、此算法的最坏的时间复杂度是O(n^2)级别的，对于长篇大论是不友好的。

第二、此算法的正则表达式普适性较差，对于表达式含有其他干扰字符时候需要频繁修改正则表达式。当正则表达式过于复杂时候，反过来又会影响到检索效率。

其实，有时候最淳朴的做法，可能会更有效。

大家在数据结构课程中曾经学习过“栈”这种数据结构。“栈”是一种满足后进先出的抽象数据结构。这个结构在这道题目中可以帮助到我们。

思路如下：

1. 巡检字符串，将括号分类，一类是左括号、一类是右括号。
2. 左括号看作是入栈信号，右括号是出栈信号。
3. 当出栈时，如果栈定没有与之匹配的元素，则宣告不匹配。
4. 当巡检完毕，如果得到空栈，则匹配，否则不匹配。

写成代码大致就是这样，时间复杂度是O(n)：

function isBalanced(exp){
    let info = exp.split("")
    let stack = []

    for(let i = 0; i < info.length; ++i){
                let el = info[i]
        if (el == "{"){
            stack.push("{")
        }
        else if (el == "}"){
            if(stack.length === 0){
                return false;
            }
            stack.pop()
        }
    }

    return stack.length === 0
}

在Javascript里，Array可以很方便的模拟栈的行为。读者有兴趣也可以自己实现一个简单的栈，用以丰富自己的代码工具箱。

另外，由于题目中的括号情形比较简单，很多同学用标志位来解决，即当为左括号时候，置标志位，为右括号时候，当标志位存在，取消标志位，否则判定不匹配。最后没有标志位则为匹配。这种解法，对于题目中的状况是可以的。

我们还可以把题目再向前面推进一步，看一看更一般的括号和字符串的情形：

实现函数isBalanced，用true或false表示给定的字符串的括号是否平衡（一一对应）。注意了是要支持三种类型的括号{}，[]，和()。带有交错括号的字符串应该返回false。

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

基本思路和上面的解法是类似的。只是这里面需要注意两点：

1. 过滤掉非括号的干扰字符。
2. 每一种右括号有一种唯一的左括号与之对应。出现右括号时候，栈顶的左括号必须是和它匹配的。

对于第二种，大家应该很自然的联想到用JSON对象控制，这个是可以的。其实在ES6中，有Map这样的数据结构作为更专业的键值对存储结构可以使用。同时，一些好玩的语法和特性如扩展语法，箭头函数可以让我们把程序写得更加一气呵成。下面是一个可行的代码：

const isBalanced = (str) => {
    const map = new Map([
        ["{", "}"],
        ["[", "]"],
        ["(", ")"]
    ])

    let stack = [];

    for(let i = 0 ; i < str.length; ++i){
        let node = str[i]

        if (map.has(node)){
            stack.push(node)    
        }
        else if ([...map.values()].includes(node)){
            if (stack[stack.length - 1] !== 
                                [...map.entries()].filter(el=>el[1]===node).pop().shift()
                         ){
                return false
            }
            stack.splice(stack.length-1, 1)
        } 
    }    

    return stack.length === 0
}

很喜欢ES6的这些扩充，和这些新的数据结构。使得撰写Javascript有一种特别愉悦的体验。

让我们再次扩充一下这道题目。要求严格限制括号的顺序，即中括号外围只能是大括号，内部只能是小括号。也即：括号只能以大括号、中括号、小括号的顺序只能前面的包含后面的，不能后面的包含前面的，用代码来表示一下：

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

这样的需求怎么解决呢？

聪明的你可能已经想出了答案，其实就是在入栈时候判断一下当前的优先级就好了。这里可能需要判断一下当前的字符和栈顶元素的关系。这里，我们如果用Array的pop API，则会破坏stack的结构。上例中，我们用length来取得，这里我们用...语法来实现数组的复制，同时在上例基础上，进行一些重构，得到下列代码：

const isStrictBalanced = (str) => {
    const map = new Map([
        ["{", "}"],
        ["[", "]"],
        ["(", ")"]
    ])
    let stack = [], keys = [...map.keys()], values = [...map.values()];
    for(let i = 0 ; i < str.length; ++i){
        let node = str[i]
        if (map.has(node)){
            if (stack.length){
                let arr = [node, [...stack].pop()]
                    .map(el => keys.indexOf(el))

                if (arr[0] < arr[1]){
                    return false
                }
            }
            stack.push(node)    
        }
        else if (values.includes(node)){
            let needKey = [...map.entries()].filter(el=>el[1]===node).pop().shift()
            if ([...stack].pop() !== needKey){
                return false
            }
            stack.pop()
        } 
    }    
    return stack.length === 0
}

从括号匹配的最简单情形，我们已经扩展到了比较复杂的括号匹配情形。至此，在逐步迭代的需求中给大家展示了栈的实际应用以及ES6中Map和扩展语法的使用。在面试的实际，即时反应很重要，也许并不拘泥于一种解法，从一点开始，逐步深入，慢慢延展，方能达到融会贯通，活学活用，这恐怕是面试官比较看中的。