我在阅读平衡括号挑战错了吗？

Question

我正在做平衡括号问题(https://www.hackerrank.com/challenges/balanced-brackets),我无法弄清楚我哪里出错了.

例如

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

- >

YES
NO
YES

我认为这将是一个直截了当的事实,该字符串包含平衡括号,当且仅当对于每一s[i],s[n-i-1]对它是真的s[i]是一个右向括号并且s[n-i-1]是相应的左向括号.

因此我的解决方案

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

由于某种原因失败了.

Answer 1

典型的实现基于堆栈:

• 推动任何开口 [,{,(支架固定到堆
• 在闭幕 ],},)支架,试图弹出顶部的项目,并检查它是否对应于当前右括号:(对)等.返回false如果堆栈是空的或有没有对应.
• 最后,在处理完最后一个字符后,堆栈应该为空.

执行:

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. "(()"
}