Design and impliment a utility class ExpressionSolver to solve any good simple e

Question

Design and impliment a utility class ExpressionSolver to solve any good simple expression using the algorithm discussed in class. Simple expressions can have +,-,*,/, and, parenthesis.

Algorithm is to take the first five tokens and figure out what has more priority and solve that problem first.

So in the problem 30 + 10 - 3 * 6 + 12 / 2, take the tokens 30 + 10 - 3 and solve the most important part first in this case 30 + 10. The new list would be 40 - 3 * 6 + 12 / 2, and the next part would be 40 - 3 * 6, and this time 3 * 6 would be done first since it's multiplication. And the list would now be 40 - 18 + 12 / 2 and so on.

Write a driver program to read expressions from a text file (one expression on each line) and print out the original expressions and their evaluation/expected results on screen. Don't forget to prompt the user for the input filename.

Requirements:

-No data structures (stack, queue, array, list...) or advanced algorithms allowed (as discussed in class)

-Error handling and user-friendliness are required

Explanation / Answer

/* A Java program to evaluate a given expression where tokens are separated
by space.
Test Cases:
"10 + 2 * 6" ---> 22
"100 * 2 + 12" ---> 212
"100 * ( 2 + 12 )" ---> 1400
"100 * ( 2 + 12 ) / 14" ---> 100
*/
import java.io.File;
import java.util.Scanner;
import java.util.Stack;

public class ExpressionSolver {
   public static int evaluate(String expression) {
       char[] tokens = expression.toCharArray();

       // Stack for numbers: 'values'
       Stack<Integer> values = new Stack<Integer>();

       // Stack for Operators: 'ops'
       Stack<Character> ops = new Stack<Character>();

       for (int i = 0; i < tokens.length; i++) {
           // Current token is a whitespace, skip it
           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++]);
               values.push(Integer.parseInt(sbuf.toString()));
           }

           // Current token is an opening brace, push it to 'ops'
           else if (tokens[i] == '(')
               ops.push(tokens[i]);

           // Closing brace encountered, solve entire brace
           else if (tokens[i] == ')') {
               while (ops.peek() != '(')
                   values.push(applyOp(ops.pop(), values.pop(), values.pop()));
               ops.pop();
           }

           // Current token is an operator.
           else if (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 (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
                   values.push(applyOp(ops.pop(), values.pop(), values.pop()));

               // Push current token to 'ops'.
               ops.push(tokens[i]);
           }
       }

       // Entire expression has been parsed at this point, apply remaining
       // ops to remaining values
       while (!ops.empty())
           values.push(applyOp(ops.pop(), values.pop(), values.pop()));

       // Top of 'values' contains result, return it
       return values.pop();
   }

   // Returns true if 'op2' has higher or same precedence as 'op1',
   // otherwise returns false.
   public static boolean hasPrecedence(char op1, char op2) {
       if (op2 == '(' || op2 == ')')
           return false;
       if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
           return false;
       else
           return true;
   }

   // A utility method to apply an operator 'op' on operands 'a'
   // and 'b'. Return the result.
   public static int applyOp(char op, int b, int a) {
       switch (op) {
       case '+':
           return a + b;
       case '-':
           return a - b;
       case '*':
           return a * b;
       case '/':
           if (b == 0)
               throw new UnsupportedOperationException("Cannot divide by zero");
           return a / b;
       }
       return 0;
   }

   // Driver method to test above methods
   public static void main(String[] args) {
       Scanner scanner;

       try {
           System.out.print("Enter the file name :");
           scanner = new Scanner(System.in);
           String fileName = scanner.nextLine();
           // expressions.txt
           File file = new File(fileName);
           scanner = new Scanner(file);

           while (scanner.hasNext()) {
               String expression = scanner.nextLine();
               System.out.println("Original expressions :" + expression);
               System.out.println("evaluation/expected result :"+ExpressionSolver.evaluate(expression));
           }
       } catch (Exception e) {
           // TODO: handle exception
           e.printStackTrace();
       }
   }
}

expressions.txt

30 + 10 - 3 * 6 + 12 / 2
22 + 10 - 3 * 6 + 12 / 2

OUTPUT:

Enter the file name :expressions.txt
Original expressions :30 + 10 - 3 * 6 + 12 / 2
evaluation/expected result :28
Original expressions :22 + 10 - 3 * 6 + 12 / 2
evaluation/expected result :20

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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