021.嵌套类问题的递归解题套路

前置知识：讲解 017、020、021、023、036、037，038 这些章节都分析过递归，尤其讲解 038，不熟悉的同学可以先熟悉一下

嵌套类问题的解题套路 §

大概过程：

1. 定义全局变量 where，标识字符串处理到哪里了
2. 递归函数 f(i)：从 i 位置出发开始解析，遇到字符串终止或嵌套条件终止就返回，返回值是 f(i) 负责这一段的结果
3. f(i) 在返回前更新全局变量 where，让上级函数通过 where 知道解析到了什么位置，进而继续

执行细节：

1. 如果 f(i) 遇到嵌套条件开始，就调用下级递归去处理嵌套，下级会负责嵌套部分的计算结
2. f(i) 下级处理完成后，f(i) 可以根据下级更新的全局变量 where，知道该从什么位置继续解析

题目1.含有嵌套的表达式求值 §

题目描述 §

实现一个基本的计算器来计算简单的表达式字符串

表达式字符串只包含非负整数，算符 +、-、*、/，左括号 ( 和右括号 )。整数除法需要向下截断

你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 $[-2^{31},2^{31}-1]$

注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval()

示例 1：

输入："1+1"

输出：2

示例 2：

输入："6-4/2"

输出：4

示例 3：

输入："2*(5+5*2)/3+(6/2+8)"

输出：21

测试链接 §

772.基本计算器 III

答案 §

package main
 
import "fmt"
 
var (
  s     string
  n     int
  where int // 处理到 s 的哪个下标了
)
 
func calculate(str string) int {
  s = str
  n = len(str)
  where = 0
  return f(0)
}
 
// S[i:] 开始计算，遇到字符串终止或者 ) 停止
// 返回: 自己负责的这一段，计算的结果
// 返回之间，更新全局变量 where，为了上游函数知道从哪继续
func f(i int) int {
  cur := 0
  numStack := []int{}
  opStack := []byte{}
  for i < n && s[i] != ')' {
    if s[i] >= '0' && s[i] <= '9' {
      cur = cur*10 + int(s[i]-'0')
      i++
    } else if s[i] != '(' { // + - * /
      pushStack(&numStack, &opStack, cur, s[i])
      i++
      cur = 0
    } else { // (
      cur = f(i + 1) // 跳过 (
      i = where + 1  // 跳过 )
    }
  }
  pushStack(&numStack, &opStack, cur, '+')
  where = i
  return compute(numStack, opStack)
}
 
func pushStack(numStack *[]int, opStack *[]byte, cur int, op byte) {
  stackSize := len(*numStack)
  if stackSize == 0 || (*opStack)[stackSize-1] == '+' || (*opStack)[stackSize-1] == '-' {
    *numStack = append(*numStack, cur)
    *opStack = append(*opStack, op)
  } else {
    topNum := (*numStack)[stackSize-1]
    topOp := (*opStack)[stackSize-1]
    if topOp == '*' {
      (*numStack)[stackSize-1] = topNum * cur
    } else { // /
      (*numStack)[stackSize-1] = topNum / cur
    }
    (*opStack)[stackSize-1] = op
  }
}
 
// opStack 中只有 + -， * / 已经被 pushStack 处理了
func compute(numStack []int, opStack []byte) int {
  stackSize := len(numStack)
  ans := numStack[0]
  for i := 1; i < stackSize; i++ {
    op := opStack[i-1]
    if op == '+' {
      ans += numStack[i]
    } else { // -
      ans -= numStack[i]
    }
  }
  return ans
}
 
func main() {
  testSet := []struct {
    expression string
    ans        int
  }{
    {"", 0},
    {"1+1", 2},
    {"6-4/2", 4},
    {"2*(5+5*2)/3+(6/2+8)", 21},
  }
 
  for _, v := range testSet {
    if calculate(v.expression) != v.ans {
      panic("error")
    }
  }
  fmt.Println("success")
}

