Expression Evaluation (Stacks & Queues)

Expression Evaluation (Stacks & Queues)

Problem Scenario / Typical Use Case

Imagine you are building a calculator or compiler, and you need to compute the value of arithmetic expressions like 3 + 2 * (1 + 5).

Naively evaluating expressions from left to right ignores operator precedence and parentheses. Stacks & Queues provide a systematic way to parse and evaluate expressions correctly, respecting the proper order of operations.

Basic Idea

Expression evaluation techniques include:

1. Infix to Postfix / Prefix Conversion: Use a stack to reorder operators and operands for easy computation.
2. Direct Evaluation Using Stacks: Maintain an operator stack and an operand stack to evaluate in one pass.
3. Queue-Based Processing: For streaming or tokenized input, queues can process elements sequentially.

Typical operations include:

• Calculating arithmetic expressions with proper precedence.
• Validating expressions and parentheses.
• Supporting compilers, interpreters, or calculators.

Advantages

• Correct Operator Precedence: Stacks allow handling parentheses and precedence naturally.
• Linear Complexity: Expressions can often be evaluated in O(n) time.
• Versatility: Works for integer, floating-point, and complex expressions.

Limitations / Considerations

• Memory Usage: Stacks may grow proportional to expression length or depth of parentheses.
• Operator Handling: Must carefully define precedence and associativity rules.
• Edge Cases: Division by zero, invalid characters, or malformed expressions require additional checks.

Practical Examples / Thought Triggers

1. Basic Arithmetic Evaluation: Compute 2 + 3 * 4 correctly respecting precedence.
2. Parentheses Handling: Evaluate (1 + 2) * (3 + 4) correctly.
3. Postfix / Prefix Evaluation: Useful for stack-based calculators or interpreters.

Thought Triggers:

• Should I convert the expression to postfix first, or evaluate directly with two stacks?
• How can I handle multi-digit numbers and whitespace efficiently?
• Can this be extended to support functions or variables in expressions?

Implementation Example

Here’s a Python example for evaluating simple arithmetic expressions using stacks:

def evaluate_expression(expr):
    def apply_op(op, b, a):
        if op == '+': return a + b
        if op == '-': return a - b
        if op == '*': return a * b
        if op == '/': return a // b  # integer division
    nums, ops = [], []
    i = 0
    while i < len(expr):
        if expr[i].isdigit():
            val = 0
            while i < len(expr) and expr[i].isdigit():
                val = val*10 + int(expr[i])
                i += 1
            nums.append(val)
        elif expr[i] in "+-*/":
            while ops and ops[-1] in "*/" and expr[i] in "+-":
                nums.append(apply_op(ops.pop(), nums.pop(), nums.pop()))
            ops.append(expr[i])
            i += 1
        elif expr[i] == '(':
            ops.append(expr[i])
            i += 1
        elif expr[i] == ')':
            while ops[-1] != '(':
                nums.append(apply_op(ops.pop(), nums.pop(), nums.pop()))
            ops.pop()
            i += 1
        else:
            i += 1  # skip spaces
    while ops:
        nums.append(apply_op(ops.pop(), nums.pop(), nums.pop()))
    return nums[0]

# Example usage
expr = "3 + 2 * (1 + 5)"
print(evaluate_expression(expr))
# Output: 15

This demonstrates stack-based evaluation, respecting operator precedence and parentheses.

Related Articles

• Stacks & Queues Fundamentals: Core operations are essential for expression evaluation.
• Binary Tree Traversals: Expression trees can be evaluated using traversal techniques.
• Backtracking & Recursive Search: Recursive evaluation is an alternative to stack-based evaluation.