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.

解决思路：

建个数组，将左半边括号入数组，如果遇到右半边括号，查看是否和数组的最后一个匹配，如果匹配，就继续读下一个；如果不匹配，则说明这个字符串不合法。注意处理只有右半边括号的字符串！

因为最近需要练习java，所以这道题我用java实现。

代码：

package leetcode;
import java.util.*;
public class ValidParentheses {

	/**
	 * author:liufan
	 * 思想：用栈的思想。建个数组，将左半边括号入数组，如果遇到右半边括号，查看是否和数组的最后一个匹配，如果匹配，就继续读下一个；
	 * 如果不匹配，则说明这个字符串不合法。注意处理一开始就是右半边括号的字符串！
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s="";
		System.out.print("输入字符串:");
		Scanner in=new Scanner(System.in);
		s=in.next();	//输入字符串
		boolean result=isValid1(s);
		System.out.print(result);
	}
	public static  boolean isValid1(String s){
		char[] str = s.toCharArray();
		char[] stack = new char[s.length()];
		int stack_end=-1,length=s.length();
		int i=0,j=0;
		for(i=0;i<length;i++){
			if(str[i]=='(' || str[i]=='[' || str[i]=='{'){	//如果是括号的左半边，入数组
				stack_end++;
				stack[stack_end]=str[i];
			}
			else if((str[i]==']' || str[i]==')' || str[i]=='}') && stack_end==-1){	//如果一开始就是右半边
				return false;
			}
			else {	//是括号右半边，判断数组内最后一个是否对应左半边
				if(str[i]==')' && stack[stack_end]=='('){	//是对应左半边
					stack_end--;
				}
				else if(str[i]==']' && stack[stack_end]=='['){	//是对应左半边
					stack_end--;
				}
				else if(str[i]=='}' && stack[stack_end]=='{'){	//是对应左半边
					stack_end--;
				}
				else{	//不是对应左半边
					return false;
				}
			}
		}
		if(stack_end!=-1){	//如果所有的判断完，数组里还有剩余，说明没有匹配完，则字符串无效
			return false;
		}
		else
			return true;
	}
}