Description: 树的和
★问题描述
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
-Description 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 Platform: |
Size: 888832 |
Author:skyalone |
Hits: