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

Question

我有一个问题，我必须使用递归编写算法（不能使用循环）。
问题说我的函数应该检查给定的字符串是否是“平衡”。
该字符串只包含字母（无符号）且仅包含（“[”，“”“））括号。
（例如：“[aa] [abbsa]”）。

假设每一个“开括号”（“[‘）具有一个闭合一个（’]”），换句话说，该串中的括号是平衡的，而且也没有必要检查。
字符串始终是这两种格式之一：

1. 简单的字符串：特征。

它只包含没有括号的字符。 （例如：“aaabbcc”）。

与字符串2子串：

[LEFT] [RIGHT]

LEFT：它本身就是一个子字符串，它可以实际上处于两种格式之一S（简单字符串或与2次字符串字符串）

RIGHT：本身是一个子串，实际上可以是对两种格式的（简单的字符串或字符串2子串）

编辑：该字符串是有效的，没有必要检查它是否合法。它总是提到的格式和示例之一（可能也更复杂，但它总是合法的）。

编辑：字符串只能是第一种格式或第二种格式。如果它是第二种格式，那么它包含第一种格式，它必须以“[”开头并以“]”结尾。
例如：“aaabbbb”（第1格式）。 “[aa] [bbbb]”（第二格式）。 “[[aa] [b]] [[[a] [bbb]] [aaaa]]”（第二格式）。

该字符串是平衡，如果它满足以下条件中的至少一个：

1. 该字符串是从第一格式。

2. 该字符串来自第二格式，并且左边的字符（不包括括号）的数量（让它称为重量）是偶数，右边的权重也是如此。

3. 该字符串来自第二格式，并且左侧的权重也是ODD，右侧的权重也是如此。

实例：

字符串 “[ABCDE] [XYZ]” 是平衡的，因为权重和左重量均为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 
} 

它检查字符串和其中的子字符串，然后打印每一个，如果他们如果它的平衡或不。
例如： 字符串“[[aa] [b]] [[[x] [yy]] [hhhhh]]”。
它打印此：
不平衡：2,1
不平衡：1,2
平衡：3,5
不平衡：3,8

我还可以创建其他功能，以帮助解决它（仅递归）。

编辑：（ANSWER）
谢谢你们了很好的解决方案，这是@科尔马的解决方案。

代码：（@科尔马的答案后，编辑对我的函数名）

#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

让我们忘记一段时间我们不能使用循环并尝试考虑解决它的算法。我们需要做的是在给定的字符串中为每个左括号找到匹配右括号的位置。该溶液变得几乎微不足道后：我们可以建立一个辅助功能，需要一个一个字符的阵列和两个指数：下限和上限并执行以下操作（它是一个伪代码）：

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

堆栈不需要任何循环的实现，所以这是它。

Answer 2

纯粹递归版本（使用辅助功能）。

的想法是找到其中左侧端部（使用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"); 
    } 
} 

Answer 3

单功能的解决方案：

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

Answer 4

我的解决方案基于匹配积分（权重）与target_score。评分函数是散列函数的非常简化版本。由于“平衡”长度为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