栈的应用:LeetCode第20题实现括号匹配
零 栈这种数据结构的应用
前面一讲，我们自己实现了一个支持动态扩展的顺序栈。其底层是一个动态数组。我们来看一下栈这种数据结构的具体应用场景：如何判定一个给定的字符串是否包含匹配的括号，对于包含“()”、”()[]{}”、”{[]}”，形式的字符串，我们认为其是一个有效的括号，成对出现。对于“(]”则认为其不是有效的括号对。具体见LeetCode第20题。
一 实现思路
对于一个给定的字符串，我们遍历它，如果它的字符是'(‘或'[‘或者是'{‘，则把它压入栈中存放，如果字符是’)’或者’]’或者是’}’，则将栈顶元素取出来，并判断其是否是'(‘或'[‘或者是'{‘，如果是的话，则栈顶元素出栈操作，然后继续遍历字符串，并重复上述操作。如果取出的栈顶元素和当前字符不是成对的括号的话，则说明字符串不是匹配的字符串。直到把整个字符串遍历完之后，如果栈不为空的话，则意味着字符串一定不是括号匹配的字符串。
二 代码实现
import java.util.Stack;
/**
* @Author:asher
* @Date:2021/4/6 10:28
* @Description:PACKAGE_NAME
* @Version:1.0
*/
public class Solution{
public boolean isValid(String s){
Stack<Character> arrayStack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
//逐个取出字符串中的字符，字符是'('或'['或者是'{'，则把它压入栈中存放
char c = s.charAt(i);
if (c == '[' || c == '(' || c == '{') {
arrayStack.push(c);
} else {
//否则，只要字符不是'('或'['或者是'{'的情况，则分两种情况，栈为空和不为空：
//如果栈此时为空，则不管取出的字符是什么，就一定不匹配
if (arrayStack.isEmpty()) {
return false;
//否则，如果栈不为空，则取出栈顶元素和当前字符进行配对
} else if (!arrayStack.isEmpty()) {
if (c == ']' && arrayStack.pop() != '[') {
return false;
} else if (c == ')' && arrayStack.pop() != '(') {
return false;
} else if (c == '}' && arrayStack.pop() != '{') {
return false;
}
}
}
}
//字符串中的所有字符都遍历结束之后，如果栈为空，则完全匹配成功，否则，栈中还有元素，则认为是不匹配
return arrayStack.isEmpty();
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "()";
System.out.println(solution.isValid(s));
}
}此时，我们就可以将上面的代码提交给LeetCode了，前面可以有引入Java基础类库中的类：import java.util.Stack;我们这里是用JDK自带的Stack类。并且，后面可以携带一个main方法一起提交。LeetCode在验证时，会忽略我们自己的main()，系统自动调用我们的Solution类，并实例化一个对象，然后跑系统设计的测试案例，如果全部通过，则提交成功。
三 LeetCode提交
当然，我们也可以使用我们前面自己写的那个用数组实现的支持动态扩展的栈，ArrayStack。如果使用我们自己实现的ArrayStack的话，则只需要把ArrayStack类，以及它依赖的我们自己动手实现的接口Stack、Array类，都放到Solution类中，定义成内部接口，内部类的形式，一并提交给LeetCode。
/**
* @Author:asher
* @Date:2021/4/7 09:52
* @Description:PACKAGE_NAME
* @Version:1.0
*/
public class Solution{
//定义栈的接口，然后用之前自己实现的动态数组Array来实现这个栈
private interface Stack<E> {
//入栈
void push(E e);
//出栈
E pop();
//查看栈顶元素
E peek();
//查看栈大小
int getSize();
//验证栈是否为空
boolean isEmpty();
}
private class Array<E > {
private E[] data;
private int size;
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
public Array() {
this(10);
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void addLast(E e) {
add(e, size);
}
public void add(E e, int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed.index is invalid");
}
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size; i>index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
public void addFirst(E e) {
add(e, 0);
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get failed.index is invalid");
}
return data[index];
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size - 1);
}
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
public E removeLast() {
return remove(size-1);
}
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove failed.index is invalid");
}
E temp = data[index];
for (int i = index; i+1 <size ; i++) {
data[i] = data[i + 1];
}
size--;
//如果数组实际存放元素个数变为总容量的一半儿，则进行缩容操作。
if (size == data.length / 2) {
resize(size);
}
return temp;
}
public E removeFirst() {
return remove(0);
}
public void modify(E e, E newValue) {
int temp = find(e);
if (temp != -1) {
data[temp] = newValue;
}
}
public void removeElement(E e) {
int temp = find(e);
if (temp != -1) {
remove(temp);
}
}
public void removeAllElement(E e) {
while (!isEmpty()) {
if (find(e) != -1) {
remove(find(e));
}
}
}
public void set(E e, int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("set failed.index is invalid");
}
data[index] = e;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Array size: %d ,length: %d\n", size, data.length));
for (int i = 0; i < size; i++) {
stringBuilder.append(data[i]);
if (i != size - 1) {
stringBuilder.append(" , ");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
private void resize(int capacity) {
E[] newData = (E[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
private class ArrayStack<E> implements Stack<E> {
private Array<E> array;
public ArrayStack(int capacity) {
array = new Array(capacity);
}
public ArrayStack() {
array = new Array();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public E peek() {
return array.getLast();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("Stack [");
for (int i = 0; i < array.getSize(); i++) {
stringBuilder.append(array.get(i));
if (i != getSize() - 1) {
stringBuilder.append(" , ");
}
}
stringBuilder.append("] top");
return stringBuilder.toString();
}
}
public boolean isValid(String s){
ArrayStack<Character> arrayStack = new ArrayStack<>();
for (int i = 0; i < s.length(); i++) {
//逐个取出字符串中的字符，字符是'('或'['或者是'{'，则把它压入栈中存放
char c = s.charAt(i);
if (c == '[' || c == '(' || c == '{') {
arrayStack.push(c);
} else {
//否则，只要字符不是'('或'['或者是'{'的情况，则分两种情况，栈为空和不为空：
//如果栈此时为空，则不管取出的字符是什么，就一定不匹配
if (arrayStack.isEmpty()) {
return false;
//否则，如果栈不为空，则取出栈顶元素和当前字符进行配对
} else if (!arrayStack.isEmpty()) {
if (c == ']' && arrayStack.pop() != '[') {
return false;
} else if (c == ')' && arrayStack.pop() != '(') {
return false;
} else if (c == '}' && arrayStack.pop() != '{') {
return false;
}
}
}
}
return arrayStack.isEmpty();
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "()";
System.out.println(solution.isValid(s));
}
}
一条评论
Pingback: