题目:给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。解题思路:想象一下你正在为你的大学课设编写一个小型编译器编译器的任务之一或称子任务将检测括号是否匹配。我们本文中看到的算法可用于处理编译器正在编译的程序中的所有括号并检查是否所有括号都已配对。这将检查给定的括号字符串是否有效是一个重要的编程问题。我们这个问题中将要处理的表达式可以包含以下三种不同类型的括号(){} 以及[]在查看如何检查由这些括号组成的给定表达式是否有效之前让我们看一下该问题的简化版本在简化后的问题中只含一种类型的括号。这么一来我们将会遇到的表达式是(((((()))))) – VALID()()()() – VALID(((((((() – INVALID((()(()))) – VALID上我们试着用一个简单的算法来解决这一问题。我们从表达式的左侧开始每次只处理一个括号。假设我们遇到一个开括号即 (表达式是否无效取决于在该表达式的其余部分的某处是否有相匹配的闭括号即 )。此时我们只是增加计数器的值保持跟踪现在为止开括号的数目。left 1如果我们遇到一个闭括号这可能意味着这样两种情况此闭括号没有与与之对应的开括号在这种情况下我们的表达式无效。当 left 0也就是没有未配对的左括号可用时就是这种情况。我们有一些未配对的开括号可以与该闭括号配对。当 left 0也就是有未配对的左括号可用时就是这种情况。如果我们在 left 0 时遇到一个闭括号例如 )那么当前的表达式无效。否则我们会减少 left 的值也就是减少了可用的未配对的左括号的数量。继续处理字符串直到处理完所有括号。如果最后我们仍然有未配对的左括号这意味着表达式无效。如果我们只是尝试对原始问题采用相同的办法这是根本就行不通的。基于简单计数器的方法能够在上面完美运行是因为所有括号都具有相同的类型。因此当我们遇到一个闭括号时我们只需要假设有一个对应匹配的开括号是可用的即假设 left 0。但是在我们的问题中如果我们遇到 ]我们真的不知道是否有相应的 [ 可用。你可能会问为什么不为不同类型的括号分别维护一个单独的计数器这可能不起作用因为括号的相对位置在这里也很重要。例如[{]如果我们只是在这里维持计数器那么只要我们遇到闭合方括号我们就会知道此处有一个可用的未配对的开口方括号。但是最近的未配对的开括号是一个花括号而不是一个方括号因此计数方法在这里被打破了。方法栈此外如果仔细查看上述结构颜色标识的单元格将标记开闭的括号对。整个表达式是有效的而它的子表达式本身也是有效的。这为问题提供了一种递归结构。例如考虑上图中两个绿色括号内的表达式。开括号位于索引 1相应闭括号位于索引 6。如果每当我们在表达式中遇到一对匹配的括号时我们只是从表达式中删除它会发生什么在表示问题的递归结构时栈数据结构可以派上用场。我们无法真正地从内到外处理这个问题因为我们对整体结构一无所知。但是栈可以帮助我们递归地处理这种情况即从外部到内部。让我们看看使用栈作为该问题的中间数据结构的算法。算法初始化栈 S。一次处理表达式的每个括号。如果遇到开括号我们只需将其推到栈上即可。这意味着我们将稍后处理它让我们简单地转到前面的 子表达式。如果我们遇到一个闭括号那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号那么我们将它从栈中弹出并继续处理。否则这意味着表达式无效。如果到最后我们剩下的栈中仍然有元素那么这意味着表达式无效。我们来看一下该算法的动画演示然后转到实现部分。代码实例:public class program2test { // Hash table that takes care of the mappings. private HashMapCharacter, Character mappings; // Initialize hash map with mappings. This simply makes the code easier to // read. public program2test() { this.mappings new HashMapCharacter, Character(); this.mappings.put(), (); this.mappings.put(}, {); this.mappings.put(], [); } public boolean isValid(String s) { // Initialize a stack to be used in the algorithm. StackCharacter stack new StackCharacter(); 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 doesnt match the stacks top // element, return false. //this.mappings.get(c)是获取c键的值 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(); } public static void main(String[] args) { program2test n new program2test(); String s {{{}}}; System.out.println(n.isValid(s)); } }文章内容参考https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode/
