Dart计算Content spinning嵌套结构组合数的实现问题求助

实现思路 #

正则表达式本身不适合处理嵌套结构，我们可以通过栈计数 + 递归计算的方式处理嵌套占位符：

• 用栈跟踪大括号的嵌套深度，找到所有完整的占位符块
• 优先计算最内层占位符的组合数，逐层向外汇总
• 同一块内用|分割的多个选项的组合数是各选项组合数的和，不同并列块的组合数是各块组合数的乘积

完整Dart实现代码 #

int calculateSpinningCombinations(String pattern) {
  // 移除所有空白字符，避免空格干扰分割逻辑
  pattern = pattern.replaceAll(RegExp(r'\s+'), '');
  return _calculate(pattern);
}

int _calculate(String s) {
  List<int> stack = [];
  List<String> parts = [];
  int start = 0;

  for (int i = 0; i < s.length; i++) {
    if (s[i] == '{') {
      if (stack.isEmpty) {
        // 新占位符开始，先存入占位符前的普通文本段
        if (i > start) {
          parts.add(s.substring(start, i));
        }
        start = i + 1;
      }
      stack.add(i);
    } else if (s[i] == '}') {
      stack.removeLast();
      if (stack.isEmpty) {
        // 占位符闭合，递归计算当前占位符的组合数
        String placeholderContent = s.substring(start, i);
        int placeholderCount = _calculatePlaceholder(placeholderContent);
        parts.add('*$placeholderCount');
        start = i + 1;
      }
    }
  }
  // 存入最后剩余的普通文本段
  if (start < s.length) {
    parts.add(s.substring(start));
  }

  // 并列块组合数为乘积，普通文本视为1种组合不影响结果
  int total = 1;
  for (String part in parts) {
    if (part.startsWith('*')) {
      total *= int.parse(part.substring(1));
    }
  }
  return total;
}

int _calculatePlaceholder(String content) {
  List<int> stack = [];
  List<String> options = [];
  int start = 0;

  for (int i = 0; i < content.length; i++) {
    if (content[i] == '{') {
      stack.add(i);
    } else if (content[i] == '}') {
      stack.removeLast();
    } else if (content[i] == '|' && stack.isEmpty) {
      // 遇到同级分隔符，拆分出独立选项
      options.add(content.substring(start, i));
      start = i + 1;
    }
  }
  options.add(content.substring(start));

  // 同占位符内多个选项为互斥关系，组合数相加
  int total = 0;
  for (String option in options) {
    total += _calculate(option);
  }
  return total;
}

测试验证 #

void main() {
  // 平级场景测试
  print(calculateSpinningCombinations("{hello|hi} {world|everyone}")); // 输出4
  // 嵌套场景测试
  print(calculateSpinningCombinations("{hi|{john|jane}}")); // 输出3
  // 复杂嵌套测试：{a|{b|c|d}} {x|{y|z}} 总组合数为(1+3)*(1+2)=12
  print(calculateSpinningCombinations("{a|{b|c|d}} {x|{y|z}}")); // 输出12
}

实现说明 #

• 普通文本不产生组合变量，视为1种可能，不影响乘积结果
• 单个占位符内的多个选项是互斥关系，所以组合数相加
• 多个并列的占位符是独立关系，所以组合数相乘
• 自动忽略输入字符串中的所有空白字符，适配带空格的写法

内容的提问来源于stack exchange，提问作者Nicolas