利用棧解決括號(hào)匹配問題 -- 算法數(shù)據(jù)結(jié)構(gòu)面試分享（三）

算法數(shù)據(jù)結(jié)構(gòu)面試分享 符號(hào)匹配問題

今天在帖子上看見有同學(xué)在問，如果一個(gè)字符串中包含大括號(hào)和小括號(hào)，我們?cè)撊绾谓鉀Q括號(hào)匹配問題。我們今天就一起看下這道題吧。按照我們之前的套路，按部就班來：

1. 確保我們理解了問題，并且嘗試一個(gè)例子，確認(rèn)理解無誤。

舉個(gè)例子，這樣的括號(hào)是匹配的， （）、{}、（{}）， ({()}(){}), 而類似于{（、{，（{）都是不匹配的。

2. 想想你可以用什么方法解決問題，你會(huì)選擇哪一種，為什么？

我們拿這個(gè)字符串為例，({()}(){})， 最后一個(gè)）匹配的是第一個(gè)（， 倒數(shù)一個(gè)}匹配的是倒數(shù)第三個(gè)。所以我們可以從尾往頭掃描，第一個(gè)）我們先記錄下來，第一個(gè)}我們記錄下來，第三個(gè){我們發(fā)現(xiàn)它和}是匹配的，消除掉，第四個(gè)是），我們保存下來，第五個(gè)是（，我們發(fā)現(xiàn)和第四個(gè)匹配，消除掉，依次類推，到最后一個(gè)（，我們發(fā)現(xiàn)它還最開始的第一個(gè)匹配。所以我們自然想到了棧，不匹配我們就入棧，匹配我們就出棧。

3. 解釋你的算法和實(shí)現(xiàn)的方法

我們申明兩個(gè)棧，首先將所有字符依次入棧，再逐個(gè)出棧，出棧時(shí)，我們看下輔助棧里的第一個(gè)字符是否匹配，若匹配我們出棧，否則入棧。當(dāng)主棧里所有字符都出棧時(shí)，我們檢查輔助棧是否為空?？毡硎就耆ヅ?，否則不匹配。

4. 寫代碼的時(shí)候，記住，一定要解釋你現(xiàn)在在干什么

我們先來定義一個(gè)棧，一般我們會(huì)借助于數(shù)組，這里我們就簡(jiǎn)單的用列表來處理了，實(shí)現(xiàn)它的Pop， Push, IsEmpty 方法，看代碼：

public class Mystack<T>  
   {  
       private List<T> list = new List<T>();  

       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<char> stack = new Mystack<char>(input.ToArray());  

              Mystack<char> secondStack = new Mystack<char>();  

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

這中間使用了一個(gè)IsClosed方法，我們用來匹配 （ 和 ）， { 和 }， 看代碼：

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

     if (first == '{') return second == '}';  

     return false;  
 }    

最后我們一起來測(cè)試這個(gè)方法：

static void Main(string[] args)  
{  
    string input = "({(){}})";  

    var result = IsMatch(input);  

    Console.WriteLine(result);  
}  

歡迎大家關(guān)注我的公眾號(hào)，還有我的專題系列：

• 視頻教程,
• 數(shù)據(jù)結(jié)構(gòu)與算法
• 經(jīng)典算法面試題輔導(dǎo)
• 排序?qū)ｎ}講解
• 鏈表專題講解。

大家有什么更好的解法，也歡迎討論哈。