题干
给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:
- () 得 1 分。
- AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
- (A) 得 2 * A 分,其中 A 是平衡括号字符串。
示例一:
输入: "()"
输出: 1
示例二:
输入: "(())"
输出: 2
示例三:
输入: "()()"
输出: 2
示例四:
输入: "(()(()))"
输出: 6
题解
解题思路
- 将字符串转换为
[1, [1]]
这种数组嵌套型的数据结构,然后深度遍历计算值
/**
* 将平衡括号字符串转换为 数组数据结构
* @param {*} str 字符串
* @returns {Array} 数组
* @example (()(())((())())) => [ 1, [ 1 ], [ [ 1 ], 1 ] ]
*/
function transfer(str) {
let cur = {
value: []
}
let deep = 0
str.split('').forEach(s => {
switch (s) {
case '(':
deep++
if(deep >= 1) {
cur = {
parent: cur,
value: []
}
}
break
case ')':
deep--
if(deep >= 0) {
const tmp = cur.parent
tmp.value.push(cur.value.length > 0 ? cur.value : 1)
cur = tmp
}
break
}
})
return cur.value
}
- 递归遍历计算求值
/**
* 计算 平衡括号字符串 对应数组数据结构的值
* @param {*} arr 平衡字符串转换数组
* @returns {Number} 计算结果
* @example [ 1, [ 1 ], [ [ 1 ], 1 ] ] => 9
*/
function computed(arr) {
let total = 0
arr.forEach(o => {
if(Array.isArray(o)) {
total += 2 * computed(o)
} else {
total += o
}
})
return total
}
本方法通过了 Leetcode 的测试用例,但是执行性能上还可以继续想想优化的方案