目录
22. 有效的括号
思路
接口
数组实现类
有效的括号
力扣
直到有一天，我不会再问离开的人为什么
—— 24.9.28
22. 有效的括号
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
思路
将字符串中每一个符号存进栈中，每遇到一个左括号，就将一个与之对应的右括号放入栈顶位置，继续遍历，如果遇到了右括号，将右括号与栈顶元素进行对比，如果栈顶元素与遇到的右括号相等，证明是有效的括号，就将栈顶元素移除出来，使下一个字符继续与栈内元素进行相对比，最终如果栈为空，则代表字符串中括号匹配
接口
public interface Stack<E> {/*向栈顶压入元素Params：value-待压入值Returns：压入成功返回true，否则返回false*/boolean push(E vale);/*从栈顶弹出元素Returns：栈非空返回栈顶元素，栈为空返回null*/E pop();/*返回栈顶元素，不弹出Returns：栈非空返回栈顶元素，栈为空返回null*/E peek();/*判断栈是否为空Returns：空返回true，非空返回false*/boolean isEmpty();/*判断栈是否为满Returns:满返回true，空返回false*/boolean isFull();
}
数组实现类
import java.util.Iterator;public class ArrayStack<E> implements Stack<E>,Iterable<E> {private E[] array;// 栈顶指针private int top;@SuppressWarnings("all")public ArrayStack(int capacity) {this.array = (E[]) new Object[capacity];}/*向栈顶压入元素Params：value-待压入值Returns：压入成功返回true，否则返回false*/@Overridepublic boolean push(E value) {if(isFull()){return false;}array[top] = value;top++;return true;}/*从栈顶弹出元素Returns：栈非空返回栈顶元素，栈为空返回null*/@Overridepublic E pop() {if(isEmpty()){return null;}E e = array[top-1];top--;return e;}/*返回栈顶元素，不弹出Returns：栈非空返回栈顶元素，栈为空返回null*/@Overridepublic E peek() {if(isEmpty()){return null;}E e = array[top-1];return e;}/*判断栈是否为空Returns：空返回true，非空返回false*/@Overridepublic boolean isEmpty() {return top == 0;}/*判断栈是否为满Returns:满返回true，空返回false*/@Overridepublic boolean isFull() {return top == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p = top;@Overridepublic boolean hasNext() {return p > 0;}@Overridepublic E next() {E e = array[p-1];p--;return e;}};}
}
有效的括号
import java.util.ArrayList;public class LeetCode20EffectiveChar {public boolean isValid(String s) {ArrayStack<Character> stack = new ArrayStack<>(s.length());for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(') {stack.push(')');}else if (c == '[') {stack.push(']');}else if (c == '{') {stack.push('}');}else {if (!stack.isEmpty() && c == stack.peek()){stack.pop();}else {return false;}}}if (stack.isEmpty()){return true;}return false;}public static void main(String[] args) {LeetCode20EffectiveChar judge = new LeetCode20EffectiveChar();System.out.println(judge.isValid("([{}])"));System.out.println(judge.isValid("(){}[]"));System.out.println(judge.isValid("([])"));// 左右括号顺序不一致System.out.println(judge.isValid("([)]"));System.out.println(judge.isValid("([])"));// 左右括号顺序不一致System.out.println(judge.isValid("({[}])"));// 左右括号顺序不一致System.out.println(judge.isValid("({}[)]"));// 左右括号不一一对应System.out.println(judge.isValid("({[])"));System.out.println(judge.isValid("}])([{"));}
}
力扣
在力扣中提交要用栈的数据结构，不需要用我们自己实现的栈
Stack<Character> stack = new Stack<>();class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();char[] chars = s.toCharArray();//遍历所有的元素for (char c : chars) {//如果是左括号，就把他们对应的右括号压栈if (c == '(') {stack.push(')');} else if (c == '{') {stack.push('}');} else if (c == '[') {stack.push(']');} else if (stack.isEmpty() || stack.pop() != c) {//如果当前字符是右括号：//1.首先检查栈是否为空。如果为空，说明没有对应的左括号可以匹配，因此返回false。//2.如果栈不为空，尝试弹出栈顶元素。如果弹出的元素与当前的右括号不匹配，也返回false。return false;}}//最后如果栈为空，说明完全匹配，是有效的括号。//否则不完全匹配，就不是有效的括号return stack.isEmpty();}
} 
