［LeetCode］Valid Parentheses 验证括号是否有效闭合 ［LeetCode］Valid Parentheses 验证括号是否有效闭合
［LeetCode］Valid Parentheses 验证括号是否有效闭合 ［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 进行扩展，允许将向量视为堆栈。这个五个操作如下：
示例代码:
//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
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
腾讯云开发者
