括号匹配问题（Valid Parentheses）

@(leetcode)[Valid Parentheses]

题记：从今天开始每天一道leetcode上的题，每天一篇博客

leetcode

leetcode是国外的一个OJ网站，到目前为止总共有158到题，这些题目包含了数据结构的很多知识，做一做不仅能提高自己的编码能力，数据结构方面的知识也能学到不少。

所有的这158道题在网上都能找到答案，把这些题刷完的人也不少。那我为什么还有每天刷一题，每天一篇博客呢？我的想法很简答，别人的答案是别人的知识，纸上得来终觉浅，绝知此事要躬行，自己做一遍之后才能知道自己有几斤几两。

另外一个原因就是把刷过的题记在博客中，也算是一个笔记吧。

PS:欢迎志同道合的小伙伴来一起刷题，一起学习，共同进步。

我用的编程语言：Java

Update:2014/11/26 博客园对Markdown的支持不好，如果每天在这里写博客，排版都要花掉不少时间。算了，我还是马克飞象+ Evernote吧，排版好看，还方便。每天一篇博客的话是不能兑现了，不过每天一道题没有问题！

题目描述

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.

Total Accepted: 25934 Total Submissions: 92373

class: Easy

分析

这道题让我们完成括号是否正确匹配的功能，这个功能在编译原理等课程中需要经常用到。

要实现这个功能，说简单也简单，说难也难，关键是看你有没有用对数据结构。用什么结构好呢？对了，就是我们经常用到的栈结构。实际上，在现有的语法分析器中，这个功能都是用栈来实现的。

伪代码

输入：括号字符串，仅仅包含 (]} 这三种括号。
输入：输入的括号字符串是不是合法的，合法的输出true，不合法输出false。

字符指针i = 0
根据字符指针取出括号字符串的当前字符，如果当前字符为空，跳到5
如果当前字符是左括号( (]}这三种 )，直接压入栈
如果当前字符是右括号( )]}这三种 )，从栈中弹出一个元素，弹出的元素如果和当前字符匹配，i++，回到2；否则，返回false
如果栈为空，返回true；否则返回false

复杂度分析

很容易看出来括号字符串的每个字符都只需要考虑一遍，时间复杂度是O(n)

源代码

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
    	//1代表( 2代表[ 3代表{ 4代表) 5代表] 6代表}
    	//第一种边界情况
    	if(s.length() == 0)
    		return true;
        Stack<Integer> stack = new Stack<Integer>();
        char c;
        int temp;
        for(int i = 0; i < s.length(); i++) {
        	c = s.charAt(i);
        	if(c == '(') stack.add(1);
        	else if(c == '[') stack.add(2);
        	else if(c == '{') stack.add(3);
        	else {
        		//第二种边界情况
        		if(stack.empty())
        			return false;
        		if(c == ')') temp = 4;
        		else if(c == ']') temp = 5;
        		else temp = 6;
        		if(stack.peek() != temp - 3)
        			return false;
        		else stack.pop();
        	}
        }
        if(stack.isEmpty()) return true;
        else return false;
    }
    
    public static void main(String[] args) {
    	ValidParentheses vp = new ValidParentheses();
    	String test = "][";
    	System.out.print(vp.isValid(test));
    }
}

别人是怎么做的

        if s == "":
            return True
        if len(s) % 2 == 1:
            return False

        else:
            while(  "()" in s or "[]" in s or "{}" in s):
                s = s.replace("()", "")
                s = s.replace("[]", "")
                s = s.replace("{}", "")
                return self.isValid(s)
            return False

上面的代码用Python写的，虽然递归效率不高，但是很简洁，也很好懂