Case Study: Evaluating Expressions

Stacks can be used to evaluate expressions. Stacks and queues have many applications. This section gives an application that uses stacks to evaluate expressions. You can enter an arithmetic expression from Google to evaluate the expression, as shown in Figure below.

How does Google evaluate an expression? This section presents a program that evaluates a compound expression with multiple operators and parentheses (e.g., (15 + 2) * 34 – 2). For simplicity, assume that the operands are integers and the operators are of four types: +, -, **, and */.

The problem can be solved using two stacks, named operandStack and operatorStack, for storing operands and operators, respectively. Operands and operators are pushed into the stacks before they are processed. When an operator is processed, it is popped from operatorStack and applied to the first two operands from operandStack (the two operands are popped from operandStack). The resultant value is pushed back to operandStack.

The algorithm proceeds in two phases:

Phase 1: Scanning the expression

The program scans the expression from left to right to extract operands, operators, and the parentheses.

1. If the extracted item is an operand, push it to operandStack.
2. If the extracted item is a + or - operator, process all the operators at the top of operatorStack and push the extracted operator to operatorStack.
3. If the extracted item is a ***** or / operator, process the ***** or / operators at the top of operatorStack and push the extracted operator to operatorStack.
4. If the extracted item is a ( symbol, push it to operatorStack.
5. If the extracted item is a ) symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack.

Phase 2: Clearing the stack

Repeatedly process the operators from the top of operatorStack until operatorStack is empty.

Table below shows how the algorithm is applied to evaluate the expression (1 + 2) * 4 - 3.

The code below gives the program, and Figure below shows some sample output.

package demo;
import java.util.Stack;

public class EvaluateExpression {

    public static void main(String[] args) {
        // Check number of arguments passed
        if(args.length != 1) {
            System.out.println("Usage: java EvaluateExpression \"expression\"");
            System.exit(1);
        }

        try {
            System.out.println(evaluateExpression(args[0]));
        }
        catch(Exception ex) {
            System.out.println("Wrong expression: " + args[0]);
        }
    }

    /** Evaluate an expression */
    public static int evaluateExpression(String expression) {
        // Create operandStack to store operands
        Stack<Integer> operandStack = new Stack<>();

        // Create operatorStack to store operators
        Stack<Character> operatorStack = new Stack<>();

        // Insert blanks around (, ), +, -, /, and *
        expression = insertBlanks(expression);

        // Extract operands and operators
        String[] tokens = expression.split(" ");

        // Phase 1: Scan tokens
        for(String token: tokens) {
            if(token.length() == 0) // Blank space
                continue; // Back to the while loop to extract the next token
            else if(token.charAt(0) == '+' || token.charAt(0) == '-') {
                // Process all +, -, *, / in the top of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-' || operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(operandStack, operatorStack);
                }

                // Push the + or - operator into the operator stack
                operatorStack.push(token.charAt(0));
            }
            else if(token.charAt(0) == '*' || token.charAt(0) == '/') {
                // Process all *, / in the top of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(operandStack, operatorStack);
                }

                // Push the * or / operator into the operator stack
                operatorStack.push(token.charAt(0));
            }
            else if(token.trim().charAt(0) == '(') {
                operatorStack.push('('); // Push '(' to stack
            }
            else if(token.trim().charAt(0) == ')') {
                // Process all the operators in the stack until seeing '('
                while(operatorStack.peek() != '(') {
                    processAnOperator(operandStack, operatorStack);
                }

                operatorStack.pop(); // Pop the '(' symbol from the stack
            }
            else {
                // Push an operand to the stack
                operandStack.push(Integer.valueOf(token));
            }
        }

        // Phase 2: Process all the remaining operators in the stack
        while(!operatorStack.isEmpty()) {
            processAnOperator(operandStack, operatorStack);
        }

        // Return the result
        return operandStack.pop();
    }

    /** Process one operator: Take an operator from operatorStack and apply it on the operands in the operandStack */
    public static void processAnOperator(Stack<Integer> operandStack, Stack<Character> operatorStack) {
        char op = operatorStack.pop();
        int op1 = operandStack.pop();
        int op2 = operandStack.pop();
        if(op == '+')
            operandStack.push(op2 + op1);
        else if(op == '-')
            operandStack.push(op2 - op1);
        else if(op == '*')
            operandStack.push(op2 * op1);
        else if(op == '/')
            operandStack.push(op2 / op1);
    }

    public static String insertBlanks(String s) {
        String result = "";

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == ')' || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/')
                result += " " + s.charAt(i) + " ";
            else
                result += s.charAt(i);
        }

        return result;
    }

}

You can use the GenericStack class provided by the book or the java.util.Stack class defined in the Java API for creating stacks. This example uses the java.util.Stack class. The program will work if it is replaced by GenericStack.

The program takes an expression as a command-line argument in one string.

The evaluateExpression method creates two stacks, operandStack and operatorStack (lines 24, 27), and extracts operands, operators, and parentheses delimited by space (lines 30–33). The insertBlanks method is used to ensure that operands, operators, and parentheses are separated by at least one blank (line 30).

The program scans each token in the for loop (lines 36–72). If a token is empty, skip it (line 38). If a token is an operand, push it to operandStack (line 70). If a token is a + or – operator (line 39), process all the operators from the top of operatorStack, if any (lines 41–43), and push the newly scanned operator into the stack (line 46). If a token is a ***** or / operator (line 48), process all the ***** and / operators from the top of operatorStack, if any (lines 50–51), and push the newly scanned operator to the stack (line 55). If a token is a ( symbol (line 57), push it into operatorStack. If a token is a ) symbol (line 60), process all the operators from the top of operatorStack until seeing the ) symbol (lines 62–64) and pop the ) symbol from the stack.

After all tokens are considered, the program processes the remaining operators in operatorStack (lines 75–77).

The processAnOperator method (lines 84–96) processes an operator. The method pops the operator from operatorStack (line 85) and pops two operands from operandStack (lines 86–87). Depending on the operator, the method performs an operation and pushes the result of the operation back to operandStack (lines 89, 91, 93, 95).