Hi I only need the code below commented to help me understand Hi I need this cod
ID: 3855459 • Letter: H
Question
Hi I only need the code below commented to help me understand
Hi I need this code commented below with an explanation of vital steps to help me understand it. The code itself evaluates a reverse polish (postfix) expression such as 2 * (3 + 4) + 5 which is then 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.
I only need the code below commented with explanations to help me understand, for example //comment etc. on major steps and logic
Thank You
----------------------------------------------
package postfix;
import java.io.IOException;
import java.util.Scanner;
public class PostfixExpEvaluationImpl {
public static void main(String args[]) throws IOException {
String ch = "y";
Scanner scanner = new Scanner(System.in);
while (ch.equals("y")) {
Tree t1 = new Tree();
System.out.println("Enter the Expression");
String a = scanner.next();
t1.insert(a);
t1.traverse(1);
System.out.println("");
t1.traverse(2);
System.out.println("");
t1.traverse(3);
System.out.println("");
System.out.print("Enter y to continue ");
ch = scanner.next();
}
}
}
--------------------- End-------------------------
package postfix;
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;
}
}
}
--------------------- End class Tree --------------------
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
Explanation / Answer
The given code is commented with proper Explanation and plese comment me if you need anything more on it.
package postfix;
import java.io.IOException;
import java.util.Scanner; //importing java.util.scannerpackage which helps in reading the input from the user
public class PostfixExpEvaluationImpl { //created class with name PostfixExpEvaluationImpl
public static void main(String args[]) throws IOException {
String ch = "y";
Scanner scanner = new Scanner(System.in); //created scanner object which allows to read the input from the user
while (ch.equals("y")) {
Tree t1 = new Tree(); // created tree object
System.out.println("Enter the Expression"); // asking user to enter the expression
String a = scanner.next(); //reading the entered expression
t1.insert(a); //storing the expression in t1 object
t1.traverse(1);
System.out.println("");
t1.traverse(2);
System.out.println("");
t1.traverse(3);
System.out.println("");
System.out.print("Enter y to continue "); // asking the user to continue entering expressions or not.
ch = scanner.next();
}
}
}
--------------------- End-------------------------
package postfix;
public class Tree //created a public class with name Tree
{
private TreeNode rootNode; //created private member rootnode
public Tree()
{
rootNode = null; //iniatialized rootnode as null
}
public void insert(String s) //inser method created
{
Conversion c = new Conversion(s);
s = c.infixToPost();
MyStack1 stk = new MyStack1(s.length()); //stack object created for storing the expressions
s = s + "#";
int i = 0; //intialized i value with 0.
char symbol = s.charAt(i);
TreeNode newNode;
while (symbol != '#') //checking if symbol is not equal to # or not
{
if (symbol >= '0' && symbol <= '9' || symbol >= 'A'
&& symbol <= 'Z' || symbol >= 'a' && symbol <= 'z') // important condition written for the program checking if symbol is >= '0' and symbol <= '9' or symbol >= 'A'
//and symbol <= 'Z' or symbol >= 'a' and symbol <= 'z'
{
newNode = new TreeNode(symbol); //created a new object and stored all the symbols in to the object
stk.push(newNode); //pushed all the symbols in to the stack
} else if (symbol == '+' || symbol == '-' || symbol == '/'
|| symbol == '*') //else if condition for checking the operators
{
TreeNode ptr1 = stk.pop(); //popping the elements from the stack
TreeNode ptr2 = stk.pop(); //popping the elements from the stack
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) //switch condition for printing the traversal elements
{
case 1:
System.out.print("Preorder Traversal:- "); //printing preorder traversal elements
preOrder(rootNode);
break;
case 2:
System.out.print("Inorder Traversal:- "); //printing INorder traversal elements
inOrder(rootNode);
break;
case 3:
System.out.print("Postorder Traversal:- "); //printing postorder traversal elements
postOrder(rootNode);
break;
default:
System.out.println("Invalid Choice");
}
}
private void preOrder(TreeNode localRoot) //preorder traversal method
{
if (localRoot != null) // checking the condition of preoder and printing according to that root, left and right elements
{
localRoot.display();
preOrder(localRoot.leftChildNode);
preOrder(localRoot.rightChildNode);
}
}
private void inOrder(TreeNode localRoot) //Inorder traversal method
{
if (localRoot != null) // checking the condition of INoder and printing according to that left, root and right elements
{
inOrder(localRoot.leftChildNode);
localRoot.display();
inOrder(localRoot.rightChildNode);
}
}
private void postOrder(TreeNode localRoot) //postorder traversal method
{
if (localRoot != null) // checking the condition of postoder and printing according to that left ,right and root elements
{
postOrder(localRoot.leftChildNode);
postOrder(localRoot.rightChildNode);
localRoot.display();
}
}
}
class TreeNode // created class TreeNode
{
public char nodeValue;
public TreeNode leftChildNode;
public TreeNode rightChildNode;
public TreeNode(char operand)
{
nodeValue = operand;
}
public void display() // display method which prints nodevalue
{
System.out.print(nodeValue);
}
}
class MyStack1 // stack class is created here MyStack1
{
private TreeNode[] a;
private int top, m;
public MyStack1(int max) // mystack1 method created here
{
m = max; //storing max value in m variable
a = new TreeNode[m];
top = -1;
}
public void push(TreeNode key) // push method created for pushing elements to stack
{
a[++top] = key;
}
public TreeNode pop() //pop method for popping elements fro stack
{
return (a[top--]);
}
public boolean isEmpty()
{
return (top == -1);
}
}
class MyStack2 // crated another class MyStack2
{
private char[] stackCharArray;
private int top, m;
public MyStack2(int max) // mystack2 method created here
{
m = max;
stackCharArray = new char[m];
top = -1;
}
public void push(char key) // push method created for pushing elements to stack
{
stackCharArray[++top] = key;
}
public char pop() //pop method for popping elements fro stack
{
return (stackCharArray[top--]);
}
public boolean isEmpty()
{
return (top == -1);
}
}
class Conversion //conversion class for converting elements
{
private MyStack2 stack;
private String input;
private String output = "";
public Conversion(String str) // conversion method is created
{
input = str;
stack = new MyStack2(str.length());
}
public String infixToPost() // infixToPostfix method
{
for (int i = 0; i < input.length(); i++) //loop for calculating the length of the input
{
char ch = input.charAt(i);
switch (ch) //switch condition for switching mjultiple operators
{
case '+':
case '-':
gotOperator(ch, 1);
break;
case '*':
case '/':
gotOperator(ch, 2);
break;
case '(':
stack.push(ch); //pushing the operators to stack
break;
case ')':
gotParenthesis();
break;
default:
output = output + ch;
}
}
while (!stack.isEmpty()) //checking whether the stack is not empty
output = output + stack.pop();
return output; //returning the output
}
private void gotOperator(char opThis, int prec1)
{
while (!stack.isEmpty())
{
char opTop = stack.pop(); //popping the elemets from stack
if (opTop == '(')
{
stack.push(opTop);
break;
} else
{
int precedence; //created precedence variable
if (opTop == '+' || opTop == '-') //checking operators
precedence = 1; //giving precedence values as 1
else
precedence = 2; //giving precedence values as 2
if (precedence < prec1)
{
stack.push(opTop); //pushing elemts to stack operator top position
break;
} else
output = output + opTop;
}
}
stack.push(opThis);
}
private void gotParenthesis() //gotParenthesis method created
{
while (!stack.isEmpty())
{
char ch = stack.pop();
if (ch == '(') //if paranthesis is found then the condition will get terminated
break;
else
output = output + ch;
}
}
}
--------------------- End class Tree --------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.