leetcode:Valid Parentheses(有效括号匹配)

Question：

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.

给定一个字符串仅仅包含这些字符'(', ')', '{', '}', '[' and ']'，判定输入的字符串是否是可匹配的，括号必须以正确的顺序打开关闭，比如"()" and "()[]{}" 。

算法思想：① 这个题首先会想到用栈进行存储操作，遇到左边的字符‘[’，'{'，‘（’则进栈，如果遇到相反字符在栈不为空的前提下出栈，并且判断读到的字符是否和出栈的字符匹配，匹配的话继续，否则直接结束。

　　　　　② 有一点儿在遍历输入字符时，如果栈为空了，表明肯定不能匹配。

　　　　　③ 如果输入的字符遍历完毕，但是栈不为空，表明‘[’，'{'，‘（这些字符多，也肯定不匹配。

代码设计：

 1 class Solution {
 2     public boolean isValid(String s) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         if(s.length()%2==1)
 5             return false;//如果是奇数，一定不匹配
 6         Stack<Character> stack=new Stack<Character>();
 7         Character temp=null;
 8         for(int i=0;i<s.length();i++){  
 9             if(s.charAt(i)=='{'||s.charAt(i)=='['||s.charAt(i)=='('){
10                 stack.push(s.charAt(i));//满足条件进栈
11             }
12             if(s.charAt(i)=='}'||s.charAt(i)==']'||s.charAt(i)==')'){
13                 if(!stack.isEmpty())
14                     temp=stack.pop(); //满足上述条件，出栈
15                 else
16                     return false;//循环还没结束 栈空了  一定不匹配
17                 if((temp=='{'&&s.charAt(i)=='}')||(temp=='('&&s.charAt(i)==')')||(temp=='['&&s.charAt(i)==']')){
18                     continue; //表示匹配，可以继续往下进行
19                 }
20                 else{
21                     return false;  //不匹配。直接结束
22                 }
23             }
24         }
25         if(stack.isEmpty())  //有可能字符串已经遍历结束，但是栈并不为空，这表示不匹配，如果匹配的话肯定是栈为空并且字符串遍历完毕
26             return true;
27         else
28             return false;
29     }
30 }

2013-10-2402:16:14