[Leetcode]Valid Parentheses

题目: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.

题目很简单,判断字符串是否合法,判断规则是看括号是否一一对应匹配。我开始的思路大概如下,如果进来的是([{这三个中的一个,存着。如果是)]}这三个的一个,就看存着的那些里面的上一个是不是与之对应的([{中的一个。想到这里,数据结构基本也出来了,那就是利用最基本的栈结构,就可以解决这个问题啦(之前还想过用数组通过下标来做,发现太麻烦,果断用现成的数据结构来解决),如果有对应匹配的,出栈,没有 压栈,最后判断栈是否为空就行啦~。

上代码:

import java.util.*;

/**
 * @author Snake
 *Valid Parentheses                 
 */

public class Test {
	/**
	 * 
	 * @param args
	 */
	public static void main(String []args){
		boolean flag = isValid("[{}]()]]");
		System.out.println(flag);
	}
	
	/**
	 * @param s String
	 * @return 判断是否合法
	 */
	public static boolean isValid(String s) {
		
        char []array = s.toCharArray();
        boolean flag = true;
        Stack<Character> stack = new Stack<Character>();//栈结构
        
        for (int i = 0; i < array.length; i++) {
        	//如果是右括号,压栈 ,调用push方法
        	if((array[i] == '{')
                 ||(array[i] == '[')
                 ||(array[i] == '(')){
        		stack.push(array[i]);
        	//如果是左括号,判断栈顶是不是对应的右括号,如果不是 直接false
        	}else if ((array[i] == '}')
                        ||(array[i] == ']')
                        ||(array[i] == ')')) {
        		if (stack.empty()) {
					flag = false;
					break;
				}
				if (array[i] == '}') {
					if(stack.pop() != '{'){
						flag = false;
						break;
					}
				}else if (array[i] == ')') {
					if(stack.pop() != '('){
						flag = false;
						break;
					}
				}else if (array[i] == ']') {
					if(stack.pop() != '['){
						flag = false;
						break;
					}
				}
			}
		}
        if(!stack.empty())
        	flag = false;
        return flag;
    }
	
}

还是比较简单的,考虑如果符号多的话,可以另外存map之类的类型,这样就不用写那么多if判断了。

(完)

——Snake

snake

作者: snake

我们需要为这个社会做一点贡献,失去了才懂得去珍惜。

发表评论

电子邮件地址不会被公开。 必填项已用*标注