* COSC3308 Example Program-8(SNOBOL) 11/5/2002 * 1. Use of user-defined data type: DATA() * 2. Building a Binary Search tree for words found in an * input line of text. * 3. Use of LGT() to compare two strings. &Anchor = 1 &Trace = 90 * Trace('Sentence') Data('Node(Value,Left,Right)') Define('Insert(Root,Next)Current') Define('Inorder(Root)') * &Dump = 1 Sentence = INPUT Output = "INPUT SENTENCE IS:::" Output = " " Sentence Sentence = Sentence " " ;* Just in case Sentence Span(" .") = ;* Strip all leading blanks Sentence Break(" .") . FirstWord = * Create the root of the BST to be constructed that contains first input word Head = Node(FirstWord,0,0) Repeat Sentence Span(" .") = :f(Done) Sentence Break(" .") . NextWord = :F(Done) Next = Node(NextWord,0,0) ;* Create another node for next word Insert(Head,Next) :(Repeat) * Now, the tree construction is over, so print its nodes Done Output = "NODES IN THE INORDER SEQUENCE" Count = 0 Inorder(Head) :(End) ********************************************************* * Function definitions to follow * * Function (Insert(Root,Next)Current) Insert Current = Root LGT(Value(Next), Value(Current)) :S(Right) * Else, current left subtree must be traversed Left(Current) = Ident(Left(Current),0) Next :S(Return) Insert(Left(Current),Next) :(Return) * Now we must traverse the right subtree. Right Right(Current) = Ident(Right(current),0) Next :S(Return) Insert(Right(Current),Next) :(Return) ********************************************************* Function (Inorder(Root)) Inorder Ident(Root,0) :S(Return) Inorder(Left(Root)) Count = Count + 1 Output = " " Count ":::" Value(Root) Inorder(Right(Root)) :(Return) End THIS IS not SUPPOSED TO BE A VERY VERY LONG SENTENCE WITH MANY WORDS.