Introduction

Infix expressions are easy for humans to read but harder for machines to evaluate directly because operator precedence and parentheses must be respected. A standard solution is Dijkstra’s shunting-yard algorithm, which converts infix tokens to postfix order. Postfix form can then be evaluated with a simple stack machine.

Why Infix Parsing Is Nontrivial

Expression 3 + 4 * 2 should evaluate as 3 + (4 * 2), not (3 + 4) * 2. Any parser must handle:

• Operator precedence.
• Operator associativity.
• Parenthesized groups.

Naive left-to-right evaluation fails for many valid expressions.

Shunting-Yard at a Glance

The algorithm maintains two structures:

• Output queue for resulting postfix tokens.
• Operator stack for pending operators and parentheses.

High-level rules:

1. Numbers go to output queue.
2. Operators pop higher-precedence stack operators to output first.
3. Left parenthesis is pushed to stack.
4. Right parenthesis pops operators until matching left parenthesis.
5. Remaining operators are flushed at end.

This runs in linear time over token count.

Python Conversion Implementation

1def infix_to_postfix(tokens):
2    precedence = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
3    right_assoc = {"^"}
4
5    output = []
6    ops = []
7
8    for tok in tokens:
9        if tok.replace('.', '', 1).isdigit():
10            output.append(tok)
11        elif tok in precedence:
12            while ops and ops[-1] in precedence:
13                top = ops[-1]
14                should_pop = (
15                    (tok not in right_assoc and precedence[tok] <= precedence[top])
16                    or (tok in right_assoc and precedence[tok] < precedence[top])
17                )
18                if should_pop:
19                    output.append(ops.pop())
20                else:
21                    break
22            ops.append(tok)
23        elif tok == "(":
24            ops.append(tok)
25        elif tok == ")":
26            while ops and ops[-1] != "(":
27                output.append(ops.pop())
28            if not ops:
29                raise ValueError("Mismatched parentheses")
30            ops.pop()
31        else:
32            raise ValueError(f"Unknown token: {tok}")
33
34    while ops:
35        if ops[-1] in {"(", ")"}:
36            raise ValueError("Mismatched parentheses")
37        output.append(ops.pop())
38
39    return output
40
41expr = ["3", "+", "4", "*", "2", "/", "(", "1", "-", "5", ")", "^", "2"]
42print(infix_to_postfix(expr))

This version handles precedence, associativity, and parenthesis validation.

Evaluating Postfix Output

Once in postfix, evaluation is straightforward using one value stack.

1import operator
2
3def eval_postfix(tokens):
4    fn = {
5        "+": operator.add,
6        "-": operator.sub,
7        "*": operator.mul,
8        "/": operator.truediv,
9        "^": operator.pow,
10    }
11
12    st = []
13    for t in tokens:
14        if t in fn:
15            b = st.pop()
16            a = st.pop()
17            st.append(fn[t](a, b))
18        else:
19            st.append(float(t))
20
21    if len(st) != 1:
22        raise ValueError("Invalid postfix expression")
23    return st[0]
24
25post = infix_to_postfix(["3", "+", "4", "*", "2"])
26print(eval_postfix(post))

Separating parse and evaluate stages improves testability and diagnostics.

Handling Unary Operators and Functions

Basic shunting-yard examples often skip unary minus and function calls. Production parsers must extend tokenization and precedence logic for:

• Unary minus and plus.
• Function identifiers such as sin.
• Argument separators like commas.

You can still use shunting-yard, but token grammar needs to be richer.

Alternative Parsing Strategies

Shunting-yard is not the only approach. Other valid designs include:

• Pratt parsers.
• Recursive descent with precedence climbing.
• Parser generators with explicit grammar files.

Shunting-yard stays popular because it is compact and easy to reason about for calculator-like grammars.

Error Handling Recommendations

Good parser UX depends on clear errors. Include:

• Token position in error messages.
• Distinct errors for unknown tokens versus mismatched parentheses.
• Defensive checks for missing operands.

This matters more than micro-optimizing parser loops in most applications.

Common Pitfalls

• Ignoring associativity, especially for exponentiation.
• Mixing tokenization and parsing in one tangled function.
• Failing to detect mismatched parentheses reliably.
• Treating unary minus as binary subtraction in all contexts.
• Returning generic parse failures without useful diagnostics.

Summary

• Shunting-yard is a standard algorithm for parsing infix expressions.
• It converts infix to postfix using an operator stack and output queue.
• Correct precedence and associativity handling is essential.
• Postfix evaluation is then a simple stack process.
• Robust tokenization and clear errors are key for production parsers.