Homework SourseWrite a program that accepts an arithmetic expression of uns
Write 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. This topic is discussed in the week 4 reading in module 2, section II-B. The main class should create the GUI shown below:
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
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 RuntimeException should be thrown and caught by the main class and an appropriate error message should be displayed.
Three Adddress Generator Enter Postfix Expression 359 2 3 Construct Tree Infix Expression ((3-(5 9))/ (2* 3Solution
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct TREE //Structure to represent a tree
{
char data;
struct TREE *right,*left,*root;
};
typedef TREE tree; /* Stack Using Linked List */
struct Stack //Structure to represent Stack
{
struct TREE *data;
struct Stack *next,*head,*top; //Pointers to next node,head and top
};
typedef struct Stack node;
node *Nw; //Global Variable to represent node
void initialize(node *&n)
{
n = new node;
n -> next = n -> head = n -> top = NULL;
}
void create(node *n)
{
Nw = new node; //Create a new node
Nw -> next = NULL; //Initialize next pointer field
if(n -> head == NULL) //if first node
{
n -> head = Nw; //Initialize head
n -> top = Nw; //Update top
}
}
void push(node *n,tree *ITEM)
{
node *temp = n -> head;
if(n -> head == NULL) //if First Item is Pushed to Stack
{
create(n); //Create a Node
n -> head -> data = ITEM; //Insert Item to head of List
n -> head = Nw;
return; //Exit from Function
}
create(n); //Create a new Node
Nw -> data = ITEM; //Insert Item
while(temp -> next != NULL)
temp = temp -> next; //Go to Last Node
temp -> next = Nw; //Point New node
n -> top = Nw; //Update top
}
node* pop(node *n)
{
node *temp = n -> head,*deleted;
if(n -> top == NULL) //If the Stack is Empty
{
return NULL;
}
if(n -> top == n -> head) //If only one Item
{
deleted = n -> head;
n -> head = n -> top = NULL; //Set head and top to Null
return deleted; //Return deleted node
}
while(temp -> next != n -> top)
temp = temp -> next; //move pointer temp to second last node
temp -> next = NULL; //Second last node points to NULL
deleted = n -> top; //Save topmost node
n -> top = temp; //Update top
return deleted; //Return deleted node
}
int Empty(node *nd) //function to check if the stack is empty or not
{
if(nd -> top == NULL)
return 1; //empty
else
return 0;
}
/*Tree Section */
tree *New;
void create() //Function to create a node of a tree
{
New = new tree;
New -> left = NULL;
New -> right = NULL;
}
void insert(tree *&t,char Item,int pass) //Function to insert item on a tree
{
if(t == NULL) //If tree doesn\'t exist
{
t = new tree; //make a node
t -> data = Item; //insert item
t -> left = NULL; //initialize left pointer
t -> right = NULL; //initialize right pointer
if(pass)
t -> root = t; //initialize root
return; //return from function
}
create();
New -> data = Item;
}
void preorder(tree *t) //Function to print tree in preorder
{
if(t != NULL)
{
cout << t -> data << \' \';
preorder(t -> left);
preorder(t -> right);
}
}
void inorder(tree *t) //Function to print tree in inorder
{
if(t != NULL)
{
inorder(t -> left);
cout << t -> data << \' \';
inorder(t -> right);
}
}
int isOperator(char ch) /* Main Program */
{
if(ch == \'+\' || ch == \'-\' || ch == \'*\' || ch == \'/\' || ch == \'$\')
return 1;
else
return 0;
}
bool check(node *nd)
{
if(nd != NULL)
return true;
else
return false;
}
float calculate(float opr1,float opr2,char oprator)
{
float value;
if(oprator == \'+\')
value = opr1 + opr2;
if(oprator == \'-\')
value = opr1 - opr2;
if(oprator == \'*\')
value = opr1 * opr2;
if(oprator == \'/\')
if(opr2 != 0)
value = opr1 / opr2;
if(oprator == \'$\')
value = pow(opr1,opr2);
return value;
}
float evaluate(tree *t)
{
float x,y,result;
char ch[3];
if(t != NULL)
{
if(isOperator(t -> data))
{
x = evaluate(t -> left); //go to left
y = evaluate(t -> right); //go to right
result = calculate(x,y,t -> data); //calculate
return result;
}
else
{
ch[0] = t -> data;
ch[1] = \'\\0\';
result = atof(ch); //convert to float
return result;
}
}
}
int main()
{
char postfix[60];
cout << \"Enter a valid Postfix Expression\ \";
cout << \"(in a single line, without spaces)\ \";
int i = 0;
while(postfix[i - 1] != \'\ \')
postfix[i++] = getchar();
int len = i - 1,pass = true,valid = true;
node *stk,*nd; //create a stack
initialize(stk);
tree *tr = NULL,*value;
i = 0;
while(i < len) //while there is data
{
if(!isOperator(postfix[i])) //if operand
{
create();
New -> data = postfix[i];
push(stk,New); //push address of tree node to stack
}
else //if operator
{
insert(tr,postfix[i],pass); //create a node of tree and insert operator
if(pass) //if first pass
{
nd = pop(stk);
valid = check(nd);
if(!valid)
break;
value = nd -> data; //pop address
tr -> right = value; //assign to left child
nd = pop(stk);
valid = check(nd);
if(!valid)
break;
value = nd -> data; //pop address
tr -> left = value; //assign to right child
pass = false; //reset pass
push(stk,tr); //push address to stack
}
else
{
nd = pop(stk);
valid = check(nd);
if(!valid)
break;
value = nd -> data; //pop address
New -> right = value; //assign to left child
nd = pop(stk);
valid = check(nd);
if(!valid)
break;
value = nd -> data; //pop stack
New -> left = value; //assign to right child
push(stk,New); //push address to stack
}
}
i++; //update i
}
if(!Empty(stk))
{
tr -> root = pop(stk) -> data; //Last data of stack is root of tree
tr = tr -> root;
}
if(!Empty(stk)) //if stack is not empty
valid = false;
if(!valid)
{
cout << \"\ The Given Postfix Expression is not Valid\";
cout << \"\ Check above Expression and try again...\";
getch();
return 0; //exit from program
}
cout << \"\ Infix : \";
inorder(tr); //Inorder traversal gives Infix of expression
cout << \"\ \ Prefix : \";
preorder(tr); //Postorder traversal gives Postfix of expression
float result = evaluate(tr);
cout << endl << \"\ Solution : \" << result;
getch();
return 0;
}
