Description：　

　　Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.

Example:

　　The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

思路分析：

　　1.这个问题不仅仅是要求 ‘（’字符  与  ‘）’字符 需要成对出现，而且要求“开闭”紧凑，所以来回遍历逐个查找匹配肯定不行；

　　2.分析问题的特征，最主要的就是合法的输入是很规范的“有开有闭”类型，即能够通过在字符间插入特定数目的竖线，使得整个字符串各个局部都对称，对‘栈’敏感一点的其实能够慢慢联想到这一数据结构，一进一出、两进两出...其实都展示着一种对称；

　　3.因此，合法的输入一定可以通过‘栈’这一数据结构的pop，push操作完成一个个完整的进出过程。

代码思路：

　　step1：初始化栈，并入栈输入串的第一个字符；

　　step2:  从输入串的第二个字符到最后一个字符，依次与栈顶元素对比，栈不为空且栈顶元素与字符匹配则出栈，否则入栈该字符；

　　Step3:  操作完最后一个字符后，如果栈为空（即有进必有出，各个局部均对称），则输入合法；

C#代码：

 1 public class Solution { 2     public bool IsValid(string s) { 3         //step1 4         Stack<char> stk = new Stack<char>(); 5         char[] sArr = s.ToCharArray(); 6         stk.Push(sArr[0]); 7         for(int i = 1;i<s.Length;i++){ 8             //step2 9             if(stk.Count!=0&&IsMatch(stk.Peek(),sArr[i])){10                 stk.Pop();11             }else{12                 stk.Push(sArr[i]);13             }14         }15         //step316         return stk.Count==0;17     }18     public bool IsMatch(char a,char b){19         if((a==‘(‘&&b==‘)‘)||(a==‘[‘&&b==‘]‘)||(a==‘{‘&&b==‘}‘)) return true;20         return false;21     }22 }    

20. Valid Parentheses - 括号匹配验证