Question

Evaluateeg

Goal of this assignment is to encourage you to get an understanding of how to use Stacks to evaluate an Infix expression by first converting to PostFix expression and then evaluating the PostFix expression. You are provided with Evaluatelnfix.java file that you have to update by filling the missing code that you will create by transforming the algorithm that is present on page 172 of the book. For your ease, 2 supporting methods: evaluate Operation and checkPrecedence have also been coded for you (they will be required at various places in your code). Also, a couple of testing scenarios have also been provided (as part of comments on top of evaluateinFix method) within java file that you can use to test your implementation. Note: please keep your focus on testing with single digit operands for now.

EvaluateInFix.java:

import java.util.Stack;
import java.util.Scanner;

public class EvaluateInfix
{
   public static void main(String[] args)
   {   
Scanner keyboard = new Scanner(System.in);
System.out.println("This program an inFix Expression: ");
System.out.print("Enter an inFix Expression that you want to evaluate (or enter ! to exit): ");
String aString = keyboard.nextLine();
  
while (!aString.equals("!"))
{
   System.out.println (evaluateinFix(aString));
   System.out.print("Enter an inFix Expression that you want to evaluate (or enter ! to exit): ");
   aString = keyboard.nextLine();
} // end while   
   }

//For testing, try these expressions/results
// (5 * 7 + 1) * 6 / (2 ^ 3 - 3 * 4 + 1) = -72
// (2 + 3) / (4 - 5 ) - 5 = 10
// Avoid testing double digit within the expression for now
   public static String evaluateinFix(String inFix)
   {
       Stack<Character> operatorStack = new Stack<Character>();
       Stack<Integer> valueStack = new Stack<Integer>();

       /////////////////////////////////////////////////////////////////////
       //TO DO: ADD CODE HERE BY CONVERTING ALGORITHM ON PAGE 172 OF BOOK //
       /////////////////////////////////////////////////////////////////////

       return valueStack.peek().toString();
   }

//Evaluates expression like 2+3 and returns the result like 5
public static int evaluateOperation(char operator, int operandOne, int operandTwo)
{
System.out.println(operandOne + " " + operator + " " + operandTwo);
       switch (operator)
       {
case '^':
               return (int)Math.pow(operandOne, operandTwo);

           case '+':
               return operandOne + operandTwo;
              
           case '-':
               return operandOne - operandTwo;
              
           case '*':
               return operandOne * operandTwo;
              
           case '/':
               if (operandTwo == 0)
               {throw new UnsupportedOperationException("Cannot divide by zero.");}
               return operandOne / operandTwo;
       }
       return 0;
}
  
//Returns true if precedence of Operator1 is less than precedence of Operator2
public static boolean checkPrecedence(char Operator1, char Operator2)
{
if (Operator2 == '(' || Operator2 == ')')
   return false;

if ((Operator1 == '*' || Operator1 == '/') && (Operator2 == '+' || Operator2 == '-'))
   return false;
else
   return true;
}   
}

A3_Book_Page172_Algorithm:

