问题:给出下面的字符串,请编写函数来校验括号是否匹配,要求函数尽可能通用。
1
let testString = "(()()()()";
方案

说明 类似问题使用栈数据结构的方式来进行匹配会比较合理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
  /* 1.提供简单的栈结构 Class */
class Stack {
constructor() {
this.data = [];
this.top = 0;
}
push(ele) {
this.data[this.top++] = ele;
}
pop() {
this.top--;
this.data.pop();
}
peek() {
return this.data[this.top - 1];
}
clear() {
this.top = 0;
this.data = [];
}
}

let stack = new Stack();

/* 2.括号字符串匹配校验函数 */
function matching(str) {
stack.clear(); /* 清栈操作 */
str = str.trim(); /* 字符串清理 */
for (let i = 0; i < str.length; i++) { /* 遍历字符串 */
if (str[i] == " ") continue; /* 如果当前字符是空格则跳过 */
if (stack.peek() == "(" && str[i] == ")") {
stack.pop(); /* 若匹配则执行出栈操作 */
} else {
stack.push(str[i]); /* 不匹配则执行入栈操作 */
}
console.log(i, stack.data) /* 打印检查栈内数据结构 */
}
return stack.top == 0; /* 返回结果 */
}

/* 3.测试数据 */
let res1 = matching("()");
console.log("_______");
let res2 = matching("(");
console.log("_______");
let res3 = matching("()(");
console.log("_______");
let res4 = matching("( (()) ()() ) ");
console.log(res1, res2, res3, res4);

打印参考:

在上面代码中matching函数中通过普通 for 循环遍历字符串,尝试使用forEach遍历调整代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
function matching(str) {
let stack = new Stack(); /* 实例化 */
str = str.trim(); /* 清理字符串前后可能存在的空格 */
if (str[0] == ")") return false; /* 如果开始字符为)那么直接结束 */

[...str].forEach((s, i) => {
if (s == " ") return; /* 如果当前字符是空格,那么忽略处理 */
/* 如果当前字符和栈顶字符匹配,那么就出栈,否则执行入栈操作 */
(stack.peek() == "(" && s == ")") ? stack.pop(): stack.push(s);
});
/* 如果栈内没有数据(都消除了),那么表示()总是合法成对匹配 */
return stack.top == 0;
}

在上面代码中我自己提供了一个 Stack 类来实例化 stack 栈对象,在面试中这样写可能代码显得有点多,下面我使用字符串来模拟栈结构调整代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 匹配函数 */
function matching(str) {
let len = 0; /* 1.使用字符串来模拟栈结构 */
let stack = ""; /* 2.初始化一个空栈 */
str = str.trim(); /* 3.对需要检查校验的字符串执行清理操作 */
if (str[0] == ")") return false; /* 4.如果第一个字符不正确那么直接结束 */

[...str].forEach((s, i) => { /* 5.遍历字符串 */
if (s == " ") return; /* 6.若当前字符为空字符串,那么就忽略处理 */

if (stack[len - 1] === "(" && s == ")") { /* 7.检查是否匹配,若匹配那么就执行出栈操作*/
len--;
stack = stack.slice(0, -1)
} else { /* 8.如果不匹配那么就执行入栈操作 */
len++;
stack += s
}
});
return len === 0; /* 9.根据栈的长度来判断是否匹配 */
}