[LeetCode]Valid Parentheses 验证括号是否有效闭合

链接https://leetcode.com/problems/valid-parentheses/#/description

难度:Easy

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

翻译:给定一个仅包含字符’(’,’)’,’{‘,’}’,’[‘和’]’的字符串,确定输入字符串是否有效。括号必须以正确的顺序关闭,“()”和“()[] {}”都是有效的,但“(]”和“([)]”不是。

思路:用数据结构——栈就可以实现。遍历字符串,把左括号压栈,碰到右括号就把栈的顶部元素拿出来与右括号匹配,匹配成功则顶部元素出栈,进入下一次循环,匹配不成功或者栈中无元素,则字符串不是有效闭合。直到所有元素遍历完,栈中无元素,即为有效闭合;如果所有元素遍历完了,栈中还有元素,则不是有效闭合。

基础概念

在 Java 中 Stack 类表示后进先出(LIFO)的对象堆栈。栈是一种非常常见的数据结构,它采用典型的先进后出的操作方式完成的。每一个栈都包含一个栈顶,每次出栈是将栈顶的数据取出,如下:

Stack 通过五个操作对 Vector 进行扩展,允许将向量视为堆栈。这个五个操作如下:

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//Create the Stack instance and add a couple of elements to it
Stack stack = new Stack();
String s1 = "element 1";
String s2 = "element 2";
stack.push(s1);
stack.push(s2);
System.out.println(stack.peek());
//element 2
//Find position of a certain element
int pos = stack.search("element 1");
System.out.println(pos);
//2
System.out.println(stack.pop());
System.out.println(stack.pop());
//element 2
//element 1
System.out.println(stack.empty());
//true

参考代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean isValid(String s) {
if(s==null || s.length()==0)
return false;
Stack<Character> parentheses = new Stack<Character>();
for (int i = 0; i< s.length(); i++){
char c = s.charAt(i);
if(c=='(' || c=='[' || c =='{')
parentheses.push(c);
else{
if (parentheses.empty())
return false;
if (c == ')' && parentheses.peek() != '(')
return false;
if (c == ']' && parentheses.peek() !='[')
return false;
if (c == '}' && parentheses.peek() !='{')
return false;
parentheses.pop();
}
}
return parentheses.empty();
}
}

参考资料

http://outofmemory.cn/code-snippet/2087/java-usage-Stack-class