Recursive Function that checks if a string is "Balanced"

Question

I have a question where I have to write an algorithm using recursion only (Must not use Loops).
The question says that my function should check if a given string is "Balanced" or not.
The string only contains letters (no symbols) and only ("[" , "]") those brackets.
(For example: "[aa][abbsa]").

Assume that every "opening bracket" ("[") has a closing one ("]"), in other words, the brackets in the string are balanced and there's no need to check that.
The string is always one of these two formats:

1. Simple String: CHARACTERS.

it only contains characters with no brackets. (Example: "aaabbcc").

2. String with 2 Sub-Strings:

[LEFT][RIGHT]

LEFT : Itself is a Sub-string that can actually be on of the two formats (Simple String OR String with 2 Sub-Strings)

RIGHT : Itself is a Sub-string that can actually be on of the two formats (Simple String OR String with 2 Sub-Strings)

EDIT: The string is Valid, there's no need to check if it's legal or not. it's always one of the mentioned formats and examples (might be more complicated too, but it's always legal).

EDIT: The String can only be in the 1st format, or the 2nd format. if it's the 2nd format, then it includes the 1st format, and it must start with "[" and end with "]".
Examples: "aaabbbb" (1st format). "[aa][bbbb]" (2nd format). "[[aa][b]][[[a][bbb]][aaaa]]" (2nd format).

The string is Balanced if it fulfills at least one of the following conditions:

1. The string is from the 1st Format.

2. The string is from the 2nd Format and also the number of the characters (without the brackets) in the LEFT side (lets call it weight) is EVEN, and so is the weight in the RIGHT side.

3. The string is from the 2nd Format and also the weight in the LEFT side is ODD and so is the weight in the Right side.

Examples:

The string "[abcde][xyz]" is Balanced, because the Right weight and the Left weight are both ODD.

The string "[abcde][xyzw]" Isn't Balanced, because the Right Weight is EVEN (4 is even) and the Left Weight is ODD (5 is odd).

The string "[abcdef][[x][yzw]]" is Balanced.
The Left weight is 6.
The Sub-String "[x][yzw]" is Balanced. (Left weight is 1, Right weight is 3 (Both ODD)).
The weight of "[x][yzw]" is 4. Therefore, "[abcdef][[x][yzw]]" is Balanced, since both of the Left and Right weight are EVEN.

"[[abcde][xyzw]][Z]" is Balanced, even though the Sub-String "[abcde][xyzw]" isn't Balanced! because its weight is 9, and "[Z]" weighs 1, They're both ODD.

So, I have to write a recursive function in C, that receives a "string".

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

it checks the string and the Sub-strings in it and then prints each one if them if its balanced or not.
for example: string "[[aa][b]][[[x][yy]][hhhhh]]".
it prints this:
imbalanced: 2,1
imbalanced: 1,2
balanced: 3,5
imbalanced: 3,8

I'm also allowed to create another functions to help with solving it (recursive only).

EDIT: (ANSWER)
Thank you guys for the nice solutions, This is @kolmar's solution.

Code: (edited after @kolmar's Answer for function names of mine)

#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;
}

Sorry for this long question, but I really need help with it, I spent a lot of time trying to solve it but i couldn't. Thank you for your time and help!

Answer 1

Purely recursive version (using auxiliary functions).

The idea is to find where the left side ends (using left_side), then count the number of non-bracket chars in each side (using 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");
    }
}