괄호 짝 맞추기
면접 대비시간 제한7초메모리 제한1024 MB
길이가 20 이하인 괄호 문자열에서 일부 자리가 물음표로 주어질 때, 네 종류의 괄호로 물음표를 채워 전체가 올바른 괄호열이 되는 경우의 수를 센다.
문제
괄호는 네 종류가 있다. 둥근 괄호 (), 대괄호 [], 중괄호 {}, 홑화살괄호 <>이다. 올바른 괄호열은 다음과 같이 정의된다.
- 빈 열은 올바른 괄호열이다.
- X가 올바른 괄호열이고 p가 여는 괄호, q가 닫는 괄호이며 p와 q의 종류가 같을 때, pXq는 올바른 괄호열이다.
- X와 Y가 올바른 괄호열이면 X와 Y를 이어 붙인 Z = XY도 올바른 괄호열이다.
일부 괄호는 주어져 있고 나머지는 알 수 없어 물음표('?')로 표시된 괄호열이 있다. 물음표 자리에 위 네 종류의 괄호를 채워 넣어 올바른 괄호열을 만들려고 한다. 만들 수 있는 서로 다른 올바른 괄호열은 몇 개인가?
입력
입력은 한 줄로 주어지며, 길이가 0이 아닌 괄호열이 들어온다. 괄호열의 길이는 짝수이고 20 이하이다. 모든 문자는 네 종류의 여는 괄호 또는 닫는 괄호 가운데 하나이거나, 알 수 없는 괄호를 나타내는 물음표이다. 괄호열에는 물음표가 적어도 하나 있다.
출력
만들 수 있는 서로 다른 올바른 괄호열의 개수를 출력한다.