c - 检查字符串是否为 "Balanced"的递归函数

Question

我有一个问题，我必须仅使用递归来编写算法(不得使用循环)。
问题说我的函数应该检查给定的字符串是否“平衡”。
该字符串仅包含字母(无符号)和(“ [ ” ，“ ] ”)那些括号。 (例如:“ [aa][abbsa] ”)。

假设每个“左括号”(“ [ ”)都有一个右括号(“ ] ”)，换句话说，字符串中的括号是平衡的，不需要检查那个。
字符串始终是以下两种格式之一:

简单字符串:人物。

它只包含没有括号的字符。 (例如:“aaabbcc”)。

带有 2 个子字符串的字符串:

[ 左 ][ 右 ]

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

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

编辑:字符串是有效的，不需要检查它是否合法。
它始终是提到的格式和示例之一(也可能更复杂，但它始终是合法的)。

编辑:字符串只能是第一种格式或第二种格式。如果是第二种格式，则包含第一种格式，并且必须以“[”开头并以“]”结尾。
示例:“aaabbbb”(第一种格式)。 “[aa][bbbb]”(第二种格式)。 “[[aa][b]][[[a][bbb]][aaaa]]”(第二种格式)。

如果字符串至少满足以下条件之一，则该字符串是平衡的:

该字符串来自第一种格式。

字符串来自第二种格式，左侧的字符数(不带括号)(我们称之为权重)是偶数，右侧的权重也是如此。

字符串来自第二种格式，左侧的权重是奇数，右侧的权重也是奇数。

例子:

字符串“ [abcde][xyz] ”是平衡的，因为右权重和左权重都是奇数。

字符串“ [abcde][xyzw] ” 不平衡，因为右权重是偶数(4 是偶数)而左权重是奇数(5 是奇数)。

字符串“ [abcdef][[x][yzw]] 是平衡的。
左权重为 6。
子字符串“ [x][yzw] ”是平衡的。 (左权重为 1，右权重为 3(均为奇数))。
“ [x][yzw] ”的权重是4。
因此，“ [abcdef][[x][yzw]] 是平衡的，因为左右权重都是偶数。

" [[abcde][xyzw]][Z] "是平衡的，即使子字符串 " [abcde][xyzw] "不平衡!因为它的权重是 9，而“ [Z] ”的权重是 1，它们都是奇数。

所以，我必须用 C 编写一个递归函数，它接收一个“字符串”。

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

它检查字符串和其中的子字符串，然后打印每个字符串是否平衡。
例如:
字符串“ [[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

纯递归版本(使用辅助函数)。

这个想法是找到左侧结束的位置(使用 left_side )，然后计算每一侧的非括号字符的数量(使用 count_side ):

#include <stdio.h>
#include <string.h>

int left_side(char* s, int i, int depth) {
    if (depth == 0) return i;
    if (s[i] == '[') return left_side(s, i+1, depth+1);
    if (s[i] == ']') return left_side(s, i+1, depth-1);
    return left_side(s, i+1, depth);
}

int count_side(char* s, int a, int b) {
    if (a==b) return 0;
    return count_side(s, a+1, b) + (s[a] != '[' && s[a] != ']');
}

int is_balanced(char* s) {
    if (s[0] != '[') return 1;
    int size = strlen(s);
    int left = left_side(s, 1, 1);
    return count_side(s, 0, left)%2 == count_side(s, left, size)%2;
}

int main() {
    char s[256];
    while(scanf("%s", s) != EOF) {
        printf("%s\n", is_balanced(s) ? "YES" : "NO");
    }
}