Q3 - 20 pts) You are given the code (including the main function) for evaluating
ID: 3872468 • Letter: Q
Question
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() );
}
}
Explanation / Answer
Note: I have modified the code of main fucntion and pasted whole code. Used proper tagging to identify the modified logic i.e. conversion of prefix to postfix.
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;
int i;
String tmpExp_str[] = new String[100]; // string array
String postfix_expression = " "; // to hold computed postfix expression
Scanner input = new Scanner(System.in);
System.out.print("Enter the expression in prefix notation to evaluate: ");
expression = input.nextLine();
//prefix to postfix conversion logic:
//Logic to reverse all the charcters of string array
for(i=0; i<=expression.length()-1; i++){
tmpExp_str[expression.length()-1-i]=Character.toString(expression.charAt(i));
}
//Postfix computation
i=0;
do{
if (!isOperator(tmpExp_str[i].charAt(0))) // check if charcter is operator
stack.push(tmpExp_str[i]); // push if it is not operator
else{
String str1 = stack.pop();
String str2 = stack.pop();
str1 = str1 + str2 + tmpExp_str[i];
postfix_expression = str1;
stack.push(str1);
}
i++;
}while(stack.getTop()>=0 && i!=expression.length());
StringTokenizer stk = new StringTokenizer(postfix_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() );
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.