遞歸函數檢查字符串是否「平衡」

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