화학
면접 대비시간 제한1초메모리 제한128 MB
중첩된 괄호와 배수를 가진 화학식을 해석해 각 원소의 총 원자 수를 사전순으로 출력한다.
문제
분자 M의 화학식을 보면 그 분자가 어떤 원소로 이루어져 있는지 알 수 있다. 화학식은 다음 문법을 따른다.
M := G | M G
G := S | S C
S := A | '(' M ')'
C := T | N E
E := D | D E
T := '2' | ... | '9'
N := '1' | ... | '9'
D := '0' | .. | '9'
A := U | U L | U L L
U := 'A' | .. | 'Z'
L := 'a' | .. | 'z'
카운트 C는 바로 앞에 있는 서브그룹 S에 곱하는 수이다.
예를 들어 H2O는 H(수소) 2개와 O(산소) 1개로 이루어져 있다. 또한 (AlC2)3Na4는 Al(알루미늄) 3개, C(탄소) 6개, Na(나트륨) 4개로 이루어져 있다.
화학식이 주어졌을 때, 그 화학식을 구성하는 원소를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 올바른 화학식 하나로 주어지며, 각 줄의 길이는 100자를 넘지 않는다. 입력은 파일의 끝(EOF)까지 계속된다.
출력
각 테스트 케이스마다 주어진 화학식을 구성하는 원소를 한 줄에 출력한다. 원소는 원소 기호의 사전순으로 정렬하며, 각 원소를 "개수기호" 형태로 '+'로 이어 붙여 출력한다. 단, 개수가 1인 원소는 개수를 생략한다.