C++의 괄호 점수

<시간/>

균형 잡힌 괄호 문자열 S가 있다고 가정하고 다음 규칙에 따라 문자열의 점수를 계산해야 합니다. -

()의 점수는 1입니다.
AB의 점수는 A + B이며, 여기서 A와 B는 균형이 잡힌 두 개의 괄호 문자열입니다.
(A) 점수는 2 * A이며, 여기서 A는 균형 잡힌 괄호 문자열입니다.

따라서 입력이 "(()(()))"와 같으면 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=0, 스택 st 정의
0 범위에서 문자열 S
- S[i]가 괄호를 여는 경우 스택에 -1을 삽입합니다.
- 그렇지 않으면
  - 스택의 맨 위가 -1이면 스택에서 삭제하고 1을 스택에 삽입
  - 그렇지 않으면
    - x :=0
    - 스택의 맨 위가 -1이 아닌 동안
      - x를 st만큼 증가, st에서 삭제
    - x :=x * 2
    - st에서 삭제하고 x 삽입
스택이 비어 있지 않은 동안
- st의 맨 위로 증가하고 맨 위 요소 삭제
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int scoreOfParentheses(string S) {
      int ans = 0;
      stack <int> st;
      for(int i = 0; i < S.size(); i+=1){
         if(S[i] == '('){
            st.push(-1);
         }else{
            if(st.top() == -1){
               st.pop();
               st.push(1);
            }else{
               int x = 0;
               while(st.top() != -1){
                  x += st.top();
                  st.pop();
               }
               x *= 2;
               st.pop();
               st.push(x);
            }
         }
      }
      while(!st.empty()){
         ans += st.top();
         st.pop();
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.scoreOfParentheses("(()(()))"));
}

입력

"(()(()))"