题干

给定一个平衡括号字符串 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 的测试用例，但是执行性能上还可以继续想想优化的方案

括号的分数

题干

题解

解题思路