关于JS括号匹配的面试题

微信扫一扫,分享到朋友圈

关于JS括号匹配的面试题

之前在面试的过程中经常会遇到匹配括号的问题,比如下面这类题目:

  1. 编写一个函数,该函数接收一个算术表达式作为参数,返回括号缺失的位置。
2.3 + 23 / 12 + (3.14 * 0.24
复制代码
  1. 实现一个normalize函数,能将特定的字符串转化为特定的结构化数据。
[a[b[c]]]
// 转化为
{ value: 'a', children: { value: 'b', children: { value: 'c' } } }
复制代码

偷偷告诉你,第2题是阿里的面试题(这也太难了吧!)

之前看到这类的题目也是一脸懵逼,没有半点思路,然后有一天我在《数据结构与算法JavaScript描述》书中了解到通过栈可以用来判断一个表达式中括号是否匹配。

什么是栈?

栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。

咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞在这一摞盘子的最上面。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。

对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用 push() 方法,出栈使用 pop() 方法。图 演示了入栈和出栈的过程。

其实这些感念挺抽象的,慢慢理解吧。

实战

好了,我们先来做一个题,判断回文:回文是指这样一种现象:一个单词、短语或数字,从前往后写和从后往前写都是一样的。

单词“dad”、“racecar”就是回文
数字 1001 也是回文
复制代码
function isPalindrome(word) {
let s = [];
for (let i = 0; i < word.length; ++i) {
s.push(word[i]); // 入栈
}
let rword = "";
while (s.length() > 0) {
rword += s.pop(); // 出栈
}
if (word == rword) {
return true;
}
else {
return false;
}
}
复制代码

栈的特点就是先进后出,把字符添加到数组中的时候是正序,而取出来的时候是倒序,正是因为这种先进后出刚好相反的顺序,就可以判断回文了。

如果数字123,那么入栈是1、2、3,出栈是3、2、1,入栈和出栈得到的结果不一样,那么他们就不是回文。

如果字符dad,那么入栈是d、a、d,出栈是d、a、d,入栈和出栈得到的结果是一样,那么他们就是回文。

现在已经理解的栈的特点了吧。。。

前面有两道题目,第一题判断缺少的括号可以这么写,参考答案:

function demo (str) {
let sign = '(){}[]'
let map = {
'(': ')',
'{': '}',
'[': ']'
}
let s = []
for (let i = 0; i < str.length; i++) {
if (sign.includes(str[i])) {
let val = str[i];
switch (val) {
case '(':
case '[':
case '{': s.push(val); break;
case ')':
let map1 = s.pop();
if (map1 !== '(') {
return `位置${i}的)不匹配`
}
break;
case ']':
let map2 = s.pop();
if (map2 !== '[') {
return `位置${i}的]不匹配`
}
break;
case '}':
let map3 = s.pop();
if (map3 !== '{') {
return `位置${i}的}不匹配`
}
break;
}
}
}
if (s.length) {
return `符号${s.join()}没有闭合`
} else {
return '符号正确'
}
}
复制代码

我们的括号包括 (){}[] ,然后入栈是左边部分的括号,出栈是右边部分的括号,当两边的括号有对应关系的时候,说明括号匹配是正确的。

然后下面是第二题 [a[b[c]]] 转换为树结构的答案:

function normalize (str) {
let s = [];
let list = [];
let obj = {}
for (let i = 0; i < str.length; i++) {
let value = str[i]
switch (value) {
case '[':
s.push(i)
break;
case ']':
let leftIndex = s.pop();
list.unshift([leftIndex, i])
default:
break;
}
}
let [start, end] = list[0]
let parent = obj
for (let i = 1; i < list.length; i++) {
let [a, b] = list[i];
let result = str.slice(start + 1, a) + str.slice(b + 1, end);
start = a;
end = b;
parent.value = result;
parent.children = {};
parent = parent.children;
}
let [x, y] = list[list.length - 1]
parent.value = str.slice(x + 1, y)
return obj
}
复制代码

先匹配了括号在字符串中的位置保存在数组 list[ [ 0, 8 ], [ 2, 7 ], [ 4, 6 ] ] ,然后通过区间的范围可以知道左右两边的内容(0到2和7到8是第一个括号里面的内容,依次类推,注意最后的内容是4到6这个是闭合的关系),然后通过字符串截取的方式可以得到。最后通过对象之前的引用关系转换为树状结构。

微信扫一扫,分享到朋友圈

关于JS括号匹配的面试题

特斯拉:国内疫情向好 免费超级充电服务月底结束

上一篇

罗永浩抖音带货微博被投诉遭删除:后续来了

下一篇

你也可能喜欢

关于JS括号匹配的面试题

长按储存图像,分享给朋友