stack 에 여는괄호 '(' 를 넣으면서 닫는괄호 ')' 가 나올 때마다 경우에 맞게 처리해주는 방식으로 풀이했다.
'(()())' 을 예시로 설명해보겠다. 그림으로 표현해보면 아래와 같은 상황이다. sp는 스택포인터다.
여는 괄호가 등장했으므로 스택에 여는 괄호를 의미하는 -1(임의숫자)을 push해준다. 이때 중요한 점은 '('를 그대로 넣지 않는다는 것이다. 여는 괄호도 결국에는 ascii table상 40이기 때문에 점수 계산을 양수인 숫자로 하는 우리에게 혼선을 준다.
그 다음 경우도 마찬가지다.
이번에는 닫는 괄호를 만났으므로 스택을 확인한다. 여는 괄호가 있기때문에 두 여닫는 괄호가 합쳐저 1점으로 바뀐다.
이어서 계속 진행해준다.
닫는 괄호를 만났으므로 -1이 나올 때까지 pop한다. 그리고 그 사이에 있는 점수들을 더한 후 2를 곱하여 push해준다.
이제 모든 괄호를 다 확인했으므로 pop을 하면 자동으로 답이 튀어나온다.
그렇지만 아래 그림과 같이 합산해줘야 하는 경우도 있으므로 stack이 빌 때까지 pop하여 그 합을 결과값으로 반환한다.
int sp=0;
int arr[50];
void push(int ele){
arr[sp++]=ele;
}
int pop(){
return arr[--sp];
}
int scoreOfParentheses(char* s) {
for (int i=0;s[i]!=0;i++){
if(s[i]=='(') push(-1);
else{
int ele=pop();
if(ele==-1) push(1);
else{
int tmp=0;
while(ele!=-1){
tmp+=ele;
ele=pop();
}
push(2*tmp);
}
}
}
int res=0;
while(sp>=1){
res+=pop();
}
return res;
}