解題系統

內容：

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 (管理員) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」