Algorithm evaluateInfix(infix)
// Evaluates an infix expression.
operatorStack = a new empty stack
valueStack = a new empty stack
while (infix has characters left to process) {
nextCharacter = next nonblank character of infix
switch (nextCharacter) {
case variable:
valueStack.push(value of the variable nextCharacter)
break
case '^':
operatorStack.push(nextCharacter)
break
case '+':
case '-':
case '*':
case '/':
while (!operatorStack.isEmpty() and precedence of nextCharacter <= precedence of operatorStack.peek()) {
// Execute operator at top of operatorStack
topOperator = operatorStack.pop()
operandTwo = valueStack.pop()
operandOne = valueStack.pop()
result = the result of the operation in topOperator and its operands
operandOne
and operandTwo
valueStack.push(result)
}
operatorStack.push(nextCharacter)
break
case '(':
operatorStack.push(nextCharacter)
break
case ')': // Stack is not empty if infix expression is valid
topOperator = operatorStack.pop()
while (topOperator != '(') {
operandTwo = valueStack.pop()
operandOne = valueStack.pop()
result = the result of the operation in topOperator and its operands
operandOne
and operandTwo
valueStack.push(result)
topOperator = operatorStack.pop()
}
break

Answer 1

NOTE : -

ALWAYS MAKE SURE THAT EVERY CHARACTER OF EXPRESSION IS SEPERATED BY SPACE

I.E DO NOT INPUT EXPRESSION LIKE (2 + 3) * 2 INSTEAD IT SHOULD BE ( 2 + 3 ) * 2

SOURCE CODE

   public static String evaluateinFix(String inFix)

   {

       Stack<Character> operatorStack = new Stack<Character>();

       Stack<Integer> valueStack = new Stack<Integer>();

       /////////////////////////////////////////////////////////////////////

       //TO DO: ADD CODE HERE BY CONVERTING ALGORITHM ON PAGE 172 OF BOOK //

       /////////////////////////////////////////////////////////////////////

       char[] tokens = inFix.toCharArray();

       for(int i = 0; i < tokens.length; i++)

       {

            if(tokens[i] == ' ')

                continue;

            // Current token is a number, push it to stack for numbers

            if (tokens[i] >= '0' && tokens[i] <= '9')

            {

                StringBuffer sbuf = new StringBuffer();

                // There may be more than one digits in number

                while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')

                    sbuf.append(tokens[i++]);

                valueStack.push(Integer.parseInt(sbuf.toString()));

            }

  

            // Current token is an opening brace, push it to 'ops'

            else if (tokens[i] == '(')

                operatorStack.push(tokens[i]);

  

            // Closing brace encountered, solve entire brace

            else if (tokens[i] == ')')

            {

                while (operatorStack.peek() != '(')

                    {

                        int op1 = valueStack.pop();

                        int op2 = valueStack.pop();

                        valueStack.push(evaluateOperation(operatorStack.pop(), op2, op1));

                    }

                operatorStack.pop();

            }

  

            // Current token is an operator.

            else if (tokens[i] == '+' || tokens[i] == '-' ||

                     tokens[i] == '*' || tokens[i] == '/' || tokens[i] == '^')

            {

                // While top of 'ops' has same or greater precedence to current

                // token, which is an operator. Apply operator on top of 'ops'

                // to top two elements in values stack

                while (!operatorStack.empty() && checkPrecedence(tokens[i], operatorStack.peek()))

                    {

                        int op1 = valueStack.pop();

                        int op2 = valueStack.pop();

                        valueStack.push(evaluateOperation(operatorStack.pop(), op2, op1));

                    }

  

                // Push current token to 'ops'.

                operatorStack.push(tokens[i]);

            }

       }

       // Entire expression has been parsed at this point, apply remaining

        // ops to remaining values

        while (!operatorStack.empty())

            {

                int op1 = valueStack.pop();

                int op2 = valueStack.pop();

                valueStack.push(evaluateOperation(operatorStack.pop(), op2, op1));

            }

  

        // Top of 'values' contains result, return it

        return valueStack.pop().toString();

   }

25 V public static String evaluateinFix(String inFix) 26 [ 27 28 Stack<Character> operatorStack = new Stack<Character>(); Stack<Integer> valueStack = new Stack<Integer>(); 29 30 31 32 //TO DO: ADD CODE HERE BY CONVERTING ALGORITHM ON PAGE 172 OF BOOK // 33 34 35 char[] tokens inFix.toCharArray(); 36 37 for(int i = 0; i < tokens.length; i++) 38 V { 39 == 40 if(tokens[i] ') continue; // Current token is a number, push it to stack for numbers if (tokens[i] >= '0' && tokens[i] <= '9') 41 42 { 43 V 44 45 46 StringBuffer sbuf = new StringBuffer(); // There may be more than one digits in number while (i < tokens.length && tokens[i] >= 'O' && tokens[i] <= '9') sbuf.append(tokens[i++]); valueStack.push(Integer.parseInt(sbuf.toString())); 47 48 49 ها 50 51 52 // Current token is an opening brace, push it to 'ops' else if (tokens[i] '(') operatorStack.push(tokens[i]); == 53 54 55 // Closing brace encountered, solve entire brace else if (tokens[i] ')') == 56 57 V { 58 while (operatorStack.peek() != '(') 59 V { 60 int op1 valueStack.pop(); int op2 = valueStack.pop(); 61

59 1 60 61 int op1 = valueStack.pop(); int op2 valueStack.pop(); valueStack.push(evaluateOperation (operatorStack.pop(), op2, op1)); = 62 63 } 64 operatorstack.pop(); 65 } 66 67 68 // Current token is an operator. else if (tokens[i] '+' || tokens[i] tokens[i] || tokens[i] == == 69 1* == '/' || tokens[i] == '^') 70 { 71 72 // While top of 'ops' has same or greater precedence to current // token, which is an operator. Apply operator on top of 'ops' // to top two elements in values stack while (!operatorStack.empty() && checkPrecedence(tokens[i], operatorStack.peek( ))) 73 74. 75 ܕܝܢ 76 77 int op1 valueStack.pop(); int op2 valueStack.pop(); valueStack.push(evaluateOperation (operatorStack.pop(), op2, op1)); = 78 79 } 80 81 // Push current token to 'ops'. operatorstack.push(tokens[i]); 82 83 } 84 } 85 86 // Entire expression has been parsed at this point, apply remaining // ops to remaining values while (!operatorStack.empty()) 87 88 { 89 90 int op1 valueStack.pop(); int op2 valueStack.pop(); valueStack.push(evaluateOperation (operatorStack.pop(), op2, op1)); 91 92 } 93 94 // Top of 'values' contains result, return it return valueStack.pop().toString(); 95 96 }

OUTPUT

C:\Users\Faheem\Documents\GitHub\HackerRank>cd "c:\Users\Faheem\Documents\GitHub\HackerRank\" && javac EvaluateInFix.java && java EvaluateInFix This program an inFix Expression: Enter an inFix Expression that you want to evaluate (or enter ! to exit): ( 2 + 3 ) / ( 4 - 5 ) - 5 2 + 3 4 5 5 / -1 -5 - 5 -10 Enter an inFix Expression that you want to evaluate (or enter ! to exit): ( 5 * 7 + 1 ) * 6 / ( 2^ 3 - 3 * 4 + 1 ) 5 * 7 35 + 1 36 * 6 2 1 3 3 4 8 12 -4 + 1 216 / -3 -72 Enter an inFix Expression that you want to evaluate (or enter ! to exit): | * - :

HOPE ANSWER THE QUESTION

COMMENT BELOW IF HAVING ANY DOUBT