C++에서 괄호 번호 인쇄

이 문제에서는 표현식이 제공됩니다. 그리고 대괄호 번호 시퀀스를 인쇄해야 합니다. 문제를 더 잘 이해하기 위해 예를 살펴보겠습니다.

예,

Input : ((()())())
Output : 1233442551

설명 − 여기에서 우리는 5개의 대괄호 쌍을 발견했으며 [발생 순서대로 인쇄했습니다.

이제 문제를 알았으므로 이 솔루션에 대한 솔루션을 만들어 보겠습니다.

이 문제를 해결하려면 스택 데이터 구조가 필요합니다. 우리는 왼쪽 대괄호의 개수를 유지하고 스택이 오른쪽 대괄호를 추적하는 하나의 변수를 사용할 것입니다. 우리는 왼쪽 대괄호를 세어 스택으로 밀어넣고 오른쪽 대괄호를 만나면 팝합니다.

알고리즘

Step 1 : Initialise leftBrackets = 1. stack rightBrackets, empty.
Step 2 : traverse the expression using variable i = 0 to n-1.
Step 3 : if expression[i] == ‘(’ i.e. left bracket is encountered. Then,
   Step 3.1 : PRINT ‘leftBracket ‘.
   Step 3.2 : push the value of leftBracket in stack.
   Step 3.3 : leftBracket++.
Step 4 : if expression[i] == ‘)’ i.e. right bracket is encountered. Then,
   Step 4.1 : PRINT top of stack.
   Step 4.2 : pop top element of the stack.
Step 5 : EXIT.

예시

이제 위 알고리즘의 구현을 설명하는 프로그래밍을 만들어 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void bracketCount(string expression, int n){
   int leftBracket = 1;
   stack<int> rightBracket;
   for (int i = 0; i < n; i++) {
      if (expression[i] == '(') {
         cout<<leftBracket<<" ";
         rightBracket.push(leftBracket);
         leftBracket++;
      }
      else if(expression[i] == ')') {
         cout<<rightBracket.top() << " ";
         rightBracket.pop();
      }
   }
}
int main(){
   string expression = "()((())()())";
   int n = expression.size();
   bracketCount(expression, n);
   return 0;
}

출력

1 1 2 3 4 4 3 5 5 6 6 2