Hi I need this evaluated and explained step by step. I need a better understandi
ID: 3855562 • Letter: H
Question
Hi I need this evaluated and explained step by step. I need a better understanding of the code to why it works and why there are two stacks aka stack 1 and 2.
Need 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 need the code below commented with explanations that connect the entire code together as to why it works This is to help me understand the concept, 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
I have added the comments in the code and added algorithm also where needed. Please check below
package postfix;
import java.io.IOException;
import java.util.Scanner;
public class PostfixExpEvaluationImpl {
public static void main(String args[]) throws IOException {
String ch = "y"; // A character flag to check if user wants to continue or exit the program
Scanner scanner = new Scanner(System.in);
while (ch.equals("y")) {
Tree t1 = new Tree();
System.out.println("Enter the Expression");
String a = scanner.next(); // user enters the expression
t1.insert(a); // add expression to tree to form a tree
t1.traverse(1); // traversing the tree with option 1
System.out.println("");
t1.traverse(2);// traversing the tree with option 2
System.out.println("");
t1.traverse(3);// traversing the tree with option 3
System.out.println("");
System.out.print("Enter y to continue ");
ch = scanner.next();
}
}
}
package postfix;
public class Tree {
private TreeNode rootNode; // represents a node in the tree A tree is nothing but combination of nodes
public Tree() { // default constructor
rootNode = null;
}
public void insert(String s) { //parsing the expression to form a tree
Conversion c = new Conversion(s); // class to convert the infix expression to postfix expression
s = c.infixToPost(); // converted string saved to String s
// initializing the stack with number of characters in postfix to get number of nodes in tree.
//Note that we have used two stacks here, 1 is used for conversion from infix to postfix
// and other is used to create a tree structure and hold nodes of the tree
MyStack1 stk = new MyStack1(s.length());
s = s + "#"; // adding delimiter
int i = 0;
char symbol = s.charAt(i); // saving value of first symbol
TreeNode newNode;
while (symbol != '#') { // check if we have reached the delimiter or end of the string
//checking if the symbol obtained in operand.
//As in expression tree operand are on leaves, so they dont have left child node and right child node.
if (symbol >= '0' && symbol <= '9' || symbol >= 'A' && symbol <= 'Z' || symbol >= 'a' && symbol <= 'z') {
newNode = new TreeNode(symbol);
stk.push(newNode); // pushing operand in the stack
} else if (symbol == '+' || symbol == '-' || symbol == '/' || symbol == '*') { // else if we get operator
//If there is operator, we will pop out top two operands in stack and make them there left and right children
TreeNode ptr1 = stk.pop();
TreeNode ptr2 = stk.pop();
newNode = new TreeNode(symbol);
// adding operands as left and right child
newNode.leftChildNode = ptr2;
newNode.rightChildNode = ptr1;
stk.push(newNode);
}
symbol = s.charAt(++i); // traversing to next symbol
}
// After traversing whole string, we will have only one element present in stack
// this element will actually be a set of TreeNodes forming a tree
// Then we will set the whole tree obtained to rootnode, thus complete expression tree is obtained.
rootNode = stk.pop();
}
public void traverse(int type) {
// Traverse method will actually traverse the tree in preorder,postorder,inorder depends upon the option.
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) {
//Pre order traversal, i.e. root,left , right
if (localRoot != null) {
localRoot.display();
preOrder(localRoot.leftChildNode);
preOrder(localRoot.rightChildNode);
}
}
private void inOrder(TreeNode localRoot) {
//In order traversal, i.e. left, root, right
if (localRoot != null) {
inOrder(localRoot.leftChildNode);
localRoot.display();
inOrder(localRoot.rightChildNode);
}
}
private void postOrder(TreeNode localRoot) {
//Post order traversal, i.e. left, right, root
if (localRoot != null) {
postOrder(localRoot.leftChildNode);
postOrder(localRoot.rightChildNode);
localRoot.display();
}
}
}
// A treenode class to create a node, having a value
// a left child node treenode
// and a right child node treenode
class TreeNode {
public char nodeValue;
public TreeNode leftChildNode;
public TreeNode rightChildNode;
public TreeNode(char operand) {
nodeValue = operand;
}
public void display() {
System.out.print(nodeValue);
}
}
// Stack 1 used for creating the expression tree.
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);
}
}
// Stack 2 used for conversion from infix to postfix
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);
}
}
//Conversion class used for converting the infix to postfix
class Conversion {
private MyStack2 stack;
private String input;
private String output = "";
//initializing conversion class with infix expression string
public Conversion(String str) {
input = str;
stack = new MyStack2(str.length()); // Initializing stack with number of symbols in string
}
//method for conversion
// algorithm used is :-
//1. Scan from left to right.
//2. print if it is operand.
//3. if current symbol is left bracket, push on stack.
//4. if it is right bracket pop from stack till you find the left bracket and keep printing it.Dont print brackets.
//5. if current symbol is of higher precedence push on stack.
//6. if it is of lower precedence, then pop the top of stack and print it, and then compare the current symbol with new top of stack.
//7. At the end, print all the symbols .
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;
}
// method used to check operator precedence
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);
}
//method used to check when closing paranthesis is obtained.
// Then pop out all the elements till we get the left paranthesis.
//Please see algorithm stated above for details.
private void gotParenthesis() {
while (!stack.isEmpty()) {
char ch = stack.pop();
if (ch == '(')
break;
else
output = output + ch;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.