C ++中的最小括号添加

假设我们有一个仅包含'（'和'）'的字符串s，我们必须找到可以插入以使该字符串平衡的最小括号。

因此，如果输入像“（（()））（”），那么输出将为“（（()））（(2)”，这样可以使输出像“（（（()））()”那样平衡。

为了解决这个问题，我们将遵循以下步骤-

• ：= 0，cnt：= 0

• 对于初始化i：= 0，当i <s的大小时，更新（将i增加1），执行-

• 如果o不为零，则-

• 除此以外

• （将o减少1）

• （将cnt增加1）

• （将o增加1）

• 如果s [i]与'（'相同，则-

• 除此以外

• 返回cnt + o

让我们看下面的实现以更好地理解-

示例

 现场演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s) {
      int o = 0;
      int cnt = 0;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '('){
            o++;
         } else {
            if(o)
               o--;
            else
               cnt++;
         }
      }
      return cnt + o;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("(()))("));
}

输入值

Input:
"(()))("

输出结果

2