Expression Evaluation Using Stack

Learn Expression Evaluation Using Stack with practical examples, explanations, best practices, and real-world coding techniques.

What Is Expression Evaluation?

Expression evaluation is the process of calculating the result of an expression containing values, operators, and possibly parentheses.

For example, the expression 5 + 3 * 2 contains numbers and arithmetic operators. To evaluate it correctly, the program must consider operator precedence and the order in which operations should be performed.

Stacks provide a natural way to process expressions because operators and operands often need to be temporarily stored and retrieved in LIFO (Last In, First Out) order.

Example: In the postfix expression 5 3 + 2 *, the stack stores operands until an operator is encountered. The + operator uses the latest two operands, and the result is pushed back onto the stack.

Why Are Stacks Used for Expressions?

Arithmetic expressions can contain nested operations and operators with different precedence levels. A stack allows a program to temporarily store values or operators and process them when the required information becomes available.

Expression processing commonly uses one or two stacks:

  • An operand stack stores numbers or evaluated results.
  • An operator stack stores operators such as +, -, *, and /.

Postfix expressions can be evaluated using only an operand stack, which makes them especially useful for demonstrating stack-based expression evaluation.

Three Common Expression Notations

Arithmetic expressions can be represented in three common forms: infix, prefix, and postfix. The position of the operator changes between these representations.

Notation Example Operator Position
Infix A + B Between operands
Prefix + A B Before operands
Postfix A B + After operands

Postfix Expression Evaluation

Postfix notation is particularly convenient for stack-based evaluation because it does not require parentheses to explicitly represent operator precedence.

Consider the postfix expression: 

5 3 + 2 *

This represents: 

(5 + 3) * 2

The stack processes the expression from left to right:

  1. Push 5.
  2. Push 3.
  3. Encounter +, so pop 3 and 5, calculate 5 + 3, and push 8.
  4. Push 2.
  5. Encounter *, so pop 2 and 8, calculate 8 * 2, and push 16.
  6. The final stack value is 16.

Postfix Evaluation Algorithm

The basic algorithm is straightforward:

  1. Create an empty stack.
  2. Read the postfix expression from left to right.
  3. If the token is an operand, push it onto the stack.
  4. If the token is an operator, pop the required operands.
  5. Apply the operator to the operands.
  6. Push the result back onto the stack.
  7. After processing all tokens, the stack should contain the final result.

Basic JavaScript Implementation

The following implementation evaluates a space-separated postfix expression containing the basic arithmetic operators. 

function evaluatePostfix(expression) {
  const stack = [];

  for (const token of expression.split(" ")) {
    if (!isNaN(token)) {
      stack.push(Number(token));
      continue;
    }

    const right = stack.pop();
    const left = stack.pop();

    switch (token) {
      case "+":
        stack.push(left + right);
        break;

      case "-":
        stack.push(left - right);
        break;

      case "*":
        stack.push(left * right);
        break;

      case "/":
        stack.push(left / right);
        break;
    }
  }

  return stack.pop();
}

console.log(evaluatePostfix("5 3 + 2 *"));
// 16

Why Operand Order Matters

For addition and multiplication, reversing the operands does not change the result. However, subtraction and division are not commutative, so the order in which values are popped from the stack is important.

Suppose the stack contains: 

[10, 4]

When the operator is -, the first value popped is the right operand and the second value popped is the left operand. 

right = 4
left = 10

result = left - right
       = 10 - 4
       = 6

Using right - left would produce an incorrect result.

Step-by-Step Evaluation Example

Consider: 

8 2 / 3 -

The expression represents: 

(8 / 2) - 3
Token Action Stack
8 Push [8]
2 Push [8, 2]
/ 8 / 2 [4]
3 Push [4, 3]
- 4 - 3 [1]

The final result is 1.

Handling Negative Numbers

A production-quality expression evaluator should distinguish between an operator such as - and a negative numeric value such as -5.

If the input format guarantees that negative numbers are represented as complete operands, the evaluator can treat them as numbers during tokenization. 

