[標準2504]かっこの値


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

1.コード

import sys

exp = list(sys.stdin.readline().rstrip())
d = {
    ')': '(',
    ']': '['
}
ignore_flag = False
ans = 0
stack = []
for char in exp:
    if char not in d:
        stack.append(char)
        ignore_flag = False
    elif stack and d[char] == stack[-1]:
        stack.pop()
        if ignore_flag:
            continue
        # () 또는 [] 으로만 구성된 괄호라면 바로 답에 더해준다
        if not stack:
            if char == ')':
                ans += 2
            elif char == ']':
                ans += 3
        else:
            add_val = 2 if char == ')' else 3
            if stack.count('(') != 0:
                # 정상출력: [()[()[()]]] = 78
                # 수정: 카운팅된 횟수를 제곱으로 곱해야 한다.
                add_val *= pow(2, stack.count('('))
            if stack.count('[') != 0:
                add_val *= pow(3, stack.count('['))
            ans += add_val
            ignore_flag = True
    else:
        print('0')
        exit(0)

# 정상출력: ()([] = 0
# if문 추가 -> stack = ['('] 인 상태로 종료되면 실패 출력
if len(stack) == 0:
    print(ans)
else:
    print('0')

2.コードの説明と後期


対称括弧を除く動作過程は[スタック]Valid Parentses問題で確認する.
  • ignore_flag:True状態であれば括弧マッチングのペアに遭遇し、pop()演算が発生しても答えは増加しない.
  • 입력값= (()[[]])([])
    char=')' stack=['('], ans=4
    char=']' stack=['(', '['], ans=22
    char=']' stack=['('], ans=28
    
    첫 번째로 괄호를 닫는 코드에서만 ans의 증가가 일어나고, 
    새로운 `[` 또는 `(`가 오기 전까지 닫는 괄호의 ans의 증가 연산은 수행하지 않는다. 

    この問題は思ったより難しい.char黄色の値を入力した場合、ans値を増やすべきでない箇所に多くの時間を費やした.最終的にはTrue,Falseタグを導入することで問題を解決する.
    テストケースこちらで確認できます.