java - 平衡括号问题的优化解

Question

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

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

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

示例1:

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

示例2:

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

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

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();
}

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

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 block 的工作原理。

Answer 1

您已为所有左括号按下了右括号。因此，当右括号出现时，它将匹配堆栈顶部的字符。如果不匹配或者堆栈变空。这意味着不平衡。

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

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

因此，括号不平衡。