console.log(evaluatePostfix("-5 3 +"));
// -2

The exact handling depends on the expression format and tokenizer being used.

Handling Invalid Expressions

A robust evaluator should validate the expression instead of assuming that every input is valid. An operator requires enough operands to perform the operation.

For example: 

5 +

is incomplete because the + operator requires two operands. A safe implementation should detect this condition before calling pop() twice.

A Safer Postfix Evaluator

The following implementation validates the number of operands and rejects unknown tokens. 

function evaluatePostfix(expression) {
  const stack = [];
  const tokens = expression.trim().split(/\s+/);

  for (const token of tokens) {
    if (!isNaN(token)) {
      stack.push(Number(token));
      continue;
    }

    if (!["+", "-", "*", "/"].includes(token)) {
      throw new Error(`Unknown token: ${token}`);
    }

    if (stack.length < 2) {
      throw new Error("Invalid expression");
    }

    const right = stack.pop();
    const left = stack.pop();

    let result;

    switch (token) {
      case "+":
        result = left + right;
        break;

      case "-":
        result = left - right;
        break;

      case "*":
        result = left * right;
        break;

      case "/":
        if (right === 0) {
          throw new Error("Division by zero");
        }

        result = left / right;
        break;
    }

    stack.push(result);
  }

  if (stack.length !== 1) {
    throw new Error("Invalid expression");
  }

  return stack[0];
}

console.log(evaluatePostfix("5 3 + 2 *"));
// 16

Evaluating Prefix Expressions

Prefix expressions can also be evaluated using a stack. The main difference is the direction in which the expression is processed.

Consider: 

* + 5 3 2

This represents: 

(5 + 3) * 2

A common stack-based approach is to scan the tokens from right to left. Operands are pushed onto the stack, while operators pop the required operands and push the result. 

function evaluatePrefix(expression) {
  const stack = [];
  const tokens = expression.trim().split(/\s+/);

  for (let i = tokens.length - 1; i >= 0; i--) {
    const token = tokens[i];

    if (!isNaN(token)) {
      stack.push(Number(token));
      continue;
    }

    const left = stack.pop();
    const right = stack.pop();

    switch (token) {
      case "+":
        stack.push(left + right);
        break;
      case "-":
        stack.push(left - right);
        break;
      case "*":
        stack.push(left * right);
        break;
      case "/":
        stack.push(left / right);
        break;
    }
  }

  return stack.pop();
}

console.log(evaluatePrefix("* + 5 3 2"));
// 16

Infix Expression Evaluation

Infix expressions are the notation developers use most frequently in normal arithmetic: 

5 + 3 * 2

Unlike postfix notation, an infix expression requires the evaluator to understand operator precedence, associativity, and parentheses.

A common stack-based approach uses:

  • One stack for operands or values.
  • One stack for operators.

Operators are pushed and removed according to their precedence. Parentheses are also handled by the operator stack.

Operator Precedence

Operator precedence determines which operation should be performed first.

Operator Typical Precedence Purpose
*, / Higher Multiplication and division
+, - Lower Addition and subtraction

For example: 

5 + 3 * 2

is evaluated as: 

5 + (3 * 2)
= 5 + 6
= 11

Converting Infix to Postfix

One practical strategy for evaluating infix expressions is to first convert them into postfix notation. The conversion can be performed using an operator stack.

For example: 

Infix:
5 + 3 * 2

Postfix:
5 3 2 * +

The postfix expression can then be evaluated using the simpler operand-stack algorithm.

Expression Evaluation and Compilers

Expression evaluation is an important concept in compiler and interpreter design. A language processor must understand tokens, operators, operands, precedence, grouping, and the structure of an expression before it can produce a result or executable representation.

Stack-based techniques are therefore closely related to parsing and expression processing. The simple postfix example is a useful way to understand the underlying mechanics before working with complete expression parsers.

Time and Space Complexity

For a postfix expression containing n tokens, each token is processed once.

