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 



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

<p>The program takes an expression as a command-line argument in one string.</p>

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

<p>The program scans each token in the <strong>for</strong> loop (lines 36–72). If a token is empty, skip it (line 38). If a token is an operand, push it to <strong>operandStack</strong> (line 70). If a token is a <strong>+</strong> or <strong>–</strong> operator (line 39), process all the operators from the top of <strong>operatorStack</strong>, if any (lines 41–43), and push the newly scanned operator into the stack (line 46). If a token is a ***** or <strong>/</strong> operator (line 48), process all the ***** and <strong>/</strong> operators from the top of <strong>operatorStack</strong>, 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 <strong>operatorStack</strong>. If a token is a <strong>)</strong> symbol (line 60), process all the operators from the top of <strong>operatorStack</strong> until seeing the <strong>)</strong> symbol (lines 62–64) and pop the <strong>)</strong> symbol from the stack.</p>
<p>After all tokens are considered, the program processes the remaining operators in <strong>operatorStack</strong> (lines 75–77).</p>

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


          

            
        </character></integer></character></integer>

The above is the detailed content of Case Study: Evaluating Expressions. For more information, please follow other related articles on the PHP Chinese website!