Assignment 

The second programming project involves writing a program that accepts an arithmetic
expression of unsigned integers in postfix notation and builds the arithmetic expression tree that
represents that expression. From that tree, the corresponding fully parenthesized infix expression
should be displayed and a file should be generated that contains the three address format
instructions. The mainclass should create the GUI shown below:

The GUI must be generated by code that you write. You may not use a drag-and-drop GUI
generator.
Pressing the Construct Tree button should cause the tree to be constructed and using that tree, the
corresponding infix expression should be displayed and the three address instruction file should
be generated.
The postfix expression input should not be required to have spaces between every token. Note in
the above example that 9+- are not separated by spaces.
The above example should produce the following output file containing the three address
instructions:
Add R0 5 9
Sub R1 3 R0
Mul R2 2 3
Div R3 R1 R2
It is not necessary to reuse registers within an expression as shown in module 2, section II-B, and
you can assume there are as many available as needed. Each new expression should, however,
begin using registers starting at R0.
Inheritance should be used to define the arithmetic expression tree. At a minimum, it should
involve three classes: an abstract class for the tree nodes and two derived classes, one for
operand nodes and another for operator nodes. Other classes should be included as needed to
accomplish good object-oriented design. All instance data must be declared as private.
You may assume that the expression is syntactically correct with regard to the order of operators
and operands, but you should check for invalid tokens, such as characters that are not valid
operators or operands such as 2a, which are not valid integers. If an invalid token is detected a RuntimeExceptionshould be thrown and caught by the main class and an appropriate error
message should be displayed. Below is an example:

Solution

ExpressionTree.java

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

packagetreeaddressgenerator;

importjava.util.ArrayList;

importjava.util.Stack;

public class ExpressionTree {

private Node RootNode;

private String normalizePostixExpression(String postfixExpression)

{

returnpostfixExpression.replace(” “, “”);

}

public void buildTree(String postfixExpression) throws InvalidTokenException

{

String tokens = normalizePostixExpression(postfixExpression);

Stack<Node>nodeStack = new Stack();

Node current, left, right;

for (int i = 0; i <tokens.length(); i++)

{

String token = Character.toString(tokens.charAt(i));

if (token.isEmpty())

{

continue;

}

// If operand, simply push into stack

if (!OperatorNode.SupportedOperators().contains(token))

{

try {

Integer.parseInt(token);

} catch (NumberFormatException e)

{

String errorMessage = new String(“Invalid token “);

errorMessage += token;

throw new InvalidTokenException(errorMessage);

}

current = new OperandNode(token);

nodeStack.push(current);

}

else

{

current = new OperatorNode(token);

right = nodeStack.pop();

left = nodeStack.pop();

current.setLeft(left);

current.setRight(right);

nodeStack.push(current);

}

}

RootNode = nodeStack.peek();

nodeStack.pop();

}

/**

* @return the RootNode

*/

public Node root()

{

returnRootNode;

}

} 

InvalidTokenException.java 

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

packagetreeaddressgenerator;

public class InvalidTokenException extends Exception{

publicInvalidTokenException(String message)

{

super(message);

}

} 

Node.java 

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

packagetreeaddressgenerator;

importjava.util.ArrayList;

// abstract class for all ‘expression tree’ nodes (‘operand’ and ‘operators’)

public abstract class Node

{

private Node LeftNode;

private Node RightNode;

private String NodeToken;

public Node(String token)

{

NodeToken = token;

}

public String token()

{

returnNodeToken;

}

public Node left()

{

returnLeftNode;

}

public void setLeft(Node node)

{

LeftNode = node;

}

public Node right()

{

returnRightNode;

}

public void setRight(Node node)

{

RightNode = node;

}

// method convert current node into infix string

// 1. for that we take left expression (it exists only for operator)

// 2. write token (it can be operator or operand)

// 3. and right expression (only if current node is operator)

// E.g.

// for operator node ‘+’ and operands (left)’a’, (right)’be’

// we’ll give

// 1. ( a

// 2. ( a +

// 3. ( a + b ) – this expression will be returned

// for simple operand node ‘a’

// Follwing workflow:

// 1. none – no left leave

// 2. a – own token value

// 3. none – no right leave

// ‘a’ string will be returned

public String toString()

{

String nodeAsString = new String(“”);

if (left() != null)

{

if (left().left() == null)

{

nodeAsString += “(“;

}

nodeAsString += ” “;

nodeAsString += left().toString();

}

nodeAsString += token();

if (right() != null)

{

nodeAsString += right().toString();

nodeAsString += ” “;

if (right().right() == null)

{

nodeAsString += “)”;

}

}

returnnodeAsString;

}

// abstract method which have different implementation in derived classes

// prepare set of strings for output into instructions file

public abstract Integer exportInstructions(Integer currentRegistry,

ArrayList<String> instructions);

} 

OperandNode.java 

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

packagetreeaddressgenerator;

importjava.util.ArrayList;

public class OperandNode extends Node

{

publicOperandNode(String token)

{

super(token);

}

// operator node doesn’t generate output instruction

@Override

public Integer exportInstructions(Integer currentRegistry, ArrayList<String> instructions)

{

returncurrentRegistry;

}

} 

OperatorNode.java 

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

packagetreeaddressgenerator;

importjava.util.ArrayList;

