用栈检查括号是否匹配的原理

栈可以用来检查括号是否匹配，其原理如下：

1. 创建一个空栈。

2. 从左到右遍历括号序列中的每一个字符。

3. 如果遇到左括号（包括小括号、中括号和大括号），则将其压入栈中。

4. 如果遇到右括号，则取出栈顶元素进行匹配。

5. 如果栈顶元素与当前右括号匹配，则继续遍历下一个字符。

6. 如果栈顶元素与当前右括号不匹配，则括号序列不匹配，返回错误。

7. 最后，如果遍历完成后栈为空，则括号序列匹配，否则不匹配。

例如，对于括号序列 "{[(())]}"，遍历过程如下：

1. 遇到 '{'，将其压入栈中。

2. 遇到 '['，将其压入栈中。

3. 遇到 '('，将其压入栈中。

4. 遇到 ')'，取出栈顶元素'('，与')'匹配。

5. 遇到 ')'，取出栈顶元素'['，与')'不匹配，返回错误。

因此，该括号序列不匹配。

相关问题

用c++的栈生成检查括号是否匹配的代码

以下是使用 C++ 标准库中的 stack 实现括号匹配检查的代码示例：

#include <iostream>
#include <stack>
#include <string>

bool isMatching(char c1, char c2) {
    return (c1 == '(' && c2 == ')') ||
           (c1 == '[' && c2 == ']') ||
           (c1 == '{' && c2 == '}');
}

bool checkParentheses(const std::string& s) {
    std::stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty() || !isMatching(st.top(), c)) {
                return false;
            }
            st.pop();
        }
    }

    return st.empty();
}

int main() {
    std::string s = "{()[()]}";
    if (checkParentheses(s)) {
        std::cout << "The parentheses are matching." << std::endl;
    } else {
        std::cout << "The parentheses are not matching." << std::endl;
    }
    return 0;
}

该代码中使用了一个 `isMatching()` 函数来判断当前字符与栈顶字符是否匹配，`checkParentheses()` 函数则使用栈来进行括号匹配检查。最后，根据栈是否为空来判断括号序列是否匹配。

用栈实现括号匹配

好的，下面是使用栈实现括号匹配的示例代码（使用 Python 语言）：

def parentheses_match(s):
    """
    括号匹配函数
    :param s: 包含括号的字符串
    :return: True/False 表示是否匹配
    """
    stack = []  # 用列表模拟栈
    for c in s:
        if c in "([{":
            stack.append(c)  # 如果是左括号，入栈
        elif c in ")]}":
            if not stack:  # 如果栈为空，说明缺少左括号，匹配失败
                return False
            top = stack.pop()  # 弹出栈顶元素
            if top == "(" and c != ")":  # 如果左右括号不匹配，匹配失败
                return False
            elif top == "[" and c != "]":
                return False
            elif top == "{" and c != "}":
                return False
    return not stack  # 如果栈为空，说明匹配成功；否则匹配失败

使用栈实现括号匹配的思路是，遍历字符串中的每个字符，如果是左括号，则将其入栈；如果是右括号，则弹出栈顶元素，并判断左右括号是否匹配。如果匹配，则继续遍历；如果不匹配，则匹配失败。最后，如果栈为空，说明匹配成功；否则匹配失败。

这个算法的时间复杂度是 $O(n)$，其中 $n$ 是字符串的长度。因为算法只需要遍历一次字符串，并且每次操作栈的时间复杂度是 $O(1)$。