平衡括号问题的优化解 [英] Optimized solution for Balanced Parentheses Problem

问题描述

给定一个只包含字符 '(', ')', '{', '}'、'[' 和 ']'，判断输入的字符串是否有效.

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

输入字符串在以下情况下有效:

An input string is valid if:

1. 左括号必须由相同类型的括号封闭.
2. 左括号必须以正确的顺序关闭.
3. 请注意，空字符串也被视为有效.

示例 1:

Input: "()[]{}"
Output: true
Example 2:

示例 2:

Input: "{[(])}"
Output: false

我对上述问题的解决方案是:

My solution for the above problem is:

static boolean isPair(char left,char right){
        return left=='{' && right=='}' || left=='(' && right==')' || left=='[' && right==']'; 
    }
    public boolean isValid(String s) {
        Stack<Character> stack= new Stack<>();
        for(char ch: s.toCharArray()){
            if(ch=='(' || ch=='{' || ch=='['){
                stack.push(ch);
            }
            else{
                if(!stack.isEmpty() && isPair(stack.peek(),ch))
                    stack.pop();
                else
                    return false;
            }
        }
        return stack.isEmpty();
}

我在某处找到了一个更聪明的解决方案，但无法理解.代码如下:

I have found a much smarter solution somewhere but unable to understand it. Here's the code:

public boolean isValid(String s) {
        Stack<Character> stack= new Stack<>();
        for(char ch: s.toCharArray()){
            if(ch=='(')
                stack.push(')');
            else if(ch=='{')
                stack.push('}');
            else if(ch=='[')
                stack.push(']');
            else if(stack.isEmpty() || stack.pop()!=ch)
                return false;
        }
        return stack.isEmpty();
}

请帮助我理解最后一个 else-if 块的工作.

Please help me to understand the working of last else-if block.

推荐答案

您已为所有 左括号 推送了 右括号.因此，当关闭括号来时，它将匹配堆栈顶部的字符.如果它不匹配或堆栈变空.这意味着不平衡.

You have pushed the closing bracket for all the opening brackets. So, that when closing brackets come, then it will match the character at the top of stack. If it doesn't match or stack becomes empty. That means unbalanced.

else if(stack.isEmpty() || stack.pop()!=ch)
    return false;

当您到达这里时，您有一个 括号 作为 ch 但堆栈为空或堆栈中的值与传入字符不匹配.

When you reach here, you have a bracket as ch but the stack is empty or the value from the stack doesn't match the incoming character.

所以，括号不平衡.

这篇关于平衡括号问题的优化解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！