只有满足下面几点之一括号字符串才是有效的它是一个空字符串或者它可以被写成ABA与B连接, 其中A和B都是有效字符串或者它可以被写作(A)其中A是有效字符串。给定一个括号字符串s在每一次操作中你都可以在字符串的任何位置插入一个括号例如如果s ()))你可以插入一个开始括号为(()))或结束括号为())))。返回为使结果字符串s有效而必须添加的最少括号数示例 1输入s ())输出1示例 2输入s (((输出3提示1 s.length 1000s只包含(和)字符。分析一个合法的括号字符串本质上要求每一个右括号)前面都能够找到一个左括号(与它匹配并且最后不能剩下没有匹配的左括号。可以从左到右遍历字符串并用一个变量记录当前还没有被匹配的左括号数量。遇到左括号(时说明多了一个等待匹配的左括号将数量加 1遇到右括号)时如果当前还有未匹配的左括号就用它与这个右括号配对将数量减 1。如果遇到右括号时已经没有左括号可以和它匹配那么这个右括号无论如何都无法通过后面的字符得到匹配因为它需要的左括号必须出现在它前面。因此此时必须额外添加一个左括号把需要添加的括号数量加 1。遍历结束之后如果还有一些左括号没有匹配那么就需要在后面补上同样数量的右括号。所以最终需要添加的括号数量就是遍历过程中无法匹配的右括号数量加上最后剩余的左括号数量。例如字符串()))((前面的()可以正常匹配之后多出的两个)没有左括号与之匹配需要补两个(最后又剩下两个(没有右括号匹配需要补两个)。因此一共需要添加 4 个括号。class Solution { public: int minAddToMakeValid(string s) { int ns.length(),left0,cnt_left0; for(int i0,jn-1;in;i,--j) { if(s[i]() { if(left0)cnt_left-left,left0; left; } else if(s[i]))left--; } cnt_leftabs(left); return cnt_left; } };