식에서 균형 잡힌 괄호 확인 - O(1) space - C++의 O(N^2) 시간 복잡도

개념

'(', ')', '{', '}', '[' 및 ']' 문자를 포함하는 주어진 문자열 str과 관련하여 작업은 대괄호가 균형을 이루는지 여부를 찾는 것입니다.

대괄호는 −

• 닫는 대괄호는 같은 유형의 대괄호로 닫아야 합니다.

• 다시 올바른 순서에 따라 여는 대괄호를 닫습니다.

입력 - str ="(()){}"

출력 − 예

입력 - str ="))(([]["

출력 - 아니요

방법

• 두 개의 변수와 b를 할당하여 비교할 두 개의 대괄호를 추적합니다.

• 여는 대괄호를 만나면 값이 증가하고 닫는 대괄호를 만나면 감소하는 개수를 유지해야 합니다.

• 여는 대괄호가 나타나면 b =a, a =a + 1 및 count=count+1을 할당합니다.

• 닫는 대괄호가 발생할 때 i와 j에서 대괄호 수를 줄이고 비교합니다.

  • 와 b의 대괄호가 일치하는 것으로 확인되면 th 및 b 위치의 문자열에서 '#'을 대체하십시오. a는 증가하고 b는 '#'이 아닌 값을 만나거나 b ≥ 0이 될 때까지 감소합니다.

  • 대괄호 a와 b가 일치하지 않는 경우 false를 반환합니다.

• count !=0이면 false를 반환합니다.

예시

// 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;
}

출력

Yes