ExpressionTree

java.lang.Object
- ATree
- - ExpressionTree

public class ExpressionTree
extends ATree

Nested Class Summary
- Nested classes/interfaces inherited from class ATree
  ATree.Node

Field Summary
- Fields inherited from class ATree
  root

Constructor Summary

Constructors
Constructor Description

ExpressionTree()

Constructors
Constructor	Description
`ExpressionTree()`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`void`	`build(java.util.List<java.lang.String> postfix)`	Calls a recursive helper method to build an expression tree from a postfix `List`.
`boolean`	`buildRecursive(ATree.Node current, java.lang.String token)`	Builds an expression tree from the postfix representation returned from the convert method.
`java.util.List<java.lang.String>`	`convert(java.util.Queue<java.lang.String> infix)`	Convert an infix expression into postfix order.
`int`	`evaluate()`	Calls a recursive helper method to evaluate expression tree and return the result.
`int`	`evaluateRecursive(ATree.Node current)`	Traverses the expression tree and produces the correct answer, which should be an integer.
`java.lang.String`	`infix()`	Calls a recursive helper method to traverse the expression tree in infix order and build the expression.
`java.lang.String`	`infixRecursive(ATree.Node current)`	Concatenates the tokens in the expression tree returned from the `build(List)` method in infix order.
`java.util.Queue<java.lang.String>`	`parse(java.lang.String expression)`	Parse an infix expression into an `ArrayList` of tokens.
`java.lang.String`	`postfix()`	Calls a recursive helper method to traverse the expression tree in postfix order and build the expression.
`java.lang.String`	`postfixRecursive(ATree.Node current)`	Concatenates the tokens in the expression tree returned from the `build(List)` method in postfix order.
`java.lang.String`	`prefix()`	Calls a recursive helper method to traverse the expression tree in prefix order and build expression.
`java.lang.String`	`prefixRecursive(ATree.Node current)`	Concatenates the tokens in the expression tree returned from the `build(List)` method in prefix order.

Methods inherited from class ATree
display, displayRecursive, isInteger, isOperator, precedence, valueOf

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - ExpressionTree
```
public ExpressionTree()
```
- Method Detail
  - parse
```
public java.util.Queue<java.lang.String> parse(java.lang.String expression)
```
    Description copied from class: ATree
    
    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.
    
    Specified by:
    
    parse in class ATree
    
    Parameters:
    
    expression - a valid expression
    
    Returns:
    
    expression in infix order
  - convert
```
public java.util.List<java.lang.String> convert(java.util.Queue<java.lang.String> infix)
```
    Description copied from class: ATree
    
    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 ATree.isOperator(String), ATree.isInteger(String), and ATree.precedence(String).
    Our implementation is ~21 lines of code.
    
    Specified by:
    
    convert in class ATree
    
    Parameters:
    
    infix - expression in infix order
    
    Returns:
    
    expression in postfix order
  - build
```
public void build(java.util.List<java.lang.String> postfix)
```
    Description copied from class: ATree
    
    Calls a recursive helper method to build an expression tree from a postfix List.
    
    Specified by:
    
    build in class ATree
    
    Parameters:
    
    postfix - the expression tree
  - buildRecursive
```
public boolean buildRecursive(ATree.Node current,
                              java.lang.String token)
```
    Builds an expression tree from the postfix representation returned from the convert method. To build the correct tree, pull tokens from List<String> postfix, and places them at the next available node in the tree. Here is the exact algorithm:
    1. If the tree root is null, create a new node containing the token, assign it to the root, and return true.
    2. If the right child of the current node is null, create a new node with the token, place it in the right child, and return true.
    3. If the right child of the current node is an operator, make a recursive call passing the right child and token, and return true if successful, otherwise continue.
    4. If the left child of the current node is null, create a new node with the token, place it in the left child, and return true.
    5. If the left child of the current node is an operator, make a recursive call passing the left child and token, and return true if successful, otherwise continue.
    6. If none of the above code returns true, then the code has failed to add the token to the tree, so return false.
    Our implementation of the recursive method is ~19 lines of code
    Parameters:
    
    current - the current Node being checked
    
    token - the token to add
    
    Returns:
    
    true, if successful
  - prefix
```
public java.lang.String prefix()
```
    Description copied from class: ATree
    
    Calls a recursive helper method to traverse the expression tree in prefix order and build expression.
    
    Specified by:
    
    prefix in class ATree
    
    Returns:
    
    a string representing the expression in prefix order.
  - prefixRecursive
```
public java.lang.String prefixRecursive(ATree.Node current)
```
    Concatenates the tokens in the expression tree returned from the build(List) method in prefix order.
    Accumulate the operator first, then the string from the left and right subtrees. Add an extra space after each token.
    Our implementation of this method is ~2-6 lines of code.
    
    Parameters:
    
    current - the root node
    
    Returns:
    
    the tokens in prefix order
  - infix
```
public java.lang.String infix()
```
    Description copied from class: ATree
    
    Calls a recursive helper method to traverse the expression tree in infix order and build the expression.
    
    Specified by:
    
    infix in class ATree
    
    Returns:
    
    a string representing the expression infix order.
  - infixRecursive
```
public java.lang.String infixRecursive(ATree.Node current)
```
    Concatenates the tokens in the expression tree returned from the build(List) method in infix order.
    1. Accumulate the string from the left subtree
    2. Add the operator
    3. Accumulate the string from the right subtree
    This method should add parentheses to maintain the correct evaluation order, add a left parentheses before traversing the left subtree, and a right parentheses after traversing the right subtree. Do not add any space to the expression string.
    Our implementation of this method is ~2-6 lines of code.
    Parameters:
    
    current -
    
    Returns:
    
    the tokens in infix order
  - postfix
```
public java.lang.String postfix()
```
    Description copied from class: ATree
    
    Calls a recursive helper method to traverse the expression tree in postfix order and build the expression.
    
    Specified by:
    
    postfix in class ATree
    
    Returns:
    
    a string representing the expression in postfix order.
  - postfixRecursive
```
public java.lang.String postfixRecursive(ATree.Node current)
```
    Concatenates the tokens in the expression tree returned from the build(List) method in postfix order. First accumulate the string from the left and right subtrees, then add the operator. Add an extra space after each token.
    Our implementation of this method is ~2-6 lines of code.
    
    Parameters:
    
    current - reference to the current node (starts with root)
    
    Returns:
    
    a String representing the tree in postfix order
  - evaluate
```
public int evaluate()
```
    Description copied from class: ATree
    
    Calls a recursive helper method to evaluate expression tree and return the result.
    
    Specified by:
    
    evaluate in class ATree
    
    Returns:
    
    the result of the expression.
  - evaluateRecursive
```
public int evaluateRecursive(ATree.Node current)
```
    Traverses the expression tree and produces the correct answer, which should be an integer. To evaluate, call the recursive version of the method to get the result from the left subtree, do the same for the right subtree, then combine these two results using the operator. A case statement based on the operator is needed to perform the mathematical operation.
    Our implementation uses one helper method (~7 lines of code) and is, itself, ~2 lines of code.
    
    Parameters:
    
    current -
    
    Returns:

CSU CS165

Class ExpressionTree

Nested Class Summary

Nested classes/interfaces inherited from class ATree

Field Summary

Fields inherited from class ATree

Constructor Summary

Method Summary

Methods inherited from class ATree

Methods inherited from class java.lang.Object

Constructor Detail

ExpressionTree

Method Detail

parse

convert

build

buildRecursive

prefix

prefixRecursive

infix

infixRecursive

postfix

postfixRecursive

evaluate

evaluateRecursive

CSU CS165