Create an Expression Tree from a Valid Algebraic Expression

packagecsu.matos;

importjava.util.Stack;

importjava.util.StringTokenizer;

publicclass Driver {

/**

* GOAL: 1. Parse an arithmetical expression. 2. Create an equivalent

* 'binary expression tree' 3. Traverse the tree in 'Post-Order', 'In-Order'

Stack<Node<Character> stack = new Stack<Node<Character>();

publicstaticvoid main(String[] args) {

// Provide a correct infix expression to be converted

String expression = "(1+3/4*5-6)-7";

try {

String postfixExp = infixToPostfix(expression);

System.out.println(postfixExp);

Node<String> root = evaluateExpression(postfixExp);

Tree<String> tree = new Tree<String>(root);

tree.printTree();

System.out.println("BFS");

tree.bfs();

System.out.println("INORDER");

tree.inOrder(root);

System.out.println("POSTORDER");

tree.postOrder(root);

System.out.println("PRE-ORDER");

tree.preOrder(root);

} catch (Exception ex) {

System.out.println("Wrong expression");

}

// ------

publicstatic Node<String> evaluateExpression(String postfixExp) {

// CreateoperandStack to store operands

Stack<Node<String> operandStack = new Stack<Node<String>();

// Extract operands and operators

StringTokenizertokens = newStringTokenizer(postfixExp, " +-/*%", true);

// Phase 1: Scan tokens

Node<String> root = null;

while (tokens.hasMoreTokens()) {

String token = tokens.nextToken().trim(); // Extract a token

if (token.length() == 0) { // Blank space

continue; // Back to the while loop to extract the next token

} elseif (token.charAt(0) == '+' || token.charAt(0) == '-'

|| token.charAt(0) == '*' || token.charAt(0) == '/') {

root = processAnOperator(token.charAt(0), operandStack);

} else{ // An operand scanned

// Push an operand to the stack

root = operandStack.push(new Node<String>(token));

}

// Return the result

returnroot;

}

// Process one operator: Take an operator from operatorStack and

// apply it on the operands in the operandStack

publicstatic Node<String> processAnOperator(charop, Stack<Node<String> operandStack) {

Node<String> operatorNode = null;

if (op == '+') {

operatorNode = connectArgs2Operator("+", operandStack);

} elseif (op == '-') {

operatorNode = connectArgs2Operator("-", operandStack);

} elseif ((op == '*')) {

operatorNode = connectArgs2Operator("*", operandStack);

} elseif (op == '/') {

operatorNode = connectArgs2Operator("/", operandStack);

}

returnoperatorNode;

}//processAnOperator

// ------

privatestatic Node<String> connectArgs2Operator(

String operatorSymbol,

Stack<Node<String> operandStack) {

Node<String> rightArg = operandStack.pop();

Node<String> leftArg = operandStack.pop();

Node<String> operatorNode = new Node<String> (operatorSymbol);

operatorNode.setLeft(leftArg);

operatorNode.setRight(rightArg);

operandStack.push(operatorNode);

returnoperatorNode;

}

// ------

// use this method to convert from infix to postfix

publicstatic String infixToPostfix(String expression) {

// Result string

String s = "";

// CreateoperatorStack to store operators

Stack<Character> operatorStack = new Stack<Character>();

// Extract operands and operators

StringTokenizertokens = newStringTokenizer(expression, "()+-/*%",

true);

// Phase 1: Scan tokens

while (tokens.hasMoreTokens()) {

String token = tokens.nextToken().trim(); // Extract a token

if (token.length() == 0) { // Blank space

continue; // Back to the while loop to extract the next token

} elseif (token.charAt(0) == '+' || token.charAt(0) == '-') {

// remove all +, -, *, / on top of the operator stack

while (!operatorStack.isEmpty()

& (operatorStack.peek().equals('+')

|| operatorStack.peek().equals('-')

|| operatorStack.peek().equals('*') || operatorStack

.peek().equals('/'))) {

s += operatorStack.pop() + " ";

}

// push the incoming + or - operator into the operator stack

operatorStack.push(new Character(token.charAt(0)));

} elseif (token.charAt(0) == '*' || token.charAt(0) == '/') {

// remove all *, / on top of the operator stack

while (!operatorStack.isEmpty()

& (operatorStack.peek().equals('*') || operatorStack

.peek().equals('/'))) {

s += operatorStack.pop() + " ";

}

// Push the incoming * or / operator into the operator stack

operatorStack.push(new Character(token.charAt(0)));

} elseif (token.trim().charAt(0) == '(') {

operatorStack.push(new Character('(')); // Push '(' to stack

} elseif (token.trim().charAt(0) == ')') {

// remove all the operators from the stack until seeing '('

while (!operatorStack.peek().equals('(')) {

s += operatorStack.pop() + " ";

}

operatorStack.pop(); // Pop the '(' symbol from the stack

} else{ // An operand scanned

// Push an operand to the stack

s += token + " ";

}

// Phase 2: remove the remaining operators from the stack

while (!operatorStack.isEmpty()) {

s += operatorStack.pop() + " ";

}

// Return the result

returns;

}// main

}

NODE

packagecsu.matos;

publicclass Node<E extends Comparable<E> > {

Node<E> left;

Node<E> right;

E data;

public Node( E data ) {

super();

this.left = null;

this.right = null;

this.data = data;

}

public Node<E> getLeft() {

returnleft;

}

publicvoidsetLeft(Node<E> left) {

this.left = left;

}

public Node<E> getRight() {

returnright;

}

publicvoidsetRight(Node<E> right) {

this.right = right;

}

public E getData() {

returndata;

}

publicvoidsetData(E data) {

this.data = data;

}

// use only for DEBUGGING

publicvoidprintNode() {

String result= (this)

+ ": Node ["+ " data=" + data

+ ",\t left=" + (left)

+ ",\t right=" + (right)

+ "]";

System.out.println(result );

}

TREE

packagecsu.matos;

importjava.util.LinkedList;

importjava.util.Queue;

publicclass Tree <E extends Comparable<E> >{

publicvoidprintTree() {

System.out.println("Tree [root=" + root + "]" );

}

Node<E> root;

public Tree() {

this.root= null;

}

public Tree(Node<E> root) {

this.root= root;

}

public Node<E> getRoot() {

returnroot;

}

publicvoidsetRoot(Node<E> root) {

this.root = root;

}

//------

publicvoidaddNode( E data ){

Node<E> newNode = new Node<E>(data );

if ( root == null ){

root = newNode;

return;

}

Node<E> ptr = root;

Node<E> parent = null;

booleancomingFromLeft = true;

while(ptr != null ){

parent = ptr;

if ( ptr.getData().compareTo(newNode.getData()) > 0) {

ptr = ptr.getLeft();

comingFromLeft = true;

}else {

ptr = ptr.getRight();

comingFromLeft = false;

}

}//while

if(comingFromLeft ){

parent.setLeft(newNode );

} else {

parent.setRight(newNode );

}

}//addNode

publicvoidinOrder(Node<E> ptr ){

if ( ptr != null ){

inOrder(ptr.getLeft() );

ptr.printNode();

inOrder(ptr.getRight() );

}

publicvoidpreOrder(Node<E> ptr ){

if ( ptr != null ){

ptr.printNode();

preOrder(ptr.getLeft() );

preOrder(ptr.getRight() );

}

publicvoidpostOrder(Node<E> ptr ){

if ( ptr != null ){

postOrder(ptr.getLeft() );

postOrder(ptr.getRight() );

ptr.printNode();

}

public Node<E> find (E searchValue){

Node<E> ptr = root;

while(ptr != null ){

if(ptr.getData().compareTo(searchValue) == 0 ){

returnptr;

}

if(ptr.getData().compareTo(searchValue) > 0 ){

ptr = ptr.getLeft();

}else {

ptr = ptr.getRight();

}

returnnull;

}//find

// ------

publicvoidbfs(){

System.out.print("\nBFS\n");

Queue<Node<E> queue = newLinkedList<Node<E>();

queue.add(root);

while ( !queue.isEmpty() ){

Node<E> ptr = queue.remove();

//System.out.print(ptr.getData() + ", ");

ptr.printNode();

if ( ptr.getLeft()!= null ) queue.add(ptr.getLeft() );

if ( ptr.getRight()!= null ) queue.add(ptr.getRight() );

}

}//class

CONSOLE

1 3 4 / 5 * + 6 - 7 -

Tree [root=csu.matos.Node@19d1b44b]

BFS

csu.matos.Node@19d1b44b: Node [ data=-, left=csu.matos.Node@2dd7e4d6, right=csu.matos.Node@38f0b51d]

csu.matos.Node@2dd7e4d6: Node [ data=-, left=csu.matos.Node@4302a01f, right=csu.matos.Node@615e7597]

csu.matos.Node@38f0b51d: Node [ data=7, left=null, right=null]

csu.matos.Node@4302a01f: Node [ data=+, left=csu.matos.Node@7a3e72, right=csu.matos.Node@5999ae9c]

csu.matos.Node@615e7597: Node [ data=6, left=null, right=null]

csu.matos.Node@7a3e72: Node [ data=1, left=null, right=null]

csu.matos.Node@5999ae9c: Node [ data=*, left=csu.matos.Node@7896b1b8, right=csu.matos.Node@6d6de4e1]

csu.matos.Node@7896b1b8: Node [ data=/, left=csu.matos.Node@49cda7e7, right=csu.matos.Node@5cca548b]

csu.matos.Node@6d6de4e1: Node [ data=5, left=null, right=null]

csu.matos.Node@49cda7e7: Node [ data=3, left=null, right=null]

csu.matos.Node@5cca548b: Node [ data=4, left=null, right=null]

INORDER