Class ATree

java.lang.Object

ATree

Direct Known Subclasses:

ExpressionTree

public abstract class ATree
extends java.lang.Object

Provides the Node data structure and defines the abstract methods that you need to implement in ExpressionTree.java. It also has a method that converts an expression tree into a format that can be displayed graphically.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	ATree.Node

Field Summary

Fields

Modifier and Type	Field	Description
ATree.Node	root

Constructor Summary

Constructors

Constructor	Description
ATree()

Method Summary

Modifier and Type	Method	Description
abstract void	build(java.util.List<java.lang.String> postfix)	Calls a recursive helper method to build an expression tree from a postfix List.
abstract java.util.List<java.lang.String>	convert(java.util.Queue<java.lang.String> infix)	Convert an infix expression into postfix order.
java.util.ArrayList<java.lang.String>	display()	Displays the expression tree in graphical format.
void	displayRecursive(ATree.Node current, java.util.ArrayList<java.lang.String> graph, java.lang.String name)
abstract int	evaluate()	Calls a recursive helper method to evaluate expression tree and return the result.
abstract java.lang.String	infix()	Calls a recursive helper method to traverse the expression tree in infix order and build the expression.
static boolean	isInteger(java.lang.String token)
static boolean	isOperator(java.lang.String token)
abstract java.util.Queue<java.lang.String>	parse(java.lang.String expression)	Parse an infix expression into an ArrayList of tokens.
abstract java.lang.String	postfix()	Calls a recursive helper method to traverse the expression tree in postfix order and build the expression.
static int	precedence(java.lang.String operator)	Returns operator precedence.
abstract java.lang.String	prefix()	Calls a recursive helper method to traverse the expression tree in prefix order and build expression.
static int	valueOf(java.lang.String token)	Converts an String into an int.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

root

public ATree.Node root

Constructor Detail

ATree

public ATree()

Method Detail

parse

public abstract java.util.Queue<java.lang.String> parse(java.lang.String expression)

Parse an infix expression into an ArrayList of tokens.

Reads a string that contains an infix expression, and converts it to a list of tokens. Each token is an operator, operand (integer), or parentheses. We suggest using the StringTokenizer method of lexing from the expressions lab, no changes should be necessary except for the addition of the modulo operator. The parse method should be able to handle an arbitrary number of white spaces in the expression. Our implementation of this method is ~8 lines of code, including brackets but not comments or white space.

Parameters:

expression - a valid expression

Returns:

expression in infix order

convert

public abstract java.util.List<java.lang.String> convert(java.util.Queue<java.lang.String> infix)

Convert an infix expression into postfix order.

Converts the list of tokens from the parse method from infix to postfix, using the Shunting-yard algorithm from Edsger Dijkstra, a famous computer scientist, as documented here. Our implementation uses Queue for the queue, and Deque for the stack. You may want to use the utility methods isOperator(String), isInteger(String), and precedence(String).

Our implementation is ~21 lines of code.

Parameters:

infix - expression in infix order

Returns:

expression in postfix order

build

public abstract void build(java.util.List<java.lang.String> postfix)

Calls a recursive helper method to build an expression tree from a postfix List.

Parameters:

postfix - the expression tree

prefix

public abstract java.lang.String prefix()

Calls a recursive helper method to traverse the expression tree in prefix order and build expression.

Returns:

a string representing the expression in prefix order.

infix

public abstract java.lang.String infix()

Calls a recursive helper method to traverse the expression tree in infix order and build the expression.

Returns:

a string representing the expression infix order.

postfix

public abstract java.lang.String postfix()

Calls a recursive helper method to traverse the expression tree in postfix order and build the expression.

Returns:

a string representing the expression in postfix order.

evaluate

public abstract int evaluate()

Calls a recursive helper method to evaluate expression tree and return the result.

Returns:

the result of the expression.

display

public java.util.ArrayList<java.lang.String> display()

Displays the expression tree in graphical format.

Returns:

a dot file representation of the tree.

displayRecursive

public void displayRecursive(ATree.Node current,
                             java.util.ArrayList<java.lang.String> graph,
                             java.lang.String name)

Parameters:

current -

graph -

name -

isOperator

public static boolean isOperator(java.lang.String token)

Parameters:

token - a token

Returns:

true if token is an operator.

isInteger

public static boolean isInteger(java.lang.String token)

Parameters:

token - a token

Returns:

true if the token is an int.

valueOf

public static int valueOf(java.lang.String token)

Converts an String into an int. For example the string "11" is converted to the int 11.

Parameters:

token - a string representing a number

Returns:

the decimal representation if the token or -1.

precedence

public static int precedence(java.lang.String operator)

Returns operator precedence.

Parameters:

operator - the operator to evaluate

Returns:

a ranking of operator precedence.