Kiểm tra các dấu ngoặc cân bằng trong một biểu thức - O (1) không gian - O (N ^ 2) thời gian phức tạp trong C ++

Khái niệm

Đối với một chuỗi str đã cho có chứa các ký tự ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ và ‘]’, nhiệm vụ là tìm xem các dấu ngoặc có cân bằng hay không.

Dấu ngoặc nhọn được biểu thị là cân bằng nếu -

• Chúng tôi đóng các dấu ngoặc mở phải được đóng bằng cùng một loại dấu ngoặc.

• Một lần nữa, chúng tôi đóng các dấu ngoặc mở theo đúng thứ tự.

Đầu vào - str =“(()) {}”

Đầu ra - Có

Đầu vào - str =“)) (([] [”

Đầu ra - Không

Phương pháp

• Gán hai biến a và b để theo dõi hai dấu ngoặc được so sánh.

• Cần duy trì một số đếm có giá trị tăng lên khi gặp dấu ngoặc mở và giảm khi gặp dấu ngoặc đóng.

• Gán b =a, a =a + 1 và count =count + 1 khi bắt gặp dấu ngoặc mở.

• Tại thời điểm bắt gặp số lượng giảm dần và so sánh các dấu ngoặc tại i và j,

  • Nếu người ta thấy rằng các dấu ngoặc ở a và b là trùng khớp, thì hãy thay thế ‘#’ trong chuỗi ở vị trí thứ a và b. a được tăng và b giảm cho đến khi gặp giá trị không phải ‘#’ hoặc b ≥ 0.

  • Nếu người ta thấy rằng dấu ngoặc tại a và b không phải là khớp thì trả về false.

• Nếu count! =0 thì trả về false.

Ví dụ

// C++ implementation of the approach
#include <iostream>
using namespace std;
bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
   count1--;
   if (j1 > -1 && s1[j1] == tocom1) {
      s1[i1] = '#';
      s1[j1] = '#';
      while (j1 >= 0 && s1[j1] == '#')
         j1--;
      i1++;
      return 1;
   }
   else
      return 0;
}
bool isValid(string s1){
   if (s1.length() == 0)
      return true;
   else {
      int i1 = 0;
      int count1 = 0;
      int j1 = -1;
      bool result1;
      while (i1 < s1.length()) {
         switch (s1[i1]) {
            case '}':
               result1 = helperFunc(count1, s1, i1, j1, '{');
               if (result1 == 0) {
                  return false;
               }
            break;
            case ')':
               result1 = helperFunc(count1, s1, i1, j1, '(');
               if (result1 == 0) {
                  return false;
               }
            break;
            case ']':
               result1 = helperFunc(count1, s1, i1, j1, '[');
               if (result1 == 0) {
                  return false;
               }
            break;
            default:
               j1 = i1;
               i1++;
               count1++;
            }
         }
         if (count1 != 0)
            return false;
         return true;
   }
}
// Driver code
int main(){
   string str1 = "[[]][]()";
   if (isValid(str1))
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

Đầu ra

Yes