Write a program that uses the stack algorithm we discussed in class to evaluate

Question

Write a program that uses the stack algorithm we discussed in class to evaluate postfix expressions entered by the user. The program should support expressions involving any double values (positive, negative, or zero) and any combination of these operators:

+ addition
- subtraction
* multiplication
/ division
% mod (remainder)
^ exponentiation (e.g., 7^2 = 49)

You can use the built-in java.util.Stack class to keep track of your operands. Assume that all tokens in the
postfix expression are separated by spaces. The program should show an appropriate message if the expression
entered by the user has too many or too few operands. Also display an error message if the expression contains
anything besides numbers and the six operators above.

Here’s an example of what your program might look like while running. The underlined portions indicate user
input.

Enter a postfix expression X to exit: 1 2 3 Result 3.0 Enter a postfix expression X to exit: 1 2 3 Too many operands Enter a postfix expression X to exit: 1 2 3 A Too few operands Enter a postfix expression X to exit a b Unsupported operand/operator type

Explanation / Answer

Here is working solution-

//Note please go through the comments once for proper understanding

//EvaluatePostfix.java
public class EvaluatePostfix {

   public static void main(String[] args) {
       System.out.println("Enter a postfix expression, X to exit");
       Scanner sc = new Scanner(System.in);
       String expresssion = sc.nextLine();       //reading postfix expression from console
       boolean isPerformTest=false;
       boolean isValid = validateExpression(expresssion); //calling a method to validate the postfix expression first
      
       if (isValid) {
           System.out.println("Result ="+postfixEvaluate(expresssion));
          
       }
       //uncomment below flag is you want to perform the test with hard coded string too
//       isPerformTest=true;
       if(isPerformTest){
           System.out.println("Result ="+validateExpression("1 -2 + 3 *"));
           System.out.println("Result ="+validateExpression("1 -2 + 3"));
           System.out.println("Result ="+validateExpression("1 -2 + 3 * ^"));
           System.out.println("Result ="+validateExpression("a b +"));
           System.out.println("Result ="+validateExpression("1 -2 + 3 +a *"));
       }
   }

   private static boolean validateExpression(String expression) {
      
       if(!expression.equalsIgnoreCase("X")){       //if user input is x or X then method will return false and program will exit
          
           return validateInputString(expression);
       }
       return false;

   }

   private static boolean validateInputString(String expression) {
       boolean atleastOneAlpha = expression.matches(".*[a-zA-Z]+.*");   // regex for testing whether postfix expression contains any alphabets or not
       if (atleastOneAlpha) {
           System.out.println("unsupported operand/operator type.");   //if expression contains alphabets then return false;
           return false;
       }

       int count = 0;
       String[] str = expression.split(" ");   // converting expression to a string array based on space separated
       String regex = "^(?!-0(\.0+)?$)-?(0|[1-9]\d*)(\.\d+)?$";   //regex for testing whether an operand is double or not
       Pattern p = Pattern.compile(regex);

       for (int i = 0; i < str.length; i++) {
           Matcher m = p.matcher(str[i]);
           if (m.find()) {       /* To check if a postfix expression is valid or not:(if input is in char array) 1.Number of operands must equal no. of operators + 1.
                               To check this keep a check variable. check=0. Increment this for every operand and decrement for each operator.If finally its value is 1,then expression is valid.*/
               count++;   //incrementing count wherever we find operand
           } else {
               count--;   //decrementing count wherever we find operator
           }
           if (i + 1 != count && i == 1) { /*The first 2 elements of the array need to be operands.No postfix expression can have operator as 1st or 2nd element.*/
               System.out.println("InValid postfix expresssion..!!");   // testing whether first two are operands or not in postfix expression
               return false;
           }

       }
       if (count > 1) {
           System.out.println("Too many operands! ");
           return false;
       }
       if (count < 1) {
           System.out.println("Too few operands!");
           return false;
       }

       return true;
   }

   /**method to evaluate postfix expression
   *
   * @param exp
   * @return
   */
   public static Double postfixEvaluate(String exp) {
       Stack<Double> s = new Stack<Double>();
       Scanner tokens = new Scanner(exp);
       while (tokens.hasNext()) {
           if (tokens.hasNextDouble()) {
               s.push(tokens.nextDouble());   //if find operand push into the stack
           } else {
               double num2 = s.pop();   // pop consecutive two operands if found operators
               double num1 = s.pop();
               String op = tokens.next();
               /* checking for operator and computing the result after that store that result into stack itself*/
               if (op.equals("+")) {
                   s.push(num1 + num2);
               } else if (op.equals("-")) {
                   s.push(num1 - num2);
               } else if (op.equals("*")) {
                   s.push(num1 * num2);
               } else if(op.equals("%")){
                   s.push(num1%num2);
               }else if(op.equals("^")){
                   s.push(Math.pow(num1, num2));   // for calculating powers
               }else {
                   s.push(num1 / num2);
               }
                  
               }

           }
       return s.pop();   // returning answer or last remaining element from the stack's top.

   }
}

//output of program with all test cases-

Enter a postfix expression, X to exit
1 -2 +3 *
Too few operands!
Result =true
Too many operands!
Result =false
Too few operands!
Result =false
unsupported operand/operator type.
Result =false
unsupported operand/operator type.
Result =false

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.