Question

In Java:

Problem 1.

Write a program that performs the following two tasks:

1. Reads an arithmetic expression in an infix form, stores it in a queue (infix queue) and converts it to a postfix form (saved in a postfix queue).

2. Evaluates the postfix expression.

Use the algorithms described in class/ lecture notes. Use linked lists to implement the Queue and Stack ADTs. Using Java built-in classes will result in 0 points. You must use your own Stack and Queue classes (my code is a good starting point). Submit the code + example runs to validate your code. Submit UML chart to show the program design.

Problem 2.

Given the following postorder and inorder traversals of a binary tree, draw the tree:

Postorder: A B C D E F I K J G H

Inorder: C B A E D F H I G K J

Explain your answer in a systematic and recursive fashion.

Answer 1

CONSTRUCTION OF BINARY TREE

****THE FOLLOWING RECURSIVE FUNCTION IMPLEMENTS THE SAME*****

Node* construct(int inorder[], int postorder[], int Start, int End, int* Index)
{

if (Start > End)
return NULL;
  
// Pick current node from Postorder traversal using
// Index and decrement Index
Node* node = newNode(post[*Index]);
(*Index)--;
  
// If this node has no children then return
if (Start == End)
return node;
  
//Else find the index of this node in Inorder
// traversal
int iIndex = search(in, Start, End, node->data);
  
// Using index in Inorder traversal, construct left and
// right subtress
node->right = construct(inorder, postorder, iIndex + 1, End, Index);
node->left = construct(in, post, Start, iIndex - 1, Index);
  
return node;
}