本文共 1248 字，大约阅读时间需要 4 分钟。

括号匹配问题的解决方案

新增一个字符堆栈，该堆栈主要用于存储当前未匹配的括号。遍历输入字符串中的每个字符，如果遇到左括号(/{/[)将其压入栈；如果是右括号(})/,则检查栈顶部的字符是否为对应的左括号。如果是，则弹出栈顶字符，无此操作则将字符压入栈。这样可以确保了括号必须闭合在正确的位置。在遍历结束后，若栈中没有任何字符，则说明所有括号均已正确闭合。

class Solution {    bool isValid(string s) {        stack
   
     A;        size_t n = s.length();        for (size_t i = 0; i < n; i++) {            char ch = s[i];            if (ch == '(' || ch == '{' || ch == '[') {                A.push(ch);                continue;            }            if (ch == ')') {                if (A.empty()) return false;                if (A.top() == '(') A.pop();                else A.push(ch);            }            if (ch == '}') {                if (A.empty()) return false;                if (A.top() == '{') A.pop();                else A.push(ch);            }            if (ch == ']') {                if (A.empty()) return false;                if (A.top() == '[') A.pop();                else A.push(ch);            }        }        return A.empty();    }}
   

代码解释

• 使用了一个栈来跟踪未匹配的左括号。
• 遍历字符串中的每个字符。
• 对于每一个右括号(})/，检查栈是否为空以及栈顶部是否为对应的左括号。
• 如果右括号对应的左括号已被匹配，则弹出栈顶字符。
• 若未找到对应的左括号，则继续压入栈，直到所有字符遍历完毕。

技术细节

为了确保括号闭合的正确性，我们可以使用栈数据结构。每当遇到一个左括号左括号{或[就将其压入栈，而每当遇到一个右括号Transactional右括号)}，则检查栈顶部是否为对应的左括号。

• 保持栈优先级的正确序列。
• 最终，栈应为空才能表示所有左括号均已闭合。

转载地址：http://zlgyk.baihongyu.com/