Question

An arithmetic expression can be represented in three different formats: infix, prefix, and postfix. In the infix notation, the operator comes between two operands. In the postfix notation, the operator comes after its two operands. For example, an expression a/b can be transformed to ab/. The following are some examples of the postfix expressions:

2+6*4 Its postfix notation is 2 6 4 * +

2-3+5/4*9-1 Its postfix expression is 2 3 – 5 4 / 9 * + 1 -

For this assignment, write a JAVA program that reads an postfix expression and evaluates the postfix expression. Your program should display the following menu repeatedly:

1. Read an expression in postfix notation.

// Read an infix expression and print out the string for verification.

2. Evaluate the postfix expression.

0. Exit.

For the input string, you can make the following assumptions:

Input strings are error-free

+, -, *, / are the only operators used

All operand are positive integers consisting of one or more digits.

Space appears in the input string to separate the operands and operators.

Implement a class StackLink, which is a stack implemented by a linked list (Do not use the JAVA predefined class java.util.LinkedList). Your program should use stack operations to evaluate the postfix expression. The following figure shows how stacks can help.

The following are some results when your run the program:

C:'>java Homework4

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

1

Enter a postfix expression: 32 15 2 * + 36 4 / -

The entered infix expression is: 32 15 2 * + 36 4 / -

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

2

32 15 2 * + 36 4 / - = 53

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

1

Enter a postfix expression: 3 4 / 15 * 9 / 6 8 * + 7 - 54 +

The entered infix expression is: 3 4 / 15 * 9 / 6 8 * + 7 - 54 +

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

2

3 4 / 15 * 9 / 6 8 * + 7 - 54 + = 95

Select from:

1. Read an expression in infix notation.

2. Convert infix to postfix.

3. Evaluate the postfix expression

0. Exit.

0

Goodbye.

Answer 1

As per your requirement I have created two classes StackLink and Test. StackList internally using user defined linked list.

Class 1 : StackLink
class StackLink {
  
private class Node {
  
int data;
Node link;
}
Node top;
StackLink()
{
this.top = null;
}
  
public void push(int x)
{
Node temp = new Node();
  
temp.data = x;
  
temp.link = top;
  
top = temp;
}
  
public boolean isEmpty()
{
return top == null;
}
  
public int peek()
{
if (!isEmpty()) {
return top.data;
}
else {
return -1;
}
}
  
public int pop()
{
if (top == null) {
System.out.println("\nStack Underflow");
return -1;
}
int temp=top.data;
top = (top).link;
return temp;
}
  
public void display()
{
if (top == null) {
System.out.println("\nStack Underflow");
System.exit(1);
}
else {
Node temp = top;
while (temp != null) {
  
System.out.print(temp.data);
  
temp = temp.link;
}
}
}
}

Class 2 : Test

import java.util.Scanner;

public class Test
{
   static int evaluatePostfix(String exp)
   {
       String array[]=exp.split(" ");
       StackLink stack=new StackLink();

       for(int i=0;i<array.length;i++)
       {
           Integer data = null;
           char c='\0';
           try {
               data = new Integer(Integer.parseInt(array[i]));
   } catch (NumberFormatException e) {
       c=array[i].charAt(0);
   }

           if(data !=null)
               stack.push(data.intValue());

           else
           {
               int val1 = stack.pop();
               int val2 = stack.pop();

               switch(c)
               {
               case '+':
                   stack.push(val2+val1);
                   break;

               case '-':
                   stack.push(val2- val1);
                   break;

               case '/':
                   stack.push(val2/val1);
                   break;

               case '*':
                   stack.push(val2*val1);
                   break;
               }
           }
       }
       return stack.pop();   
   }

   public static void main(String[] args)
   {
       int input=0;
       String exp="";
       Scanner sc=new Scanner(System.in);
       System.out.println("Select from:");
       while(true){
           System.out.println("1. Read an expression in postfix notation.");
           System.out.println("2. Evalute the postfix expression.");
           System.out.println("0. Exit.");
           input=Integer.parseInt(sc.nextLine());
           switch (input) {
           case 1:
               System.out.print("Enter a postfix expression: ");
               exp=sc.nextLine();
               System.out.println("The entered postfix expression is: "+exp);
               break;
           case 2:
               System.out.println(exp+" = "+evaluatePostfix(exp));
               break;
           case 0:
               System.out.println("Goodbye");
               System.exit(0);
               break;
           }
       }
   }
}

Example output:

Select from:
1. Read an expression in postfix notation.
2. Evalute the postfix expression.
0. Exit.
1
Enter a postfix expression: 2 3 +
The entered postfix expression is: 2 3 +
1. Read an expression in postfix notation.
2. Evalute the postfix expression.
0. Exit.
2
2 3 +=5
1. Read an expression in postfix notation.
2. Evalute the postfix expression.
0. Exit.
0
0
Goodbye