递归函数检查字符串是否“平衡”

Question

我有一个问题需要使用递归算法编写（不能使用循环），题目要求我的函数应该检查给定的字符串是否“平衡”。该字符串仅包含字母（没有符号）和括号（“[”、“]”）。假设每个“开放括号”（“[”）都有一个对应的“闭合括号”（“]”），换句话说，字符串中的括号是平衡的，并且不需要检查。字符串始终是以下两种格式之一：

1. 简单字符串：字符。 2. 由两个子字符串组成的字符串：“[LEFT][RIGHT]”。

左侧子字符串可以是两种格式之一（简单字符串或由两个子字符串组成的字符串），右侧子字符串也可以是两种格式之一。如果字符串满足以下条件之一，则被认为是平衡的：

1. 字符串是第一种格式。 2. 字符串是第二种格式并且左侧的字符数（称为权重）是偶数，右侧的权重也是偶数。 3. 字符串是第二种格式并且左侧的权重是奇数，右侧的权重也是奇数。

例如，字符串“[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;
}

非常抱歉这是一个很长的问题，但我真的需要帮助，我花了很多时间尝试解决它，但我没能成功。感谢您的时间和帮助！

- Buk Lau

---

这是给我妹妹的，她要参加递归考试，已经学习了好几天。她问我一个问题，但我无法解决，我们花了很多时间尝试解决它，但是我们无法做到...我认为我们在递归方面缺少一些基础知识。 - Buk Lau

你有尝试过写任何东西吗？ - Iharob Al Asimi

基本功能应该找到字符串的左半部分和右半部分，然后递归调用自身以获取两个部分的权重。然后可以打印出它们是否平衡，并通过对两个递归调用的返回值求和来返回总权重。您需要解决如空字符串或没有子字符串的字符串等基本情况的处理方法。在您实现一些实际代码并回来报告具体问题之前，我们无法为您提供更多帮助。 - Katie

我猜在递归中也需要使用循环，你所说的“NO LOOPS”到底是指非迭代解决方案还是根本不允许使用循环？ - advocateofnone

我刚注意到你提到找不到获取右侧的方法。在处理成对的括号时，一个有用的技巧是保持一个运行计数器。每次看到一个开放的括号就将其增加，每次看到一个关闭的括号就将其减少。当计数器达到零时，这意味着您刚刚读取了左字符串末尾的闭合括号，因此下一个字符必须是右字符串的开头。 - Katie

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");
    }
}

- Juan Lopes

---

OP并没有要求验证输入是否符合规范，只有在给定规范的情况下才能保持平衡。而“ab[c]”不是一个有效的输入字符串。参见：“字符串始终是这两种格式之一”。 - Juan Lopes

@BukLau，你能验证字符串是否始终有效吗？ - advocateofnone

我解释错了，它只能是第一种格式或第二种格式。如果是第二种格式，则包括第一种格式，并且必须以“ [”开头并以“]”结尾。对此我感到抱歉...我也在问题中进行了编辑。 - Buk Lau

严格来说，你需要一个strlen的递归定义才是正确的;-) - Alnitak

Answer 2

单一功能解决方案：

// rs - if we are in the right side bracket now
// ob - unmatched open brackets in the left hand side
// wl - weight of left side
// wr - weight of right side
// call as check(your_string, 0, 0, 0, 0)
int check(char *s, int rs, int ob, int wl, int wr) 
{
  if (!*s) return !rs || wl % 2 == wr % 2;
  if (rs) return check(s+1, rs, ob, wl, wr+1);
  if (s[0] == ']') return check(s+1, ob==1, ob-1, wl, wr);
  if (s[0] == '[') return check(s+1, rs, ob+1, wl, wr);
  return check(s+1, rs, ob, wl+1, wr);
}

编辑：

这里是解决方案，它会为格式2中的每个子字符串打印出它是否平衡：

#include "stdio.h"

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

int get_weight(char *s)
{
  if (s[0] == '[') {
    int left = get_weight(s+1);
    int right = get_weight(s + get_length(s, 0) + 2);

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

    return left+right;
  } else {
    return get_length(s, 1);
  }
}

- Kolmar

---

不错的解决方案。只有一件事，"abc" 不是应该有效吗？ - Juan Lopes

[0][[00][0]] 在 [[00][0]] 中右侧未平衡，但此处返回 true。 - ryanpattison

@rpattiso 一个不平衡的侧面并不会使整个字符串不平衡。例如："[ [abcde] [xyzw] ] [Z]"是平衡的，即使..."（而[[00][0]]不是有效的输入，只有[00][0]才是）。 - Juan Lopes

@JuanLopes 是的，我忘记了那种情况，现在已经修复了。 - Kolmar

@BukLau 很高兴能够帮到你。另外，你在 between_balanced 中对于 if (!*s 的编辑是错误的。即使将其作为 char s[] 发送，s 仍然是指针。此处进行 !*s 检查的原因是防止递归发生，当用户输入为格式1时。如果输入保证始终为格式2，则可以完全删除 !s || 部分。如果输入可能为格式1，则应在此处使用 !*s 或 !s[0]，但不要使用 !s。 - Kolmar

Answer 3

先暂时忘记我们不能使用循环的事实，试着思考一个解决方案。我们需要做的是找到给定字符串中每个开括号对应的闭括号的位置。之后，解决方案就变得几乎微不足道了：我们可以创建一个帮助函数，它接受一个字符数组和两个索引：下限和上限，并执行以下操作（这是伪代码）：

// 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)

栈的实现不需要任何循环，就是这样。

- kraskevich

---

必须有一种只使用递归解决它的方法，而且不能使用堆栈（这个问题是为了我妹妹，她们还没有学习堆栈和队列）。 - Buk Lau

我不知道问题的具体细节，但通常当有人说要编写一个递归解决方案时，这并不意味着你不能使用循环，只是指递归解决方案而非迭代。如果您不想使用循环，则ILoveCoding已经提出了一种方法。 - advocateofnone

我理解，但问题要求仅使用递归。这是为了我妹妹的考试，而且只能使用递归。 - Buk Lau

那么，如果你想要的是ILoveCoding的方法，那就是你想要的。 - advocateofnone

@BukLau 好的，栈大小由字符串长度限制，因此可以使用数组来实现。 - kraskevich

Answer 4

我的解决方案基于将累积分数（权重）与目标分数匹配。评分函数是哈希函数的简化版本。由于“Balanced”长度为8字节，因此该值应能够适合64位长整型。

用Python编写，但类似于C语言。

def wfunc(s):
    ret = 0
    for x in s:
        ret <<= 8
        ret |= ord(x)
    return ret

def find_balanced(buf, index, score, target_score):
    end = len(buf) == index
    score_hit = score == target_score
    if end:
        return score_hit
    c = buf[index]
    enclosed = c == '[' or c == ']'
    if enclosed:
        if score_hit:
            return True
        else:
            # Reset accumulated value
            return find_balanced(buf, index+1, 0, target_score)
    score <<= 8
    score |= ord(c)
    return find_balanced(buf, index+1, score, target_score)


find_balanced('[Orama][Koma][[exmp][Balanced]', 0, 0, wfunc('Balanced')) # True
find_balanced('[Orama][Koma][[exmp][Balanceded]', 0, 0, wfunc('Balanced')) # False
find_balanced('[Orama][Koma][[exmp][Balance]', 0, 0, wfunc('Balanced')) # False

- sardok