Metric Complexity Reason
Time O(n) Each token is processed once
Space O(n) The operand stack may contain up to n values

Common Mistakes

  • Using the wrong operand order for subtraction and division.
  • Forgetting that an operator requires two operands in binary arithmetic.
  • Ignoring operator precedence when evaluating infix expressions.
  • Treating an invalid token as a number.
  • Not checking for division by zero.
  • Assuming the final stack can contain multiple values in a valid postfix expression.
  • Confusing postfix notation with prefix notation.

When to Use a Stack for Expression Problems

A stack is a strong choice when expression processing involves operators that need to wait until their operands are available or when nested operations must be resolved in reverse order.

  • Evaluating postfix expressions.
  • Evaluating prefix expressions.
  • Converting infix expressions to postfix or prefix.
  • Handling parentheses and nested expressions.
  • Processing operator precedence.
  • Building simple expression evaluators.

Key Takeaways

  • Stacks are widely used in expression evaluation because they follow LIFO ordering.
  • Postfix expressions can be evaluated using a single operand stack.
  • Operands are pushed onto the stack.
  • Operators pop operands, perform calculations, and push the result back.
  • For subtraction and division, the second value popped is the left operand.
  • Prefix expressions can be evaluated by scanning from right to left.
  • Infix expressions require handling precedence, associativity, and parentheses.
  • Infix expressions can be converted to postfix before evaluation.
  • A standard postfix evaluation algorithm runs in O(n) time and O(n) additional space.

Code Examples 

function evaluatePostfix(expression) {
  const stack = [];

  for (const token of expression.trim().split(/\s+/)) {
    if (!isNaN(token)) {
      stack.push(Number(token));
      continue;
    }

    const right = stack.pop();
    const left = stack.pop();

    switch (token) {
      case "+":
        stack.push(left + right);
        break;

      case "-":
        stack.push(left - right);
        break;

      case "*":
        stack.push(left * right);
        break;

      case "/":
        stack.push(left / right);
        break;
    }
  }

  return stack.pop();
}

console.log(evaluatePostfix("5 3 + 2 *"));
// 16
    
function evaluatePrefix(expression) {
  const stack = [];
  const tokens = expression.trim().split(/\s+/);

  for (let i = tokens.length - 1; i >= 0; i--) {
    const token = tokens[i];

    if (!isNaN(token)) {
      stack.push(Number(token));
      continue;
    }

    const left = stack.pop();
    const right = stack.pop();

    switch (token) {
      case "+":
        stack.push(left + right);
        break;

      case "-":
        stack.push(left - right);
        break;

      case "*":
        stack.push(left * right);
        break;

      case "/":
        stack.push(left / right);
        break;
    }
  }

  return stack.pop();
}

console.log(evaluatePrefix("* + 5 3 2"));
// 16
    
function evaluatePostfix(expression) {
  const stack = [];
  const tokens = expression.trim().split(/\s+/);

  for (const token of tokens) {
    if (!isNaN(token)) {
      stack.push(Number(token));
      continue;
    }

    if (!["+", "-", "*", "/"].includes(token)) {
      throw new Error(`Unknown token: ${token}`);
    }

    if (stack.length < 2) {
      throw new Error("Invalid expression");
    }

    const right = stack.pop();
    const left = stack.pop();

    if (token === "/" && right === 0) {
      throw new Error("Division by zero");
    }

    let result;

    switch (token) {
      case "+":
        result = left + right;
        break;

      case "-":
        result = left - right;
        break;

      case "*":
        result = left * right;
        break;

      case "/":
        result = left / right;
        break;
    }

    stack.push(result);
  }

  if (stack.length !== 1) {
    throw new Error("Invalid expression");
  }

  return stack[0];
}

console.log(evaluatePostfix("10 2 / 3 +"));
// 8

Pro Tip

When evaluating postfix expressions, remember that the first value popped is the right operand and the second value popped is the left operand. This detail is critical for subtraction and division.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.