[백준] 괄호의 값

https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

입력 문자열 string 에 strip() 함수 없이 받으면 '틀렸습니다' 을 받는다.

 

예로 '(()[[]])([])' 를 구해보자.

분배법칙과 스택을 이용한다. 즉, '(())' + '([[]])' + '([])'

 

'(' : temp = 2

'((' : temp = 2 * 2 = 4

'(()' : 바로 이전에 여는 괄호가 들어왔고 '()' 로 괄호가 닫혔으므로 temp = 4 를 answer 에 더해 주고 temp 를 2로 나눠준다. 그리고 '()' 를 스택에서 제거해준다. temp = 2, answer = 4

'([' : temp = 2 * 3 = 6

'([[' : temp = 6 * 3 = 18

'([[]' : 바로 이전에 여는 괄호가 들어왔고 '[]' 로 괄호가 닫혔으므로 temp = 18 을 answer 에 더해 주고 temp 를 3으로 나눠준다. 그리고 '[]' 를 스택에서 제거해준다. temp = 6, answer = 22

'([]' : 바로 이전에 닫는 괄호가 들어왔으므로 temp 를 3으로 나눠주고 스택에서 '[]' 을 제거해준다.(이미 앞에서 계산이 되었다.) temp = 2, answer = 22

'()' : 바로 이전에 닫는 괄호가 들어왔으므로 temp 를 2로 나눠주고 스택에서 '()' 을 제거해준다. temp = 1, answer = 22

'(' : temp = 1 * 2, answer = 22

'([' : temp = 2 * 3 = 6, answer = 22

'([]' : 바로 이전에 여는 괄호가 들어왔고 '()' 로 괄호가 닫혔으므로 temp = 6 을 answer 에 더해 주고 temp 를 3으로 나눠준다. 그리고 '[]' 를 스택에서 제거해준다. temp = 2, answer = 28

'()' : 바로 이전에 닫는 괄호가 들어왔으므로 temp 를 2로 나눠주고 스택에서 '()' 을 제거해준다. temp = 1, answer = 28

 

또한,

닫는 괄호의 개수가 여는 괄호의 개수보다 많은 경우

닫는 괄호가 나타날 때, 스택의 마지막 두 개의 값으로 괄호를 만들 때 '[]' 또는 '()' 가 아닌 경우

여는 괄호의 개수가 닫는 괄호의 개수보다 많은 경우

올바른 괄호가 아니므로 0을 반환한다. 

 

import sys

string = sys.stdin.readline().strip()
stack = []
answer = 0
temp = 1
check = 0
pre = True

for i in string:
    stack.append(i)
    
    if i in ['(', '[']:
        check += 1
        pre = True
        
        if i == '(':
            temp *= 2
        else:
            temp *= 3
    else:
        check -= 1
        
        if check < 0:
            break
        
        if stack[-2:] == ['(', ')']:
            if pre: answer += temp
                
            temp //= 2
            stack.pop()
            stack.pop()
            
        else:
            if stack[-2:] == ['[', ']']:
                if pre: answer += temp
                
                temp //= 3
                stack.pop()
                stack.pop()
            else:
                check = -1
                break
        
        pre = False
        
print(0 if check != 0 else answer)