C# 有效括号LeetCode解法中Stack未全调用Pop却最终为空的原因咨询

解法代码 #

bool testen(string s)
{
    // 初始化栈，存储待匹配的右括号
    var k = new Stack<char>();
    // 遍历字符串的每个字符
    foreach (char c in s)
    {
        // 遇到左小括号，压入对应的右小括号，跳过后续判断
        if (c == '(') { k.Push(')'); continue; }
        // 遇到左花括号，压入对应的右花括号，跳过后续判断
        if (c == '{') { k.Push('}'); continue; }
        // 遇到左中括号，压入对应的右中括号，跳过后续判断
        if (c == '[') { k.Push(']'); continue; }
        // 遇到右括号时，栈为空无匹配项，或当前右括号和栈顶待匹配的右括号不一致，直接返回不合法
        if (k.Count == 0 || c != k.Pop()) return false;
    }
    // 栈为空说明所有左括号都匹配到了对应的右括号，否则存在未匹配的左括号
    return k.Count == 0;
}

核心原理解答 #

你提到的「遍历结束后栈为空」的情况，只会出现在输入的括号字符串完全合法的场景下，逻辑推导如下：

• 每出现1个左括号，就会触发1次Push操作，栈长度+1
• 每出现1个合法匹配的右括号，就会触发1次Pop操作，栈长度-1
• 完全合法的括号字符串，左括号的总数量必然等于右括号的总数量，因此Push的总次数和Pop的总次数完全相等
• 栈初始长度为0，加减次数完全抵消后，最终长度自然为0，不存在「未对所有元素调用Pop()」的情况——所有被Push进栈的右括号，后续都被匹配的右括号触发的Pop操作弹出了。

举个直观的例子，输入合法字符串()[]{}的栈变化过程：

1. 遍历(：压入)，栈为[')']
2. 遍历)：弹出栈顶)匹配成功，栈为空
3. 遍历[：压入]，栈为[']']
4. 遍历]：弹出栈顶]匹配成功，栈为空
5. 遍历{：压入}，栈为['}']
6. 遍历}：弹出栈顶}匹配成功，栈为空
   遍历结束后栈长度为0，返回true。

如果输入字符串不合法，比如多了左括号(()，最终会剩1个元素在栈中，返回false；如果多了右括号())，遍历到第三个字符时就会因为栈为空提前返回false。

内容的提问来源于stack exchange，提问作者Yusuf Eminoglu