UVa. 112, PKU 1145. Tree Summing.

트리 합계?!

배경지식

LISP는 FORTRAN과 함께 최초의 고수준 프로그래밍 언어중 하나로, 현재까지 쓰이는 언어중 가장 오래된 것중 하나이다. 리스트나 트리 같은 LISP의 트리 구조는 현재까지도 쉽게 채용되어 잘 사용되고 있다.

이 문제는 LISP의 S-표현식의 방식에 근거해 이진 트리를 읽어들이는 문제와 관련이 있다.

문제

정수로 구성된 이진 트리를 입력받아서 루트-리프의 루틴중 원소들의 합이 가장 큰 루틴을 찾아내는 프로그램을 기술하라. 아래 예시에서는 각 루틴의 값이 27, 22, 26 18이다.

이진트리는 LISP의 S-표현식에서 다음과 같이 구성한다.

 
빈 트리 		 ::= 		 ()

트리 		 ::= 		 빈 트리    (정수 트리 트리)

위 예시의 트리 다이어그램을 표현식에 맞추어 바꾸면 이와 같다. (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )

모든 리프노드는 이렇게 구성됨을확인하라. (정수 () () )

빈 트리는 루트부터 리프까지의 루틴이 없으니, 이 경우는 음의 정수를 출력하도록 구성하라.

입력

입력은 정수 하나와 트리의 짝으로 구성된다. 각 테스트케이스는 첫 부분에 존재여부를 물을 루트-리프 루틴의 합이 입력되고, 두번째 부분에는 S-표현식의 방식으로 확인할 트리가 주어진다. 모든 S-표현식의 트리는 항상 유효할 것이나, 여러 줄이나 여러개의 빈칸을 포함한 채로 입력될 것이다. 입력시 여러개의 테스트케이스가 입력될 수 있으며, EOF까지 입력받는다.

출력

각 테스트케이스 쌍에 대해 한 입력당 한번의 출력을 한다. I, T로 구분했을때, T에 I값의 합 루틴이 존재한다면 yes를, 아니면 no를 출력한다.

입력 예시

22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3 
     (2 (4 () () )
        (8 () () ) )
     (1 (6 () () )
        (4 () () ) ) )
5 ()

출력 예시

yes
no
yes
no







 



 
*역자주 - UVa와 PKU에 동시에 있는 문제입니다. 답안은 띄우겠으며, 솔루션도 함께 올릴 테니 
필요하시다면 참고하시면 됩니다. 문제가 약간 지저분한게 흠입니다.