递归函数检查字符串是否为"平衡"

Question

我有一个问题,我必须使用递归编写算法(不能使用循环).
问题是我的函数应检查给定的字符串是否为"Balanced".
该字符串仅包含字母(无符号)和仅(" [ "," ] ")括号.
(例如:" [aa] [abbsa] ").

假设每个"开括号"(" [ ")都有一个结束符(" ] "),换句话说,字符串中的括号是平衡的,不需要检查它.
字符串始终是以下两种格式之一:

1. 简单字符串:字符.

它只包含没有括号的字符.(例如:"aaabbcc").

2. 包含2个子字符串的字符串:

[ 左 ] [ 右 ]

左:本身是一个子字符串,实际上可以是两种格式(简单字符串或带有2个子字符串的字符串)

右:本身是一个子字符串,实际上可以使用两种格式(简单字符串或带有2个子字符串的字符串)

编辑:字符串是有效的,没有必要检查它是否合法.它总是提到的格式和示例之一(也可能更复杂,但它总是合法的).

编辑:字符串只能是第一种格式,或第二种格式.如果它是第二种格式,那么它包括第一种格式,它必须以"["开头并以"]"结尾.
示例:"aaabbbb"(第1格式)."[aa] [bbbb]"(第2格式)."[[aa] [b]] [[[a] [bbb]] [aaaa]]"(第2格式).

如果字符串满足以下至少一个条件,则该字符串为Balanced:

1. 该字符串来自第一格式.

2. 字符串来自第二个格式,左侧的字符数(没有括号)(称为称重)是偶数,右侧的权重也是如此.

3. 字符串来自第二格式,LEFT侧的权重也是ODD,右侧的权重也是.

例子:

字符串" [abcde] [xyz] "是Balanced,因为Right weight和Left weight都是ODD.

字符串" [abcde] [xyzw] "未平衡,因为右权重是偶数(4是偶数)而左权重是奇数(5是奇数).

字符串" [abcdef] [[x] [yzw]] "是平衡的.
左权重为6.
子字符串" [x] [yzw] "是平衡的.(左权重为1,右权重为3(均为ODD)).
" [x] [yzw] " 的权重是4.因此," [abcdef] [[x] [yzw]] "是平衡的,因为左右权重都是偶数.

" [[abcde] [xyzw]] [Z] "是平衡的,即使子串" [abcde] [xyzw] " 不平衡!因为它的重量是9,而" [Z] "的重量是1,它们都是ODD.

所以,我必须在C中编写一个递归函数,它接收一个"字符串".

int verify_weight(char s[])
{
    //Code I need here
}

它会检查字符串及其中的子字符串,然后如果它们是否平衡则打印每个字符串.
例如:string" [[aa] [b]] [[[x] [yy]] [hhhhh]] ".
它打印这个:
不平衡:2,1
不平衡:1,2
平衡:3,5
不平衡:3,8

我也被允许创建另一个函数来帮助解决它(仅递归).

编辑:(答案)
谢谢大家的好解决方案,这是@ kolmar的解决方案.

代码:(在@ kolmar对我的函数名称的答案之后编辑)

#include "stdio.h"

int between_balanced(char s[], int n)
{
  if (!s[0] || (s[0] == ']' && n == 1)) return 0;
  return 1 + between_balanced(s+1, n + (
    s[0] == '[' ? 1 :
    s[0] == ']' ? -1 :
    0
  ));
}

int verify_weight(char s[])
{
  if (s[0] == '[') {
    int left = verify_weight(s+1);
    int right = verify_weight(s + between_balanced(s, 0) + 2);

    if (left % 2 == right % 2) {
      printf("balanced: ");
    } else {
      printf("imbalanced: ");
    }
    printf("%d,%d\n", left, right);

    return left+right;
  } else {
    return between_balanced(s, 1);
  }
}
int main() {
    char s[100];
    scanf("%s", s);
        printf("%d\n", verify_weight(s));
return 0;
}

对不起这个很长的问题,但我真的需要帮助,我花了很多时间试图解决它,但我不能.感谢您的时间和帮助!

Answer 1

让我们忘记我们暂时不能使用循环的事实，并尝试思考解决它的算法。我们需要做的是在给定字符串中找到每个左括号匹配的右括号的位置。之后，解决方案变得几乎微不足道：我们可以创建一个辅助函数，它接受一个 char 数组和两个索引：下限和上限，并执行以下操作（它是伪代码）：

// low is inclusive, high is not.
int get_weight(char[] s, int low, int high) {
    if (low == high || s[low] is not a bracket) // The base case: a simple string.
        return high - low;
    int mid = get_matching_index(low); // An index of a matching bracket.
    // Solves this problem recursively for the left and the right substrings.
    int left_weight = get_weight(s, low + 1, mid);
    int right_weight = get_weight(s, mid + 2, high - 1);
    // Prints balanced/imbalanced depending on the left_weight and the right_weight.
    return left_weight + right_weight;
}

所以问题是如何找到匹配的括号对。如果我们可以使用循环，我们可以应用标准的基于堆栈的算法（从左到右迭代字符串，如果它是左括号，则将位置推入堆栈，如果它是右括号，则从堆栈中弹出顶部元素一）。即使我们不允许使用循环，我们也可以模拟它：

int i;
for (i = 0; i < n; i++) {
    // do something 
}

可以实现为

void iterate_recursively(int i, int n) {
    if (i < n) {
        // do something
        iterate_recursively(i + 1, n);
    }
}

...

iterate_recursively(0, n)

堆栈的实现不需要任何循环，仅此而已。