乘风破浪：LeetCode真题_020_Valid Parentheses
一、前言
下面开始堆栈方面的问题了，堆栈的操作基本上有压栈，出栈，判断栈空等等，虽然很简单，但是非常有意义。
二、Valid Parentheses
2.1 问题
2.2 分析与解决
我们可以看到通过堆栈，先压进符号的左半部分，然后如果下次直接是该符号的右半部分，那就弹出左半部分，否则继续压入符号的左半部分，如果此时是其他符号的右半部分，那就是错误了。每一次当形成一个整体的时候都会被弹出去，这样就能直接判断了。
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// If the current character is a closing bracket.
if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false.
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
}
}
上面的代码已经很清晰了，当然我们也可以这样表述：
import java.util.Deque;
import java.util.LinkedList; public class Solution {
/**
*
* 题目大意
* 给定一个只包含(‘, ‘)’, ‘{‘, ‘}’, ‘[’ 和‘]’的字符串，验证它是否是有效的。
* 括号必须配对，并且要以正确的顺序。
*
* 解题思路
* 用一个栈来对输入的括号串进行处理，如果是左括号就入栈，如果是右括号就与栈顶元素看是否组成一对括号，
* 组成就弹出，并且处理下一个输入的括号，如果不匹配就直接返回结果。
*/
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();
int index = 0;
Character top;
while (index < s.length()) {
Character c = s.charAt(index);
switch (c) {
case '(':
case '[':
case '{':
stack.addFirst(c);
break;
case ')': if (stack.isEmpty()) {
return false;
} top = stack.getFirst();
if (top == '(') {
stack.removeFirst();
} else if (top == '[' || top == '{') {
return false;
} else {
stack.addFirst(c);
}
break;
case ']': if (stack.isEmpty()) {
return false;
} top = stack.getFirst();
if (top == '[') {
stack.removeFirst();
} else if (top == '(' || top == '{') {
return false;
} else {
stack.addFirst(c);
}
break;
case '}': if (stack.isEmpty()) {
return false;
} top = stack.getFirst();
if (top == '{') {
stack.removeFirst();
} else if (top == '[' || top == '(') {
return false;
} else {
stack.addFirst(c);
}
break;
default:
return false;
} index++;
} return stack.isEmpty();
}
}
三、总结
通过对堆栈的练习，我们复习了一些基础知识，同时对于这些涉及表达式的运算，类似于树的遍历，我们都要想到堆栈来解决。