Am I reading Balanced Brackets?

Question

I am making a problem with symmetric brackets ( https://www.hackerrank.com/challenges/balanced-brackets ) and I cannot figure out where I am going wrong.

eg.

3
{[()]}
{[(])}
{{[[(())]]}}

->

YES
NO
YES

I thought it would be a straightforward fact that a line contains balanced brackets if and only if for each pair it s[i],s[n-i-1]is true that it s[i]is a right-angled bracket and s[n-i-1]the corresponding left side is a bracket.

Hence my decision

static readonly Dictionary<char,char> brackets = new Dictionary<char,char>() 
{
    { '{', '}' },
    { '[', ']' },
    { '(', ')' }
};

static bool IsBalanced(string str)
{
    for(int i = 0, j = str.Length - 1; i < j; ++i, --j)
        if(!brackets.ContainsKey(str[i]) || brackets[str[i]] != str[j])
            return false;
    return true;
}

which for some reason fails.

Answer 1

A typical implementation is based on the stack:

• [, {, (
• ], }, ) , , : ( ) .. return false if .
• , .

:

private static Dictionary<char, char> openByClose = new Dictionary<char, char>() {
  { '}', '{' }, 
  { ']', '[' }, 
  { ')', '(' },
};

private static bool IsBalanced(string source) {
  if (string.IsNullOrEmpty(source))
    return true;

  Stack<char> brackets = new Stack<char>();

  foreach (char ch in source) {
    char open;

    if (openByClose.Values.Contains(ch)) // ch is an opening bracket
      brackets.Push(ch);
    else if (openByClose.TryGetValue(ch, out open)) // ch is a closing bracket
      if (!brackets.Any())
        return false; // too many closing brackets, e.g. "())"
      else if (brackets.Pop() != open)
        return false; // brackets don't correspond, e.g. "(]"
  }

  return !brackets.Any(); // too many opening brackets, e.g. "(()"
}

Answer 2

?

str = "()()".

.
isBalanced(l, r) str[l] + str[l+1] + ... + str[r-1] , (++) isBalanced(0, str.Length).

bool isBalanced(int l, int r) {
    if(l == r) return true;
    int depth = 0, prevptr = l;
    for(int i = l; i < r; i++) {
        if(str[i] == '(' || str[i] == '{' || str[i] == '[') depth++;
        else depth--;
        if(i != r - 1 && depth == 0) {
            if(!isBalanced(prevptr, i + 1)) return false;
            prevptr = i + 1;
        }
    }
    if(depth != 0) return false;
    if(prevptr != l) {
        if(!isBalanced(prevptr, r)) return false;
        return true;
    }
    bool ok = false;
    if(str[l] == '(' && str[r - 1] == ')') ok = true;
    if(str[l] == '{' && str[r - 1] == '}') ok = true;
    if(str[l] == '[' && str[r - 1] == ']') ok = true;
    if(!ok || !isBalanced(l + 1, r - 1)) return false;
    return true;
}

, # -, # - ++-, ++ ( ++-)