括号匹配问题

这个问题的描述很简单，就是若括号匹配则返回true，否则返回false。

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

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

这个问题中的括号必须是对称的，否则不可能匹配，由于对称点很可能有多个，无法使用两个指针进行标记，很自然地联想到需要使用栈来解决。

我的算法思路就是遇到 ' ( ' , ' [ ' , ' { '便push进栈，遇到 ' ) ' , ' ] ' , ' } '便通过peek()函数看是否与栈顶匹配，若匹配则将栈顶pop掉，否则返回false

public class Solution {
     public static boolean isValid(String s) {
         if(s.length()%2!=0)
             return false;
         Stack<Character> stack=new Stack<Character>();
         for(int i=0;i<s.length();i++)
         {
             if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{')
                 stack.push(s.charAt(i));
             else switch(s.charAt(i))
             {
             case ')':
                 if(stack.size()!=0&&stack.peek()=='(')
                       stack.pop();
                 else return false;
                 break;
             case ']':
                 if(stack.size()!=0&&stack.peek()=='[')
                       stack.pop();
                 else return false;
                 break;
             case '}':
                 if(stack.size()!=0&&stack.peek()=='{')
                       stack.pop();
                 else return false;
                 break;
             }
         }
        if(stack.size()==0)
            return true;
        else 
            return false;
        }
}

leetcode上的高票答案思路与上面大致相同，但是更优雅，思路更简洁。
体现在
1.遍历String时使用for(char c:s.toCharArray())
2.直接在栈中存储' ( ',' [ ',' { '相对应匹配的括号，而不储存' ( ',' [ ',' { '，这样在对栈进行peek()的时候可以直接与charAt(i)进行比较，而无需再进行转换来看是否匹配。使代码更简洁优雅。

不过个人感觉在前面加上

if(s.length()%2!=0)
     return false;

可以更有效避免不必要的计算。
leecode高票答案如下

    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}