Design, write and test a program that accepts an arithmetic expression of unsign

Question

Design, write and test a program that accepts an arithmetic expression of unsigned integers in postfix notation in which the tokens are separated by spaces and builds and processes the arithmetic expression tree that represents that expression. The main class will be P2GUI. It should create a Swing based 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 following:

(i)the arithmetic expression tree that represents the entered postfix expression will be constructed

(ii) using that tree, the corresponding fully parenthesized

infix expression should be generated and displayed in the GUI and finally

(iii) a file should be generated that contains the 3-address format instructions corresponding to the arithmetic expression.

These topics, including relevant classes for implementing and processing an expression tree, are discussed in the week 4 reading “Binary Trees, Expression Trees, BST (AVL) trees, and B-Trees” section II “Expression Trees”.

The above example should produce the following output file containing the3-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 the above mentioned reading and you can assume there are as many available registers as needed. Each new expression should, however, begin using registers starting at R0.

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 checked custom exception "InvalidTokenException" should be thrown and caught by the main class and an appropriate error message should be displayed in an "JOptionPane". Below is an example:

Your program should compile without errors.

For building the expression tree from the postfix expression you have to:

1. Define a Stack of type Node, i.e. Stack<Node>

2. Tokenize the postfixExpression (use the space character " " as separator)

3. Read next token

3.1 If the token is a numeric value => generate an OperandNode and push it on the stack

3.2 If the token is an operator => generate an OperatorNode. An OperatorNode is defined by a reference to Operator (i.e. AddOperator, SubOperator, etc.) and two references to the left and right subtrees of the OperatorNode. The references to the left and right subtrees should be obtained by pop-ing two Nodes from the Stack<Node>. Push the reference to the generated OperatorNode on the Stack<Node>

4. Repeat step 3 for all tokens of the postfixExprssion.

5. At the end the stack will contain only one Node(a reference to that node) which is the root of the expression tree corresponding to the postfix expression given as parameter.

Explanation / Answer

// Java core packages
import java.awt.*;
import java.awt.event.*;
import java.util.*;
// Java extension packages
import javax.swing.*;
class InfixToPostfixConverter extends JFrame
{
private JLabel prompt, postfixLabel;
private JTextField infixField, postfixField;
// set up GUI
public InfixToPostfixConverter()
{
prompt = new JLabel("Enter infix arithmetic expression: ");
infixField = new JTextField( 20 );
infixField.addActionListener(
new ActionListener() {
public void actionPerformed( ActionEvent event )
{
// call convertToPostfix
StringBuffer input = new StringBuffer(
infixField.getText() );
postfixField.setEnabled( true );
postfixField.setText( convertToPostfix(
input ).toString() );
postfixField.setEditable( false );
}
}
);
postfixLabel = new JLabel("Expression in postfix notation: " );
postfixField = new JTextField( 20 );
postfixField.setEnabled( false );
Container container = getContentPane();
container.setLayout( new FlowLayout() );
container.add( prompt );
container.add( infixField );
container.add( postfixLabel );
container.add( postfixField );
setSize( 260, 150 );
show();
}
// convert expression
public StringBuffer convertToPostfix( StringBuffer infix )
{
StringBuffer postfix = new StringBuffer();
Stack stack = new Stack();
stack.push( new Character( '(' ) );
infix.append( ")" );
int index = 0;
// convert expression
while( !stack.isEmpty() ) {
char temp = infix.charAt( index );
// digits
if ( Character.isDigit( temp ) )
postfix.append( temp );
// left parenthesis
else if ( temp == '(' )
stack.push( new Character( temp ) );
// operators
else if ( isOperator( temp ) ) {
char top =
( ( Character ) stack.peek() ).charValue();
while ( isOperator( top ) &&
!precedence( top, temp ) ) {
postfix.append(
( ( Character) stack.pop() ).charValue() );
top = ( ( Character ) stack.peek() ).charValue();
}
stack.push( new Character( temp ) );
}
// right parenthesis
else {
while ( ( ( Character ) stack.peek() ).charValue()
!= '(' )
postfix.append(
( ( Character ) stack.pop() ).charValue() );
stack.pop();
}
index++;
}
return postfix;
} // end method convertToPostfix
// determine if c is an operator
public boolean isOperator( char c )
{
if ( c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^' || c == '%' )
return true;
return false;
}
// return true if operator1 has
// lower precedence than operator2
public boolean precedence( char operator1, char operator2 )
{
if ( ( operator1 == '+' || operator1 == '-' ) &&
operator2 != '+' && operator2 != '-' )
return true;
else if ( operator1 != '^' && operator2 == '^' )
return true;
return false;
}
// execute application
public static void main( String args[] )
{
P2GUI application =
new P2GUI();
application.setDefaultCloseOperation(
JFrame.EXIT_ON_CLOSE );
}
} // end class InfixToPostfixConverter

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.