题目描述

LISP是最早的高级编程语言之一，并且和FORTRAN一样，是目前仍在使用的最古老的编程语言之一。列表是LISP中的基本数据结构，能够很容易地被用来表示其他重要的数据结构，比如树。

这个问题是关于判断以LISP S-表达式表示的二叉树是否具有某种属性。

给定一棵由整数组成的二叉树，你需要编写一个程序，判断是否存在一条从根节点到叶节点的路径，使得该路径上节点的值之和等于一个指定的整数。例如，在下面所示的树中，恰好有四条从根节点到叶节点的路径。这些路径的节点值之和分别是$27、22、26$和$18$。

二叉树在输入文件中以LISP S-表达式的形式表示，具有以下格式：

空树 ::= ()

树 	   ::= 空树 (整数 树 树)

上面的树状图由表达式$(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )$表示。

注意，按照这种表示方式，树的所有叶子节点的形式都是(整数 $() ()$)。

由于空树没有从根节点到叶节点的路径，所以对于空树中是否存在节点值之和为指定整数的路径的任何查询，答案都必须是否定的。

输入格式

输入由一系列测试用例组成，形式为整数/树对。每个测试用例由一个整数、一个或多个空格，以及一个按照上述S-表达式格式表示的二叉树组成。所有的二叉树S-表达式都是有效的，但表达式可能会跨多行，并且可能包含空格。输入文件中会有一个或多个测试用例，输入以文件结束符终止。

输出格式

对于输入文件中的每个测试用例（整数/树对），应该有一行输出。对于每一对I, T（I代表整数，T代表树），如果在树T中存在一条从根节点到叶节点的路径，其节点值之和为I，则输出字符串“yes”；如果在树T中不存在这样的路径，则输出“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

来源

1992年杜克大学互联网编程竞赛，UVA 112