a029: Tree Summing
標籤 :
通過比率 : 100% (7 人 / 7 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-04-03 10:56

內容 :

LISP是最早的高階程式語言之一,而Lists則是LISP中最重要的資料結構。Lists可以很簡單的用來表達其他的資料結構,例如:tree。在這個問題中,給你LISP中的S表示式(S-expression),請你寫一個程式判斷這表示式(整數的二元樹)是否存在一條由根節點到樹葉的路徑,且路徑上各節點的值的和為某一特定的數 n。例如:在以下的樹中共有4條從根到樹葉的路徑。而各路徑的和分別為27,22,26以及18。

在LISP中的S表示式有以下的格式:

empty tree ::= ()
tree ::= empty tree | (integer tree tree)

上圖中的樹若以S表示式表達為:(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )

注意:在樹中所有的葉節點為 (integer () () )

既然空樹不存在任何根到葉的路徑,任何對空樹是否有某個和的詢問,其答案都是否定的。

輸入說明

輸入含有多組測試資料。每組測試資料的開頭有一個整數 n。接下來為一S表示式。所有的S表示式一定是合法的,但是可能會跨多列,並且可能含有空白字元。請參考Sample Input。

輸出說明

對每一組測試資料輸出一列。如果S表示式所表達的樹存在一條由根到葉的路徑,且路徑上節點值的和為n的話,則輸出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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :

DFS, parser

標籤:
出處:
UVA [編輯: zero (管理員) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」