Chi phí để cân bằng dấu ngoặc trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm chi phí để cân bằng các dấu ngoặc đơn.

Đối với điều này, chúng ta sẽ được cung cấp một chuỗi các dấu ngoặc. Nhiệm vụ của chúng tôi là cân bằng các dấu ngoặc đơn đó trong phương trình bằng cách dịch chuyển vị trí của chúng đi một và in ra -1 nếu không thể cân bằng chúng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int costToBalance(string s) {
   if (s.length() == 0)
      cout << 0 << endl;
   //storing count of opening and
   //closing parentheses
   int ans = 0;
   int o = 0, c = 0;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '(')
         o++;
   if (s[i] == ')')
      c++;
   }
   if (o != c)
      return -1;
   int a[s.size()];
   if (s[0] == '(')
      a[0] = 1;
   else
      a[0] = -1;
   if (a[0] < 0)
      ans += abs(a[0]);
   for (int i = 1; i < s.length(); i++) {
      if (s[i] == '(')
         a[i] = a[i - 1] + 1;
      else
         a[i] = a[i - 1] - 1;
      if (a[i] < 0)
         ans += abs(a[i]);
   }
   return ans;
}
int main(){
   string s;
   s = ")))(((";
   cout << costToBalance(s) << endl;
   s = "))((";
   cout << costToBalance(s) << endl;
   return 0;
}

Đầu ra

9
4