Expression Evaluation Using Stacks

Stacks are among the most elegant data structures in computer science precisely because their behavior — last in, first out — mirrors the way nested structures naturally unfold. When you read a mathematical expression like ((3 + 4) * (2 - 1)), you intuitively resolve the innermost parentheses first, work outward, and keep track of where you are in the nesting. A stack does exactly the same thing algorithmically. This makes stacks the standard building block in compilers, interpreters, and calculators whenever expressions must be parsed and evaluated correctly.

Understanding expression evaluation with stacks requires grasping several interrelated ideas: why the stack's structure fits the problem so naturally, how to use one to verify that parentheses are balanced, the three notations in which expressions can be written, the algorithm that converts human-readable infix notation into machine-friendly postfix notation, how to evaluate postfix expressions efficiently using a stack, and how operator precedence and associativity are woven into all of the above. Each of these ideas builds on the previous one, and together they form a complete picture of stack-based expression processing.

Why Stacks Are Natural for Expression Parsing

Mathematical expressions are inherently recursive. A parenthesized sub-expression can contain another parenthesized sub-expression, which can contain yet another, and so on. When a parser encounters an opening parenthesis, it must set aside whatever it was doing and begin working on the inner expression. When it reaches the matching closing parenthesis, it needs to return to exactly the point it left off — and "exactly the point it left off" is the definition of what the top of a stack gives you.

Consider what happens when you evaluate 2 * (3 + (4 - 1)) mentally. You read 2 * and then realize you cannot proceed until the parenthesized group is resolved. You "save" the multiplication and dive into 3 + (4 - 1). Again you save the addition and resolve 4 - 1 = 3. Now you can finish the addition: 3 + 3 = 6. Now you can finish the multiplication: 2 * 6 = 12. At each level, you pushed a pending operation onto a mental stack; at each closing parenthesis, you popped and completed the operation. A program does this with an explicit stack data structure.

This pattern appears everywhere in software: the call stack of a running program uses the same mechanism to track which function called which. Compilers, calculators, and interpreters all exploit it. There is no coincidence here — the problem structure dictates the data structure.

Balancing Parentheses

One of the simplest and most practically useful applications of a stack is checking whether all grouping symbols in an expression are properly balanced. "Grouping symbols" include round parentheses (), curly braces {}, and square brackets []. A well-formed expression must open and close each symbol in the correct order.

The algorithm is straightforward:

• Read the expression character by character from left to right.
• Whenever an opening symbol — (, {, or [ — is encountered, push it onto the stack.
• Whenever a closing symbol — ), }, or ] — is encountered, check whether the stack is empty. If it is, there is no matching opener, so the expression is unbalanced. If the stack is not empty, pop the top element and verify that it is the corresponding opener. A ) must match (, a } must match {, and a ] must match [. If the wrong opener is on top, there is a mismatch and the expression is unbalanced.
• After the entire input has been read, if the stack is empty, the expression is balanced. If the stack still contains items, there are unclosed openers, and the expression is unbalanced.

Let us trace through two examples. First, the balanced expression {[()()]}:

Now consider the unbalanced expression ([)]:

Even though every opener eventually has a closer, the nesting order is wrong. The stack catches this immediately because the top of the stack always holds the most recently opened, not-yet-closed symbol — and that is precisely the one that must be closed next.

In Python, this algorithm looks like the following:

def is_balanced(expression):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
    for ch in expression:
        if ch in '({[':
            stack.append(ch)
        elif ch in ')}]':
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced("{[()()]}"))   # True
print(is_balanced("([)]"))       # False
print(is_balanced("((()"))       # False

Infix, Prefix, and Postfix Notation

Humans write arithmetic in infix notation, where operators appear between their operands: 3 + 4, a * b + c. Infix notation is readable, but it is ambiguous without additional rules. When you see 3 + 4 * 2, you need to know that * has higher precedence than + in order to compute 3 + 8 = 11 rather than 14. Parentheses can override precedence, further complicating parsing.

Prefix notation (also called Polish notation) places the operator before its operands. The expression 3 + 4 becomes + 3 4, and 3 + 4 * 2 becomes + 3 * 4 2. No parentheses or precedence rules are needed; the structure of the expression is unambiguous by position alone.

