Case Study: Evaluating Expressions
Tags: java, programming, learning, beginners
Published: 2024-07-09 22:26:22

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cb6x9tfkz3dbz732nnoi.png)

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**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p705s8tsymkilfqo6m51.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5vixtlzrfu1y2uwg12i4.png)

```
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).