> For the complete documentation index, see [llms.txt](https://mqjyl2012.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mqjyl2012.gitbook.io/algorithm/leetcode/bracket-matching.md).

# 括号匹配问题

### 有效的括号【[链接](https://leetcode-cn.com/problems/valid-parentheses/)】

给定一个只包括 '('，')'，'{'，'}'，'\['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

* 左括号必须用相同类型的右括号闭合。 
* 左括号必须以正确的顺序闭合。 

注意空字符串可被认为是有效字符串。

```cpp
bool isValid(string s) {
    stack<char> cstk;
    for(char ch : s){
        if(ch == '(' || ch == '[' || ch == '{')
            cstk.push(ch);
        else{
            if(cstk.empty())
                return false;
            if(ch == ')' && cstk.top() != '(')
                return false;
            if(ch == '}' && cstk.top() != '{')
                return false;
            if(ch == ']' && cstk.top() != '[')
                return false;
            cstk.pop();
        }
    }
    return cstk.empty();
}
```

### **有效的括号字符串【**[**链接**](https://leetcode-cn.com/problems/valid-parenthesis-string/)**】（百度面试）**

给定一个只包含三种字符的字符串：（ ，） 和 \*，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

* 任何左括号 ( 必须有相应的右括号 )。&#x20;
* 任何右括号 ) 必须有相应的左括号 ( 。&#x20;
* 左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
* 一个空字符串也被视为有效字符串。

```cpp
bool checkValidString(string s) {
    stack<char> left_stk;
    stack<char> star_stk;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '(')
            left_stk.push(i);
        else if(s[i] == '*')
            star_stk.push(i);
        else{
            if(left_stk.empty() && star_stk.empty())
                return false;
            else if(!left_stk.empty())
                left_stk.pop();
            else
                star_stk.pop();
        }
    }
    while(!left_stk.empty() && !star_stk.empty()){
        if(left_stk.top() > star_stk.top())
            return false;
        left_stk.pop();
        star_stk.pop();
    }
    return left_stk.empty();
}
```

### 最长有效括号【[链接](https://leetcode-cn.com/problems/longest-valid-parentheses/)】

### **使括号有效的最少添加**【[链接](https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/)】

###

### 删除无效的括号【[链接](https://leetcode-cn.com/problems/remove-invalid-parentheses/)】

###

### 括号生成【[链接](https://leetcode-cn.com/problems/generate-parentheses/)】


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mqjyl2012.gitbook.io/algorithm/leetcode/bracket-matching.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.