Postfix notation (also called Reverse Polish Notation, or RPN) places the operator after its operands. 3 + 4 becomes 3 4 +, and 3 + 4 * 2 becomes 3 4 2 * +. Like prefix, postfix requires no parentheses and encodes operator order explicitly. Postfix is especially convenient for stack-based evaluation, which is why it is preferred in expression evaluation algorithms and was used in many early calculators (including Hewlett-Packard's famous HP-35).

The key insight is that postfix notation makes evaluation order completely explicit. A machine can evaluate a postfix expression by making a single left-to-right pass with a stack, with no need to look ahead or apply precedence rules at evaluation time. All the complexity of precedence and associativity is resolved once, during the conversion from infix to postfix.

Converting Infix to Postfix: The Shunting-Yard Algorithm

The Shunting-Yard Algorithm, devised by Edsger Dijkstra in 1961 (named after the railway shunting yard analogy), converts an infix expression into postfix notation using a stack for operators and a queue (or simple list) for output. The algorithm handles operator precedence, left and right associativity, and parentheses.

The rules are:

• Operand (number or variable): Send it directly to the output.
• Operator: Before pushing the new operator onto the stack, pop and send to output any operator already on the stack whose precedence is greater than the new operator's precedence, or equal to the new operator's precedence if that operator is left-associative. Stop popping when the top of the stack is a left parenthesis or is of lower precedence (for left-associative) / lower or equal precedence (for right-associative). Then push the new operator.
• Left parenthesis (: Push it onto the stack as a marker.
• Right parenthesis ): Pop operators from the stack and send them to output until a left parenthesis is found on top. Discard the left parenthesis (do not send it to output). If no left parenthesis is found, the expression has mismatched parentheses.
• End of input: Pop all remaining operators from the stack and append them to the output. Any remaining parenthesis at this point indicates a mismatch.

Let us assign precedence values and associativity:

Now trace the conversion of 3 + 4 * 2 / ( 1 - 5 ) ^ 2:

The postfix result is 3 4 2 * 1 5 - 2 ^ / +. You can verify this is correct: 4*2=8, 1-5=-4, (-4)^2=16, 8/16=0.5, 3+0.5=3.5. Indeed the original infix expression also evaluates to 3.5.

A Python implementation of the Shunting-Yard Algorithm:

def infix_to_postfix(tokens):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    right_assoc = {'^'}
    output = []
    stack = []

    for token in tokens:
        if token not in precedence and token not in '()':
            # Operand: numbers or variable names
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # discard '('
        else:
            # Operator
            while (stack and stack[-1] != '(' and
                   stack[-1] in precedence and
                   (precedence[stack[-1]] > precedence[token] or
                    (precedence[stack[-1]] == precedence[token]
                     and token not in right_assoc))):
                output.append(stack.pop())
            stack.append(token)

    while stack:
        output.append(stack.pop())

    return output

tokens = ['3','+','4','*','2','/','(','1','-','5',')','*','2']
print(infix_to_postfix(tokens))
# Output: ['3', '4', '2', '*', '1', '5', '-', '2', '*', '/', '+']

Evaluating Postfix Expressions with a Stack

Once an expression is in postfix form, evaluating it is remarkably simple. The algorithm makes a single left-to-right scan:

• If the current token is an operand, push it onto the stack.
• If the current token is a binary operator, pop two operands from the stack — the first popped is the right operand, and the second popped is the left operand. Apply the operator, and push the result back onto the stack.
• After the entire expression has been processed, the stack contains exactly one value: the final result.

Let us evaluate 3 4 2 * 1 5 - 2 ^ / + step by step:

The result is 3.5, as expected. Notice that the order of popping matters: when evaluating a - b, the first value popped is b (the right operand) and the second is a (the left operand). For commutative operations like addition and multiplication, order does not affect the result, but for subtraction, division, and exponentiation it does.

A Python implementation:

def evaluate_postfix(tokens):
    stack = []
    for token in tokens:
        if token == '+':
            b, a = stack.pop(), stack.pop()
            stack.append(a + b)
        elif token == '-':
            b, a = stack.pop(), stack.pop()
            stack.append(a - b)
        elif token == '*':
            b, a = stack.pop(), stack.pop()
            stack.append(a * b)
        elif token == '/':
            b, a = stack.pop(), stack.pop()
            stack.append(a / b)
        elif token == '^':
            b, a = stack.pop(), stack.pop()
            stack.append(a ** b)
        else:
            stack.append(float(token))
    return stack[0]

postfix = ['3','4','2','*','1','5','-','2','^','/','+']
print(evaluate_postfix(postfix))  # 3.5

This algorithm operates in O(n) time where n is the number of tokens, since each token is processed exactly once and each stack operation is O(1). There is no backtracking, no lookahead, and no recursive descent required. This linear-time complexity is one of the strongest practical arguments for converting expressions to postfix before evaluation.

Operator Precedence and Associativity in Stack-Based Parsing

Operator precedence determines which operations bind more tightly to their operands. In standard arithmetic, multiplication and division have higher precedence than addition and subtraction. Exponentiation typically has the highest precedence. If these rules are not correctly encoded in the Shunting-Yard Algorithm, the resulting postfix expression will not evaluate to the mathematically correct answer.

The mechanism is simple but must be applied carefully: when a new operator is being pushed onto the stack, the algorithm compares its precedence to that of the operator currently on top of the stack. If the top operator has greater or equal precedence (subject to associativity, discussed below), it must be popped and sent to output before the new operator is pushed. This ensures that higher-precedence operations appear in the postfix output before lower-precedence ones, so they are applied first during evaluation.

Associativity governs how operators of equal precedence are grouped when no parentheses are present. Consider 8 - 3 - 2. Mathematically this is (8 - 3) - 2 = 3, not 8 - (3 - 2) = 7. Subtraction is left-associative: operations at the same level group from left to right. The Shunting-Yard Algorithm handles this by popping an operator of equal precedence from the stack (sending it to output) before pushing the new operator of the same precedence — thereby ensuring the left operation appears in the postfix output first.

Exponentiation, by mathematical convention, is right-associative: 2 ^ 3 ^ 2 means 2 ^ (3 ^ 2) = 2 ^ 9 = 512, not (2 ^ 3) ^ 2 = 8 ^ 2 = 64. For right-associative operators, when the new operator has the same precedence as the top of the stack, the stack is not popped; the new operator is pushed on top. This leaves the earlier exponentiation lower on the stack, meaning it will be applied after the one just pushed — achieving right-to-left grouping.

Getting these rules wrong produces subtly incorrect results that can be difficult to debug. For example, if a parser incorrectly treated - as right-associative, 8 - 3 - 2 would yield 7 instead of 3. The combination of a precedence table and an associativity flag for each operator, checked at the moment an operator is pushed onto the stack, is what makes the Shunting-Yard Algorithm both correct and complete for standard arithmetic expressions.

In summary, the stack is not merely a convenient data structure for expression parsing — it is the natural data structure for it. The nesting structure of expressions, the need to remember pending operations while resolving inner ones, the linear-time complexity of postfix evaluation, and the clean encoding of precedence and associativity in a single algorithm all reinforce why stacks have been the foundation of expression evaluation since the earliest days of compiler design.