利用栈解决括号匹配问题 -- 算法数据结构面试分享（三）

算法数据结构面试分享 符号匹配问题

今天在帖子上看见有同学在问，如果一个字符串中包含大括号和小括号，我们该如何解决括号匹配问题。我们今天就一起看下这道题吧。按照我们之前的套路，按部就班来：

1. 确保我们理解了问题，并且尝试一个例子，确认理解无误。

举个例子，这样的括号是匹配的， （）、{}、（{}）， ({()}(){}), 而类似于{（、{，（{）都是不匹配的。

2. 想想你可以用什么方法解决问题，你会选择哪一种，为什么？

我们拿这个字符串为例，({()}(){})， 最后一个）匹配的是第一个（， 倒数一个}匹配的是倒数第三个。所以我们可以从尾往头扫描，第一个）我们先记录下来，第一个}我们记录下来，第三个{我们发现它和}是匹配的，消除掉，第四个是），我们保存下来，第五个是（，我们发现和第四个匹配，消除掉，依次类推，到最后一个（，我们发现它还最开始的第一个匹配。所以我们自然想到了栈，不匹配我们就入栈，匹配我们就出栈。

3. 解释你的算法和实现的方法

我们申明两个栈，首先将所有字符依次入栈，再逐个出栈，出栈时，我们看下辅助栈里的第一个字符是否匹配，若匹配我们出栈，否则入栈。当主栈里所有字符都出栈时，我们检查辅助栈是否为空。空表示完全匹配，否则不匹配。

4. 写代码的时候，记住，一定要解释你现在在干什么

我们先来定义一个栈，一般我们会借助于数组，这里我们就简单的用列表来处理了，实现它的Pop， Push, IsEmpty 方法，看代码：

public class Mystack     {         private List list = new List();         public Mystack()         { }         public Mystack(T[] input)         {             if (input != null)             {                 for (int index = 0; index < input.Length; index++)                 {                     list.Add(input[index]);                 }             }         }         public T Pop()         {             if (!this.IsEmpty())             {                 T element = list[list.Count-1];                 list.RemoveAt(list.Count-1);                 return element;             }             throw new IndexOutOfRangeException("The stack is empty already.");         }         public void Push(T element)         {             list.Add(element);         }         public bool IsEmpty()         {             return this.list.Count == 0;         }     }  

接下来，我们看算法：

public static bool IsMatch(string input)        {            if (!string.IsNullOrEmpty(input))            {                Mystack stack = new Mystack(input.ToArray());                Mystack secondStack = new Mystack();                while (!stack.IsEmpty())                {                    char current = stack.Pop();                    if (secondStack.IsEmpty())                    {                        secondStack.Push(current);                    }                    else                    {                        char target = secondStack.Pop();                        if (!IsClosed(current, target))                        {                            secondStack.Push(target);                            secondStack.Push(current);                        }                    }                }                return secondStack.IsEmpty();            }            return false;        }  

这中间使用了一个IsClosed方法，我们用来匹配 （ 和 ）， { 和 }， 看代码：

private static bool IsClosed(char first, char second)   {       if (first == '(') return second == ')';       if (first == '{') return second == '}';       return false;   }    

最后我们一起来测试这个方法：

static void Main(string[] args)  {      string input = "({(){}})";      var result = IsMatch(input);      Console.WriteLine(result);  }  

欢迎大家关注我的公众号，还有我的专题系列：

• 视频教程,
• 数据结构与算法
• 经典算法面试题辅导
• 排序专题讲解
• 链表专题讲解。

大家有什么更好的解法，也欢迎讨论哈。