importjava.util.HashMap;

importjava.util.Map;

importjava.util.Objects;

public class OperatorNode extends Node

{

// define all supported operators

private static ArrayList<String> Operators = new ArrayList<String>() {{

add(“+”);

add(“-“);

add(“*”);

add(“/”);

}};

// convert supported operators into instruction

private static Map<String, String>OperatorToInstruction = new HashMap<String, String>() {{

put(“+”, “Add”);

put(“-“, “Sub”);

put(“*”, “Mul”);

put(“/”, “Div”);

}};

staticArrayList<String>SupportedOperators()

{

return Operators;

}

publicOperatorNode(String token)

{

super(token);

}

// operand node generates output instruction

// current registry is input registry number which used for calculation of current node

@Override

public Integer exportInstructions(Integer currentRegistry, ArrayList<String> instructions)

{

// each operator node has left and right child

String leftOperand = left().token(); // guess that left child is simple operand

if (left() != null)

{

Integer registryValueBeforeExport = currentRegistry; // remember ‘currentRegistry’ value

// request instructions export from left child

// if left child is operator it’ll add instruction and modify registry count value

Integer registryValueAfterExport = left().exportInstructions(currentRegistry, instructions);

if (!Objects.equals(registryValueBeforeExport, registryValueAfterExport))

{

// if registry value was modified the result was saved in

// registry ‘registryValueAfterExport – 1’

currentRegistry = registryValueAfterExport;

leftOperand = “R” + (registryValueAfterExport – 1);

}

}

String rightOperand = right().token(); // guess that right child is simple operand

if (right() != null)

{

Integer registryValueBeforeExport = currentRegistry;

// request instructions export from right child

// if right child is operator it’ll add instruction and modify registry count value

Integer registryValueAfterExport = right().exportInstructions(currentRegistry, instructions);

if (!Objects.equals(registryValueBeforeExport, registryValueAfterExport))

{

// if registry value was modified the result was saved in

// registry ‘registryValueAfterExport – 1’

currentRegistry = registryValueAfterExport;

rightOperand = “R” + (registryValueAfterExport – 1);

}

}

// convert token into instruction

String instruction = OperatorToInstruction.get(token());

// add free registry value

instruction += ” R” + currentRegistry + ” “;

// add left and right operands

instruction += leftOperand + ” ” + rightOperand;

instructions.add(instruction);

returncurrentRegistry + 1;

}

}

 TreeAddressGenerator.java

 /*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

packagetreeaddressgenerator;

import java.io.*;

importjava.util.ArrayList;

importjava.util.logging.Level;

importjava.util.logging.Logger;

importjavafx.application.Application;

importjavafx.event.ActionEvent;

importjavafx.event.EventHandler;

importjavafx.scene.Scene;

importjavafx.geometry.Insets;

importjavafx.geometry.Pos;

importjavafx.scene.control.*;

importjavafx.scene.layout.*;

importjavafx.stage.Stage;

public class TreeAddressGenerator extends Application {

privateTextFieldPostfixExpression;

privateTextFieldInfixExpression;

@Override

public void start(Stage primaryStage)

{

Label label1 = new Label();

label1.setAlignment(Pos.BASELINE_RIGHT);

label1.setText(“Enter Postfix Expression”);

Label label2 = new Label();

label2.setAlignment(Pos.BASELINE_RIGHT);

label2.setText(“Infix Expression”);

PostfixExpression = new TextField();

PostfixExpression.setPrefColumnCount(20);

PostfixExpression.setPromptText(“Enter expression”);

InfixExpression = new TextField();

InfixExpression.setPrefColumnCount(20);

InfixExpression.setEditable(false);

Button btn = new Button();

btn.setText(“Construct Tree”);

btn.setOnAction(new EventHandler<ActionEvent>() {

@Override

public void handle(ActionEvent event) {

String postfixExpression = PostfixExpression.getText();

try

{

ExpressionTreeexpressionTree = new ExpressionTree();

expressionTree.buildTree(postfixExpression);

Node root = expressionTree.root();

InfixExpression.setText(root.toString());

ArrayList<String> instructions = new ArrayList<String>();

root.exportInstructions(0, instructions);

try {

BufferedWriter out = new BufferedWriter(new FileWriter(“instructions.txt”));

for (String instruction : instructions)

{

out.write(instruction + “\n”);

}

out.close();

}

catch (IOException ex)

{

}

}

catch(InvalidTokenException e)

{

Alert alert = new Alert(Alert.AlertType.INFORMATION);

alert.setTitle(“Message”);

alert.setHeaderText(null);

alert.setContentText(e.getMessage());

alert.showAndWait();                }

}

});

GridPane grid = new GridPane();

grid.setPadding(new Insets(10, 10, 10, 10));

grid.setVgap(12);

grid.setHgap(10);

grid.add(label1, 0, 0);

grid.add(PostfixExpression, 1, 0);

grid.add(btn, 1, 1);

grid.add(label2, 0, 2);

grid.add(InfixExpression, 1, 2);

Scene scene = new Scene(grid, 400, 120);

primaryStage.setTitle(“Three Address Generator”);

primaryStage.setScene(scene);

primaryStage.show();

}

/**

* @paramargs the command line arguments

*/

public static void main(String[] args) {

launch(args);

}

}