C++에서 표현식에 중복 괄호가 있는지 여부 찾기

표현식 exp가 있다고 가정하고 exp 주위에 중복된 괄호 세트가 있는지 여부를 확인해야 합니다. 하나의 하위 표현식이 둘 이상의 괄호 세트로 둘러싸여 있는 경우 표현식에는 중복 괄호가 있습니다. 예를 들어 표현식이 −

(5+((7−3)))

여기서 하위 표현식(7 – 3)은 두 개의 괄호 쌍으로 둘러싸여 있으므로 중복 괄호입니다.

이 문제를 해결하기 위해 스택을 사용합니다. 우리는 exp의 각 문자를 반복하고 문자가 여는 괄호 '(' 또는 연산자 또는 피연산자 중 하나라도 스택에 푸시합니다. 문자가 닫는 괄호일 때 스택에서 반복적으로 문자를 팝합니다. 일치하는 여는 괄호가 발견되고 여는 괄호 쌍과 닫는 괄호 쌍 사이에서 만나는 모든 문자에 대해 값이 증가하는 카운터가 사용될 때까지 카운터 값과 동일한 값이 1보다 작은 경우 중복 괄호 쌍 은(는) 있지만 그렇지 않으면 찾을 수 없습니다.

예시

#include<iostream>
#include<stack>
using namespace std;
bool hasDuplicateParentheses(string str) {
   stack<char> stk;
   for (int i = 0; i<str.length(); i++) {
      char ch = str[i];
      if (ch == ')') {
         char top = stk.top();
         stk.pop();
         int count = 0;
         while (top != '(') {
            count++;
            top = stk.top();
            stk.pop();
         }
         if(count < 1) {
            return true;
         }
      }
      else
         stk.push(ch);
   }
   return false;
}
int main() {
   string str = "(5+((7-3)))";
   if (hasDuplicateParentheses(str))
      cout << "Duplicate parentheses has Found";
   else
      cout << "No Duplicates parentheses has Found ";
}

출력

Duplicate parentheses has Found