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

1. 题目

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：输入："())"输出：1示例 2：输入："((("输出：3示例 3：输入："()"输出：0示例 4：输入："()))(("输出：4 提示：S.length <= 1000S 只包含 '(' 和 ')' 字符。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

• 用栈来匹配，未匹配的在栈内留下来

class Solution {
   public:    int minAddToMakeValid(string S) {
           stack
   
     stk;        for(int i = 0; i < S.size(); ++i)        {
           	if(stk.empty())        		stk.push(S[i]);        	else        	{
           		if(stk.top()=='(' && S[i]==')')        			stk.pop();        		else        			stk.push(S[i]);        	}        }        return stk.size();//未匹配的字符数    }};
   

or

class Solution {
   public:    int minAddToMakeValid(string S) {
           int left = 0;        int right = 0;        for(char &c:S)        {
               if(c=='(')                 left++;            else            {
                   if(left>0) //右括号可以与之匹配                    left--;                else //右括号没有相应的左括号匹配                    right++;            }           }        return left+right;    }};