有效的括号 Posted on 2021-07-22 00:00:00 2021-07-22 00:00:00 by Author 摘要 给定一些只包含括号的字符串,你能判断给定字符串的左右括号是否相应的匹配吗????? # 有效的括号 > 写于2021/06/03 1. 题目描述 - 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: - 左括号必须用相同类型的右括号闭合。 - 左括号必须以正确的顺序闭合。 - 注意空字符串可被认为是有效字符串。 2. 示例描述 - 示例一 - 输入:"{()()}(){}[]" - 输出:true - 示例二 - 输入:"{{(()}}" - 输出:false - 示例三 - 输入: "([)]" - 输出:false 3. 解题思路 - 对于本题来说,学计算的铁子都知道这是一道经典的用栈来解决的题目。为什么会这么说,因为我们知道,在写代码或者写伪代码的时候`[]`,`()`,`{}`这三种括号必须是成对出现的,并且这三种括号可以随便嵌套,但是在嵌套的过程中必须保证有左括号,那么在相应的位置有右括号,不然代码就会 编译出错。那么我们换句话说左括号必须出现在右括号前面,并且左右括号在相对应的位置是匹配的。 - 同时,有些老铁会想这三种括号相互嵌套,我怎么找到左右括号相对于的位置尼。这不,栈就能够解决这个问题。 - 首先,我们应该知道栈的性质就是先进后出,那么当我们处理括号字符串的时候,当我们遇到左括号,我们就压入栈,当我们遇到右括号的时候,栈顶位置中存放离右括号最近的左括号,然后我们判断栈顶指针位置的左括号是否与当前的右括号是否匹配,如果不匹配,那么整个括号字符串都是有问题的。如果匹配的话,就可以弹出栈顶位置的左括号,继续进行下次操作。这里为什么要弹出栈顶位置的左括号尼,因为该位置的括号已经匹配完毕,左括号弹出栈,栈中存放左括号相应的位置,而右括号没进入栈中,左括号弹出栈,这就保证找到正确的左右括号对应的位置。同时为了后续遇到右括号时候,才能找到其相对应左括号的位置。而栈正好符合这个特点,所以用栈解决这个问题是在合适不过了。详细代码及解释见如下代码。 4. 代码实现 ```java boolean isValid(String str) { Stack<Character> st = new Stack<>(); char[] s = str.toCharArray(); for (int i = 0; i < str.length(); i++) { if (s[i] == '(') st.push(')'); else if (s[i] == '{') st.push('}'); else if (s[i] == '[') st.push(']'); // 第三种情况:遍历字符串匹配的过程中,栈已经为空了,没有匹配的字符了,说明右括号没有找到对应的左括号 return false // 第二种情况:遍历字符串匹配的过程中,发现栈里没有我们要匹配的字符。所以return false else if (st.empty() || st.peek() != s[i]) return false; else st.pop(); // st.top() 与 s[i]相等,栈弹出元素 } // 第一种情况:此时我们已经遍历完了字符串,但是栈不为空,说明有相应的左括号没有右括号来匹配,所以return false,否则就return true return st.empty(); } ```
{{ item.content }}
{{ child.content }}