Q3 - 20 pts) You are given the code (including the main function) for evaluating an expression in post-fix format using Stack. Your task is to modify the code in the main function to input an expression in pre-fix format, reverse it (as discussed in class) and then evaluate the value of the reversed expression (scanned from left to right) using Stack. You test your code with an expression string in pre-fix format that comprises of all the four operators (at least once) in a randomly chosen order with randomly chosen values in the range 1 to 9. For example, a sample expression string (pre-fix notation) could be input as 8, 4, 3, 2, 5, /, *, +, - for the expression (infix-notation) 5 / 2 * 3 + 4 - 8.

The code is: import java.util.*; class Node{ private int data; private Node nextNodePtr; public Node(){} public void setData(int d){ data = d; } public int getData(){ return data; } public void setNextNodePtr(Node nodePtr){ nextNodePtr = nodePtr; } public Node getNextNodePtr(){ return nextNodePtr; } } class Stack{ private Node headPtr; public Stack(){ headPtr = new Node(); headPtr.setNextNodePtr(null); } public Node getHeadPtr(){ return headPtr; } public boolean isEmpty(){ if (headPtr.getNextNodePtr() == null) return true; return false; } public void push(int data){ Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; while (currentNodePtr != null){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr(); } Node newNodePtr = new Node(); newNodePtr.setData(data); newNodePtr.setNextNodePtr(null); prevNodePtr.setNextNodePtr(newNodePtr); } public int peek(){ Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; if (currentNodePtr == null){ return -1000000; // stack is empty } while (currentNodePtr.getNextNodePtr() != null) currentNodePtr = currentNodePtr.getNextNodePtr(); return currentNodePtr.getData(); } public int pop(){ Node currentNodePtr = headPtr.getNextNodePtr(); Node prevNodePtr = headPtr; if (currentNodePtr == null){ return -1000000; // stack is empty } while (currentNodePtr.getNextNodePtr() != null){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr.getNextNodePtr(); } prevNodePtr.setNextNodePtr(null); return currentNodePtr.getData(); } } class SinglyLinkedListBasedStack{ public static void main(String[] args){ Stack stack = new Stack(); String expression; Scanner input = new Scanner(System.in); System.out.print("Enter the expression to evaluate: "); expression = input.nextLine(); StringTokenizer stk = new StringTokenizer(expression, ", "); while (stk.hasMoreTokens()){ String token = stk.nextToken(); boolean isOperator = false; if ( (token.equals("*")) || (token.equals("/")) || (token.equals("+")) || (token.equals("-")) ) isOperator = true; if (!isOperator){ int val = Integer.parseInt(token); stack.push(val); } if (isOperator){ int rightOperand = stack.pop(); int leftOperand = stack.pop(); if (token.equals("*")){ int result = leftOperand * rightOperand; System.out.println("intermediate result: " + leftOperand + "*" + rightOperand + "=" + result); stack.push(result); } else if (token.equals("/")){ int result = leftOperand / rightOperand; System.out.println("intermediate result: " + leftOperand + "/" + rightOperand + "=" + result); stack.push(result); } else if (token.equals("+")){ int result = leftOperand + rightOperand; System.out.println("intermediate result: " + leftOperand + "+" + rightOperand + "=" + result); stack.push(result); } else if (token.equals("-")){ int result = leftOperand - rightOperand; System.out.println("intermediate result: " + leftOperand + "-" + rightOperand + "=" + result); stack.push(result); } } } System.out.println("final result: " + stack.pop() ); } }