Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++를 사용하여 대괄호 문자열에서 등점을 찾습니다.

<시간/>

여기서 우리는 대괄호 문자열에서 동일한 점을 얻는 방법을 볼 것입니다. 등점은 인덱스 I로 앞의 여는 괄호의 수가 뒤의 닫는 괄호의 수와 같도록 합니다. 대괄호 문자열이 "(()))(()()()))"와 같다고 가정하고 자세히 보면

C++를 사용하여 대괄호 문자열에서 등점을 찾습니다.

따라서 0에서 9까지의 여는 괄호의 개수는 5이고, 9에서 14까지의 닫는 괄호의 개수도 5이므로 이것이 등점입니다.

이 문제를 해결하려면 다음 몇 단계를 따라야 합니다 -

  • 모든 인덱스 i까지 문자열에 나타나는 여는 괄호의 수를 저장합니다.
  • 문자열에 나타나는 닫는 괄호의 수를 각 인덱스 I까지 저장하지만 마지막 인덱스부터 수행해야 합니다.
  • 인덱스가 여는 괄호와 닫는 괄호 값이 같은지 확인합니다.

#include<iostream>
#include<cmath>
using namespace std;
int findEqualPoint(string str) {
   int total_length = str.length();
   int open[total_length+1] = {0}, close[total_length+1] = {0};
   int index = -1;
   open[0] = 0;
   close[total_length] = 0;
   if (str[0]=='(') //check whether first bracket is opening or not, if so mark open[1] = 1
   open[1] = 1;
   if (str[total_length-1] == ')') //check whether first bracket is closing or not, if so mark       close[end] = 1
   close[total_length-1] = 1;
   for (int i = 1; i < total_length; i++) {
      if ( str[i] == '(' )
      open[i+1] = open[i] + 1;
   else
      open[i+1] = open[i];
   }
   for (int i = total_length-2; i >= 0; i--) {
      if ( str[i] == ')' )
         close[i] = close[i+1] + 1;
      else
         close[i] = close[i+1];
   }
   if (open[total_length] == 0)
      return total_length;
   if (close[0] == 0)
      return 0;
   for (int i=0; i<=total_length; i++)
      if (open[i] == close[i])
      index = i;
   return index;
}
int main() {
   string str = "(()))(()()())))";
   cout << "Index of equal point: " << findEqualPoint(str);
}

출력

Index of equal point: 9