CS 503 - Advanced Programming I Programming Assignment 4

Programming Assignment 4 - Searching Trees

Advanced Programming I, Spring 2007

Due Date

This assignment is due by 5:30 p.m. on Tuesday, 20 March.

See the assignment turn-in page (last modified on 14 January 2006) for instructions on turning in your assignment.

A labeled n-ary tree T is an n-ary tree in which every node in the tree has a string associated with it; the string is called the node's label. A path through T is a sequence of nodes n₁, n₂, …, n_i, i > 0, such that node n_j has parent n_{j - 1} for 1 < j ≤ i.

A path pattern is a sequence of zero or more label patterns; successive label patterns are separated by one or more non-newline space characters, which are any characters that make isspace() true.

A label pattern is a string. With one exception, a label pattern matches a node label if the two are the same. For example, the label pattern white matches the node label white but not the node label red. The exception is the wildcard label pattern *, which matches any node label.

The path pattern p₁ p₂ ... p_i matches a path n₁ n₂ n_i through a tree if the label pattern p_j matches the label on the node n_j for 1 ≤ j ≤ i. For example, the path pattern red * blue matches the paths red white blue and red green blue in the tree

paths matching red * blue

The Problem

Write a program that reads a tree description and some path patterns from std-in and writes to std-out all paths in the tree that match the path patterns.

Input

All input comes from std-in. Input is in two parts: a description of a tree and sequence of zero or more path patterns. The two parts are separated by one or more blank lines, which is a line containing only space characters.

The tree description is input one node label per line. The labels of the child nodes are indented relative to the label of the parent node; all child labels of the same parent have the same indentation. For example, the input

red
  blue
    sky
    midnight
    slate
  white

describes the tree

a simple tree

Each path pattern is input one per line; each line contains at most one path pattern. Path patterns have the format described above; white space in a path pattern is ignored.

Output

The paths matching a given path pattern should be written to std-out one path per line. Paths should be output in the same order as the path patterns that were input. The paths between successive input path patterns should be separated by at least one blank line. If no paths match a pattern, [none] should be output.

The program should print an informative error message when it detects an error in the tree description and end execution without further processing. If the program detects an error in a path pattern, it should print an informative error message and go on to the next path pattern, if any. As always, error messages should be written to std-err and start with a bang-space ("! ").

Testing

You can use gen-input, available in the class assignment directory /export/home/class/cs-503/a4, to generate input for your program. When run, it writes an randomly generated tree description to std-out, followed by some randomly generated path expressions. You can use it with your program like so:

$ ./gen-input | ./tree-search

Because gen-input creates new input each time it's run, you might find it more convenient to save the input in a file to provide your program with consistent input:

$ ./gen-input > input

$ ./search-tree < input

My solution match-paths is also available in the class assignment directory. Remember the purpose of this assignment is to implement a correct solution, not to copy the behavior of my solution. If my solution's wrong and you copy the incorrect behavior, you're going to lose points.

This page last modified on 22 March 2006.