Data Structure Programing Assignment: Fully Parenthesized Logical Expression Tree
 

In this programing assignment you evaluate a logical expression by building an expression tree and print out a (rather crude) representation of the tree.  As in the first assignment your program will read from standard-in an fully parenthesized logical expression. fully parenthesized form means there are no operational preference and there is always at least the outer most parenthesis.

An example input:

((T | F)|(T & F))
represents the logical expression tree:
      |
    /   \
   |     &
  / \   / \
 T   F T   F


The program will:

  1. Print out a tree representation on it side
  2. Evaluate the expression and print out the result
The logical operators are: The booleans are characters T of F, meaning true or false.

Note:  You may assume that the input is correct and represents a valid logical expression tree; meaning each boolean will be bracked with a T or F and the operators are | and &.

More examples:

You are to write a print routine that prints the expression tree on its left side. For each node, you should print the operation or boolean. The text for a node should be indented 4 times the depth of the node (e.g., a node at level 0, the root, would not be indented, a node at depth 3 would be indented 12 spaces).

As an example for the input:

"((T | F)|(T & F))"
Note that the quotations are indetional and are meant to assist you in acquiring the input as a single String. Then you can parse the input using String methods.

The out put of you program is:

        F
    &
        T
|
        F
    |
        T

Value is: true

Note that the tree is on it side and the value of the expression is outputted after the tree representation.

The input is a quoted delimited string of the whole logical expression.   I recommend using java's StreamTokenizer class, the input will contian only one quoted string representing the logical expression. Study the program ReadForParenLogTree.java and input file testPLTree.in to get ideas on how to parse the input stream.  You will need to build the expression tree and parsing the string by counting/matching parentheses. You may want to use String.Substing() and String.charAt() or String.toCharArray() methods.

The expression tree can be implemented as a link tree or an array tree, but you can not assume a maximum size or use the java.util Vector class.  I  recommend using the interfaces and classes provided in the book.  The code is online at http://datastructures.net/

Hint: Constructing the tree from the inputs is conceptually difficult, come to class for more hints.

After you have debugged your program put all the classes in a single file called LogExprTree.java.  LogExprTree should be the name of the only public class in the file.  Have fun computing and remember to submit a compiling program at least.