Question

1. Postfix Evaluation (JAVA PROGRAMMING)

Write class PostfixEva1uator that evaluates a postfix expression such as 6 2 + 5 * 8 4 / -

The program should read a postfix expression consisting of single digits and operators into a StringBuilder, The program should read the expression and evaluate it (assume it's valid). The algorithm to evaluate a postfix expression is shown below. Use +, -, *, /, and ^. ^ is the exponent.

Append a right parenthesis ') ' to the end of the postfix expression. When the right-parenthesis character is encountered, no further processing is necessary.

Until the right parenthesis is encountered, read the expression from left to right.

if the current character is a digit, do the following:

Push its integer value onto the stack

else, if the current character is an operator:

Pop the two top elements of the stack into variables x and y.

Calculate y operator x.

Push the result of the calculation onto the stack.

End until when the right parenthesis is encountered in the expression,

Pop the top value of the stack. This is the result of the postfix expression .

[Note: (based on the sample expression at the beginning of this exercise), if the operator is '/', the top of the stack is 4 and the next element in the stack is 40, then pop 4 into x, pop 40 into y, evaluate 40 / 4 and push the result, 10, back on the stack. This note also applies to other operators.] The arithmetic operations allowed in an expression are: + (addition), - (subtraction), '' (multiplication),/ (division), A (exponentiation) and x (remainder).

You willy want to use the following methods:

a) Method evaluatePostfixExpression, which evaluates the postfix expression. It is called from main. (20)

b) Method calculate, which evaluates the expression opl operator op2. Called from evaluatePostfixExpression. (20)

c) Method printStack which prints out the stack after each push or pop. Called from evaluatePostfixExpression (multiple times) (20)

This example can all be done in a single class.

The main program simply request the postfix expression. Remember to leave a space between each digit and/or operator. (10)

Sample input/output

Please enter a postfix expression:

6 2 + 5 * 8 4 / -

The original postfix expression is:

6 2 + 5 * 8 4 / -

6

6

2

6

8

8

5

8

40

40

8

40

8

4

40

8

40

40

2

40

38

The value of the expression is: 38

Another Example:

Please enter a postfix expression:

4 5 + 3 / 4 ^ 2 -

The original postfix expression is:

4 5 + 3 / 4 ^ 2 -

4

4

5

4

9

9

3

9

3

3

4

3

81

81

2

81

79

The value of the expression

Answer 1

import java.util.Stack;

class Main
{
   // Function to evaluate given postfix expression
   public static int postfixEval(String exp)
   {
       // create an empty stack
       Stack<Integer> stack = new Stack<>();

       // traverse the given expression
       for (char c: exp.toCharArray())
       {
           // if current char is an operand, push it to the stack
           if (Character.isDigit(c)) {
               stack.push(c - '0');
           }
           // if current char is an operator
           else
           {
               // pop top two elements from the stack
               int x = stack.pop();
               int y = stack.pop();

               // evaluate the expression x op y, and push the
               // result back to the stack
               if (c == '+') {
                   stack.push(y + x);
               }
               else if (c == '-') {
                   stack.push(y - x);
               }
               else if (c == '*') {
                   stack.push(y * x);
               }
               else if (c == '/') {
                   stack.push(y / x);
               }
           }
       }

       // At this point, the stack is left with only one element i.e.
       // expression result
       return stack.pop();
   }

   public static void main(String[] args)
   {

       System.out.println(postfixEval(138*+));
   }
}