复杂度 §

时间复杂度：$O(n)$

where 不后退，一直往前走

题目2.含有嵌套的字符串解码 §

题目描述 §

示例 1：

输入："3[a]2[bc]"

输出："aaabcbc"

示例 2：

输入："3[a2[c]]"

输出："accaccacc"

示例 3：

输入："2[abc]3[cd]ef"

输出："abcabccdcdcdef"

示例 4：

输入："abc3[cd]xyz"

输出："abccdcdcdxyz"

测试链接 §

394.字符串解码

答案 §

var (
	s     string
	n     int
	where int
)
 
func decodeString(str string) string {
	s = str
	n = len(str)
	where = 0
 
	return f(0)
}
 
func f(i int) string {
	count := 0
	var builder strings.Builder
	for i < n && s[i] != ']' {
		if s[i] >= '0' && s[i] <= '9' {
			count = count*10 + int(s[i]-'0')
			i++
		} else if s[i] != '[' { // 字母
			builder.WriteByte(s[i])
			i++
		} else { // [
			builder.WriteString(strings.Repeat(f(i+1), count))
			i = where + 1
			count = 0
		}
	}
	where = i
	return builder.String()
}

复杂度 §

时间复杂度：$O(n)$

题目3.含有嵌套的分子式求原子数量 §

题目描述 §

示例 1：

输入："H2O"

输出："H2O"

解释：原子的数量是 {H: 2, O: 1}

示例 2：

输入："Mg(OH)2"

输出："H2MgO2"

解释：原子的数量是 {H: 2, Mg: 1, O: 2}

示例 3：

输入："K4(ON(SO3)2)2"

输出："K4N2O14S4"

解释：原子的数量是 {K: 4, N: 2, O: 14, S: 4}

元素按字典序排序

测试链接 §

726.原子的数量

答案 §

var (
	s     string
	n     int
	where int
)
 
func countOfAtoms(formula string) string {
	s = formula
	n = len(formula)
	where = 0
	var ans strings.Builder
	rbt := f(0)
	for it := rbt.Iterator(); it.Next(); {
		node := it.Node()
		ans.WriteString(node.Key.(string))
		count := node.Value.(int)
		if count > 1 {
			ans.WriteString(strconv.Itoa(count))
		}
	}
	return ans.String()
}
 
func f(i int) *redblacktree.Tree {
	// ans 是总表
	ans := redblacktree.NewWithStringComparator()
	// 之前收集到的有序表，历史一部分
	var prev *redblacktree.Tree
	// 之前收集到的名字，历史一部分
	var name strings.Builder
	// 历史翻几倍
	count := 0
	for i < n && s[i] != ')' {
		if s[i] >= 'A' && s[i] <= 'Z' || s[i] == '(' {
			fill(name.String(), count, ans, prev)
			name.Reset()
			prev = nil
			count = 0
			if s[i] != '(' {
				name.WriteByte(s[i])
				i++
			} else {
				prev = f(i + 1)
				i = where + 1
			}
		} else if s[i] >= '0' && s[i] <= '9' {
			count = count*10 + int(s[i]-'0')
			i++
		} else { // a-z
			name.WriteByte(s[i])
			i++
		}
	}
	fill(name.String(), count, ans, prev)
	where = i
	return ans
}
 
func fill(name string, count int, ans, prev *redblacktree.Tree) {
	if count == 0 {
		count = 1
	}
	if len(name) > 0 {
		if v, has := ans.Get(name); has {
			count += v.(int)
		}
		ans.Put(name, count)
	} else if prev != nil {
		for it := prev.Iterator(); it.Next(); {
			node := it.Node()
			name = node.Key.(string)
			cnt := node.Value.(int) * count
			if v, has := ans.Get(name); has {
				cnt += v.(int)
			}
			ans.Put(name, cnt)
		}
	}
}

复杂度 §

时间复杂度：$O(n)$