树的和

★问题描述

LISP是一种高级语言，可以用它来表示其它的数据结构，例如二叉树。二叉树由LISP的S

表达式来表示，其规则如下：

空树=()

树= (整数 左子树 右子树)

叶节点=(整数 () ())

★编程任务

问题是给定一棵由LISP的S表达式决定的二叉树，问是否存在一条从根到叶节点的路径

P，使这条路径上所有节点的和等于一个给定的整数I。

★数据输入

由文件input.txt给出输入数据。每个输入数据包含多组数据，每组数据包含一个整数I和

一个S表达式T(代表二叉树)，整数I后可以跟多个空格。S表达式可以跨越多行，可以包含多余

的空格。

★结果输出

将计算结果输出到文件output.txt。如果存在一条路径p，使路径上所有节点的和等于I，

则输出”yes”，否则输出”no”。

输入文件示例输出文件示例

input.txt output.txt

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

-Descr iption of the problem ★

LISP is a high-level language, you can use it to that other data structures, such as binary tree. Binary tree by the LISP S-

Expression to that of its rules as follows:

Empty tree = ()

Tree = (Integer left subtree right subtree)

Leaf node = (integer () ())

★ programming tasks

The problem is given by an S-expression LISP decision tree to ask whether there is a leaf node from the root to the path

P, so that all nodes on the path and equal to a given integer I.

★ data entry

Given by the input data file input.txt. Each input data includes multiple sets of data, each data contains an integer I and

An S expression T (on behalf of binary tree), integral I can be with a number of spaces. S expression across multiple lines, may contain redundant

Spaces.

★ output

The results will be output to the file output.txt. If there is a path p, so that the path on all nodes and equal to I,

Then output "yes", otherwise output "no".

Sample input file output file