数据结构--Java语言实现有效的括号

目录

1 题目描述

2 解题思路

3 代码实现

---

1 题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

2 解题思路

栈：里面存放左括号，当有右括号出现时，将栈顶元素出栈，进行匹配即可。共有四种情况：

栈中为空，右括号无法进行匹配左右括号不匹配栈中元素剩余(左括号个数多于右括号)左右括号 

具体如下：

将字符串转化成字符数组，遍历字符数组，如果遇到左括号，则将该左括号入栈，{如果遇到的第一个元素为右括号，则不匹配；否则进行比较，若两者匹配，则将栈内元素出栈；否则{不匹配；}}最后遍历完字符数组，若栈为空，则说明所有括号匹配成功，否则匹配不成功。

3 代码实现

实现一：自定义栈

class Solution { public boolean isValid(String s) { char[] stack = new char[s.length()]; int top = 0; for(int i = 0;i < s.length();i++){ if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){ stack[top++] = s.charAt(i); }else{ //是右括号 if(top == 0){ //右括号多 return false; }else{ //栈顶元素和右括号进行比较 char t = stack[top - 1]; if((t == '('&&s.charAt(i)==')')||(t == '{'&&s.charAt(i)=='}')||(t == '['&&s.charAt(i)==']')){ //进行出栈操作 --top; }else{ //不匹配 return false; } } } } if(top > 0){ //左括号多 return false; } return true; } }

实现二：使用栈集合

class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0;i < s.length();i++){ if (s.charAt(i) == '('||s.charAt(i) == '{'||s.charAt(i) == '['){ stack.push(s.charAt(i)); }else { if (stack.empty()){ return false; }else { if (stack.peek() == '('&&s.charAt(i) == ')'||stack.peek() == '{' &&s.charAt(i) == '}'||stack.peek() == '['&&s.charAt(i) == ']'){ stack.pop(); }else { return false; } } } } if (!stack.empty()){ return false; } return true; } }