Hi I need some help explaning this code essentially I need these parts of the co
ID: 3855437 • Letter: H
Question
Hi I need some help explaning this code essentially I need these parts of the code commented to understand it. This essentially is the section of logic that makes the program run. I need to understand this logic as it is the warm up for another project later on.
This is how I got the code as I asked this question earlier if it helps you understand:
****I need a Java program that reads in a postfix expression, splits it into an array of strings and does just this so I can fully understand this excercise. It needs to deal correctly with parenthesized sub-expressions and operator precedence. A tree needs to be built to take the grammatical subtleties of the expression into account. Thank you!!!!
Evaluate a reverse polish (postfix) expression such as
2 * (3 + 4) + 5
then this will be parsed into a tree, and then the output in reverse polish notation (postfix notation) such as
2 3 4 + * 5 +
This can be interpreted by reading it from left to right once you see a number you can then push it on the stack, and when you see an operator, pop the right operand off the stack into a variable(r) and then pop the left operand off the stack into a variable(l), then using a switch on the operator combine (l) with (r) using the operator and push the result back onto the stack.
Essentially this can be completed by creating various parts in different classes of a tree i.e a stack, node, operatorenode, number node.
This excercise should be very simple but I just do not understand it I need help creating the program to understand this as my next project does need me to understand this. Thank You so much****
Ouput
---------------
Enter the Expression
2*(3+4) + 5
Preorder Traversal:- *2+34
Inorder Traversal:- 2*3+4
Postorder Traversal:- 234+*
Enter y to continue y
Enter the Expression
3+(2+3)
Preorder Traversal:- +3+23
Inorder Traversal:- 3+2+3
Postorder Traversal:- 323++
Enter y to continue n
---------------------------------------
public class Tree
{
private TreeNode rootNode;
public Tree()
{
rootNode = null;
}
public void insert(String s)
{
Conversion c = new Conversion(s);
s = c.infixToPost();
MyStack1 stk = new MyStack1(s.length());
s = s + "#";
int i = 0;
char symbol = s.charAt(i);
TreeNode newNode;
while (symbol != '#')
{
if (symbol >= '0' && symbol <= '9' || symbol >= 'A'
&& symbol <= 'Z' || symbol >= 'a' && symbol <= 'z')
{
newNode = new TreeNode(symbol);
stk.push(newNode);
} else if (symbol == '+' || symbol == '-' || symbol == '/'
|| symbol == '*')
{
TreeNode ptr1 = stk.pop();
TreeNode ptr2 = stk.pop();
newNode = new TreeNode(symbol);
newNode.leftChildNode = ptr2;
newNode.rightChildNode = ptr1;
stk.push(newNode);
}
symbol = s.charAt(++i);
}
rootNode = stk.pop();
}
public void traverse(int type)
{
switch (type)
{
case 1:
System.out.print("Preorder Traversal:- ");
preOrder(rootNode);
break;
case 2:
System.out.print("Inorder Traversal:- ");
inOrder(rootNode);
break;
case 3:
System.out.print("Postorder Traversal:- ");
postOrder(rootNode);
break;
default:
System.out.println("Invalid Choice");
}
}
private void preOrder(TreeNode localRoot)
{
if (localRoot != null)
{
localRoot.display();
preOrder(localRoot.leftChildNode);
preOrder(localRoot.rightChildNode);
}
}
private void inOrder(TreeNode localRoot)
{
if (localRoot != null)
{
inOrder(localRoot.leftChildNode);
localRoot.display();
inOrder(localRoot.rightChildNode);
}
}
private void postOrder(TreeNode localRoot)
{
if (localRoot != null)
{
postOrder(localRoot.leftChildNode);
postOrder(localRoot.rightChildNode);
localRoot.display();
}
}
}
class TreeNode
{
public char nodeValue;
public TreeNode leftChildNode;
public TreeNode rightChildNode;
public TreeNode(char operand)
{
nodeValue = operand;
}
public void display()
{
System.out.print(nodeValue);
}
}
class MyStack1
{
private TreeNode[] a;
private int top, m;
public MyStack1(int max)
{
m = max;
a = new TreeNode[m];
top = -1;
}
public void push(TreeNode key)
{
a[++top] = key;
}
public TreeNode pop()
{
return (a[top--]);
}
public boolean isEmpty()
{
return (top == -1);
}
}
class MyStack2
{
private char[] stackCharArray;
private int top, m;
public MyStack2(int max)
{
m = max;
stackCharArray = new char[m];
top = -1;
}
public void push(char key)
{
stackCharArray[++top] = key;
}
public char pop()
{
return (stackCharArray[top--]);
}
public boolean isEmpty()
{
return (top == -1);
}
}
class Conversion
{
private MyStack2 stack;
private String input;
private String output = "";
public Conversion(String str)
{
input = str;
stack = new MyStack2(str.length());
}
public String infixToPost()
{
for (int i = 0; i < input.length(); i++)
{
char ch = input.charAt(i);
switch (ch)
{
case '+':
case '-':
gotOperator(ch, 1);
break;
case '*':
case '/':
gotOperator(ch, 2);
break;
case '(':
stack.push(ch);
break;
case ')':
gotParenthesis();
break;
default:
output = output + ch;
}
}
while (!stack.isEmpty())
output = output + stack.pop();
return output;
}
private void gotOperator(char opThis, int prec1)
{
while (!stack.isEmpty())
{
char opTop = stack.pop();
if (opTop == '(')
{
stack.push(opTop);
break;
} else
{
int precedence;
if (opTop == '+' || opTop == '-')
precedence = 1;
else
precedence = 2;
if (precedence < prec1)
{
stack.push(opTop);
break;
} else
output = output + opTop;
}
}
stack.push(opThis);
}
private void gotParenthesis()
{
while (!stack.isEmpty())
{
char ch = stack.pop();
if (ch == '(')
break;
else
output = output + ch;
}
}
}
Explanation / Answer
Answer here is the code with comments I hope it will help you
---------------------------------------
public class Tree
{
private TreeNode rootNode;
public Tree()
{
rootNode = null;. //Making root node to null
}
public void insert(String s)
{
Conversion c = new Conversion(s); //creating object of class conversion
s = c.infixToPost(); //calling method with object of conversion
MyStack1 stk = new MyStack1(s.length());//object of mystack class
s = s + "#";
int i = 0;
char symbol = s.charAt(i);
TreeNode newNode;
while (symbol != '#')//while condition to if not #
{
if (symbol >= '0' && symbol <= '9' || symbol >= 'A'
&& symbol <= 'Z' || symbol >= 'a' && symbol <= 'z')//condition to check the symbol
{
newNode = new TreeNode(symbol);
stk.push(newNode);//pushing into the stack
} else if (symbol == '+' || symbol == '-' || symbol == '/'
|| symbol == '*')//else if condition
{
TreeNode ptr1 = stk.pop();
TreeNode ptr2 = stk.pop();//calling pop() function
newNode = new TreeNode(symbol);
newNode.leftChildNode = ptr2;
newNode.rightChildNode = ptr1;//as we are having node then we will both have right now left node
stk.push(newNode);
}
symbol = s.charAt(++i);
}
rootNode = stk.pop();
}
public void traverse(int type)//method to traverse the nodes
{
switch (type)//switch case to ask pre post or in order
{
case 1:
System.out.print("Preorder Traversal:- ");
preOrder(rootNode);
break;
case 2:
System.out.print("Inorder Traversal:- ");
inOrder(rootNode);
break;
case 3:
System.out.print("Postorder Traversal:- ");
postOrder(rootNode);
break;
default:
System.out.println("Invalid Choice");
}
}
private void preOrder(TreeNode localRoot)//to convert in pre-order
{
if (localRoot != null)
{
localRoot.display();
preOrder(localRoot.leftChildNode);
preOrder(localRoot.rightChildNode);
}
}
private void inOrder(TreeNode localRoot)//convert into inorder
{
if (localRoot != null)
{
inOrder(localRoot.leftChildNode);
localRoot.display();
inOrder(localRoot.rightChildNode);
}
}
private void postOrder(TreeNode localRoot)//to convert into post order
{
if (localRoot != null)
{
postOrder(localRoot.leftChildNode);
postOrder(localRoot.rightChildNode);
localRoot.display();
}
}
}
class TreeNode//class tree node to traverse both right and left side
{
public char nodeValue;
public TreeNode leftChildNode;
public TreeNode rightChildNode;
public TreeNode(char operand)
{
nodeValue = operand;
}
public void display()//to display after converting
{
System.out.print(nodeValue);
}
}
class MyStack1//class to make a stack
{
private TreeNode[] a;
private int top, m;
public MyStack1(int max)
{
m = max;//m is the no of values
a = new TreeNode[m];
top = -1;//end of stack
}
public void push(TreeNode key)//insert in stack
{
a[++top] = key;
}
public TreeNode pop()//delete from stack
{
return (a[top--]);
}
public boolean isEmpty()//of stack is empty
{
return (top == -1);
}
}
class MyStack2
{
private char[] stackCharArray;
private int top, m;
public MyStack2(int max) //another stack
{
m = max;
stackCharArray = new char[m];
top = -1;
}
public void push(char key)//insertion in stack
{
stackCharArray[++top] = key;
}
public char pop()//deletion from stack
{
return (stackCharArray[top--]);
}
public boolean isEmpty()
{
return (top == -1);
}
}
class Conversion//conversion class to convert from one form to another
{
private MyStack2 stack;
private String input;
private String output = "";
public Conversion(String str)
{
input = str;
stack = new MyStack2(str.length());
}
public String infixToPost()
{
for (int i = 0; i < input.length(); i++)
{
char ch = input.charAt(i);
switch (ch)
{
case '+':
case '-':
gotOperator(ch, 1);
break;
case '*':
case '/':
gotOperator(ch, 2);
break;
case '(':
stack.push(ch);
break;
case ')':
gotParenthesis();
break;
default:
output = output + ch;
}
}
while (!stack.isEmpty())
output = output + stack.pop();
return output;
}
private void gotOperator(char opThis, int prec1)//operators precedence
{
while (!stack.isEmpty())
{
char opTop = stack.pop();
if (opTop == '(')
{
stack.push(opTop);
break;
} else
{
int precedence;
if (opTop == '+' || opTop == '-')
precedence = 1;
else
precedence = 2;
if (precedence < prec1)//priority of the operator check
{
stack.push(opTop);
break;
} else
output = output + opTop;
}
}
stack.push(opThis);
}
private void gotParenthesis()//if stack empty then a parse thesis
{
while (!stack.isEmpty())
{
char ch = stack.pop();
if (ch == '(')
break;
else
output = output + ch;
}
}
}