How do you build a calculator and tokenizer in a coding interview?

In this article

1. Before you start
2. Why interviewers ask this
3. Calculators and tokenizers from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the machine coding rounds guide, which collects applied coding problems of this kind. The "tokenizer" here is the compiler kind that cuts source text into pieces. Tokenizers for large language models, which split text for a neural network, are a different tool and are not covered.

Why interviewers ask this

A calculator question is short to state and easy to get half right. Candidates report tasks such as evaluating a reverse Polish notation (RPN) list (LeetCode 150), evaluating an infix expression with parentheses such as 1+2*(3-(65+2)*2), and tokenizing an input command by applying the longest matching pattern first. These reports come from candidates in interviews at AI labs and large tech companies; no public source confirms that any one company asks them.

The question separates candidates on three things. Do they see that text must be cut into tokens before it can be evaluated? Do they handle precedence and parentheses with a method rather than a pile of special cases? Do they know the edge cases: multi-digit numbers, pop order, rounding of negative division? A weak answer scans characters and patches bugs. A strong answer names the stages, states the cost of each, and tests one tricky input. The same shape appears in the low level design questions that ask for a small parser or rules engine.

Calculators and tokenizers from first principles

Tokenizer

A tokenizer is a scanner that reads a string left to right and groups its characters into tokens, such as numbers, names and operators, without checking whether those tokens form a sensible statement.

Maximal munch

Maximal munch, also called longest match, is the rule that a tokenizer consumes as many input characters as possible for each token, so >= becomes one token instead of > followed by =.

Reverse Polish notation

Reverse Polish notation (RPN), also called postfix, is a way of writing an expression with each operator after its operands, so 3 + 4 becomes 3 4 +, which needs no parentheses and no precedence rules to evaluate.

Shunting yard algorithm

The shunting yard algorithm is a stack-based method that converts an infix expression, with operators between operands, into postfix or a syntax tree, while respecting precedence, associativity and parentheses.

In plain words

Think of reading a sentence aloud. Your eyes first group letters into words, and only then does your mind work out what the sentence means. A calculator does the same in stages. A token is one meaningful chunk of the input, such as a number, a name or an operator. The tokenizer finds the chunks, a converter puts them in an order in which operators can be applied one at a time, and the evaluator works out the value.

The analogy breaks in one place. You know what words mean. A tokenizer knows only a list of patterns, and it understands nothing. Deciding that 1 2 + is not a sensible sum is not its job.

In one precise sentence, a calculator tokenizes the string, converts the tokens to an order in which operators can be applied one at a time, and applies them with a stack.

Step 1: Raw characters have no boundaries

Splitting an expression on spaces fails, because numbers and operators often touch. The expression 1+2*(3-(65+2)*2) has sixteen characters and no spaces, so there is nothing to split on, and cutting after every character breaks 65 into 6 and 5.¹ Real inputs also carry arbitrary spacing: LeetCode 227 accepts " 3+5 / 2 " and evaluates it to 5.

The evaluator therefore needs units larger than a character and smaller than the whole string. That unit is the token. Finding the tokens is the tokenizer's only job, and it does not check that the expression makes sense. Python's own scanner is only designed for syntactically valid code, and its behaviour on invalid input is undefined, so a production scanner needs its own error path. You now know why a tokenizer exists. Step 2 shows how it decides where one token ends.

Step 2: A tokenizer takes the longest match at every position

A tokenizer groups characters into tokens by taking the longest match at every position. At the current position it tries every token pattern and keeps the one that consumes the most characters. This is maximal munch, the longest-sequence rule that the C++ working draft (lex.pptoken) states for preprocessing tokens (see also the maximal munch overview): consume as much of the available input as possible.

Take count1>=10. The longest matches are the name count1, the comparison >= and the number 10, three tokens in all. If a shorter match won, the scanner would emit > and = separately, four tokens, and the comparison would be lost.¹ The rule applies to every token class: a multi-digit number is one token, and ++ is one token rather than two +.

When two patterns match the same length, a tie-break is needed, and the common convention is that the pattern listed first wins. The line if (count1 >= 10) total = total + rate2 * 3.5; gives fourteen tokens under this rule.¹ Input: a string and a pattern list. Output: a list of tokens. Maximal munch has known exceptions, covered under Trade-offs.

Text description of the diagram

• The longest matches are the name count1, the comparison >= and the number 10, three tokens in all.
• A shorter match would emit > and = separately, four tokens, and the comparison would be lost.

How do you find the longest matching pattern quickly?

The fast way to find the longest matching pattern is a trie, a tree built from the patterns in which each path from the root spells one pattern. The naive way tries every pattern at every position, which costs O(n × P × L) for n input characters, P patterns and a longest pattern of L characters. With a trie, you walk down from the root at each position for as long as the input allows.

You remember the last node that ends a pattern, emit that token and jump past it. The walk visits at most L nodes per position and does not depend on P, so the cost is O(n × L). Input: the string and the trie. Output: the same tokens as the naive scan, found faster. Step 3 uses the token list.

Step 3: Shunting yard turns infix tokens into postfix

The shunting yard algorithm turns tokens into postfix using an operator stack. Dijkstra invented it and first published it in November 1961, and it can output postfix or an abstract syntax tree (AST), per the shunting yard reference.

Operator precedence is the rule that decides which operator binds tighter, so * binds tighter than +. Associativity is the rule that decides the grouping of equal-precedence operators: - groups left to right, while ^ groups right to left.

The method: a number goes straight to the output. An operator first pops every stacked operator that binds tighter (or equally tight when it groups left to right), then is pushed. A ( is pushed, and a ) pops operators until the matching (. At the end, pop everything. The cost is O(n). On the reference input, 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 becomes 3 4 2 * 1 5 - 2 3 ^ ^ / +.¹ Our example becomes 1 2 3 65 2 + 2 * - * +.¹

Step 4: A second stack evaluates postfix into a value

A second stack evaluates postfix into a value. Scan the postfix tokens left to right. A number is pushed. An operator pops two values, applies itself, and pushes the result. The pop order matters: pop b first, then a, and compute a op b, because - and / are not commutative. The problem statement for LeetCode 150 shows ["2","1","+","3","*"] giving 9, which is (2 + 1) * 3, and ["4","13","5","/","+"] giving 6, which is 4 + (13 / 5).

Each token is pushed and popped at most once, so evaluation is O(n) time, and the stack never holds more than n values. At the end exactly one value remains, and that value is the answer. Postfix needs no parentheses, because the order of tokens already fixes the order of operations.

1 · Characters2 · Tokens3 · Postfix4 · ValueReplay

Step-by-step description

1. The input is a string with no boundaries.
2. Longest match groups characters into tokens.
3. An operator stack reorders the tokens.
4. A second stack evaluates the postfix.

• A tokenizer groups characters into tokens by taking the longest match.
• The shunting yard algorithm turns tokens into postfix using an operator stack.
• A second stack evaluates postfix into a value.

Worked example

The infix expression 1+2*(3-(65+2)*2) was reported by candidates in a coding task. We run it through all three stages.¹

The tokenizer reads sixteen characters and emits fifteen tokens: 1, +, 2, *, (, 3, -, (, 65, +, 2, ), *, 2, ). Shunting yard turns them into 1 2 3 65 2 + 2 * - * +. The evaluator then runs the postfix on its stack. The addition gives 67, the next multiplication gives 134, the subtraction pops 134 first as b, then 3 as a, and pushes -131, the multiplication gives -262, and the last addition gives -261.¹ The stack ends holding one number, -261, the value of the whole expression.

Text description of the diagram

• The subtraction pops 134 first as b, then 3 as a, and pushes -131.
• The stack ends holding one number, -261.

LeetCode 227 gives "3+2*2" as 7, while a left-to-right pass wrongly gives 10.¹ The truncation rows come from the third LeetCode 150 example, whose tokens evaluate to 22: it contains 6 / -132, which truncates to 0, whereas flooring would give -1.¹ Both LeetCode 227 and LeetCode 150 state that integer division truncates toward zero.

The functions below are the ones that produced these numbers.¹ The first is the tokenizer. Its regular expression lists >= before >, and findall silently skips characters that match nothing, such as spaces.

import re

# Longer operators come first: ">=" must be listed before ">".
TOKEN_RE = re.compile(r"\d+\.?\d*|[A-Za-z_]\w*|>=|<=|==|!=|\+\+|[-+*/^()<>=;]")

def tokenize(s):
    return TOKEN_RE.findall(s)

The second function is the shunting yard converter. A number goes to the output. An operator first pops every stacked operator that binds tighter, or equally tight when it groups left to right, then is pushed. A ) pops operators until the matching (.

PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
RIGHT = {"^"}  # operators that group right to left

def to_rpn(tokens):
    out, st = [], []
    for t in tokens:
        if t[0].isdigit():
            out.append(t)                      # numbers go straight out
        elif t in PREC:
            while st and st[-1] != "(" and (
                PREC[st[-1]] > PREC[t]
                or (PREC[st[-1]] == PREC[t] and t not in RIGHT)
            ):
                out.append(st.pop())           # tighter operators first
            st.append(t)
        elif t == "(":
            st.append(t)
        elif t == ")":
            while st[-1] != "(":
                out.append(st.pop())
            st.pop()                           # discard the "("
    while st:
        out.append(st.pop())
    return out

The third pair is the evaluator. trunc_div divides the absolute values and restores the sign, which truncates toward zero. In eval_rpn, b is popped before a, so a - b and a / b come out the right way round.

def trunc_div(a, b):
    q = abs(a) // abs(b)
    return q if (a < 0) == (b < 0) else -q

def eval_rpn(tokens):
    st = []
    for t in tokens:
        try:
            st.append(int(t))                  # a number: push it
            continue
        except ValueError:
            pass
        b = st.pop()                           # pop b first, then a
        a = st.pop()
        if t == "+":
            st.append(a + b)
        elif t == "-":
            st.append(a - b)
        elif t == "*":
            st.append(a * b)
        elif t == "/":
            st.append(trunc_div(a, b))
    return st[0]

The last block is the one-pass method for input without parentheses. It keeps the last operator seen, pushes signed terms on a stack, folds * and / into the top term, and sums the stack at the end.

def one_pass(s):
    s = s.replace(" ", "")
    stack, num, op = [], 0, "+"
    for ch in s + "+":                         # "+" flushes the last number
        if ch.isdigit():
            num = num * 10 + int(ch)           # build multi-digit numbers
        else:
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            elif op == "/":
                stack.append(trunc_div(stack.pop(), num))
            op, num = ch, 0
    return sum(stack)

Trade-offs and edge cases

Of the three approaches in this table, shunting yard with postfix is the one that handles both parentheses and precedence.

Left to right evaluation gives 10 for 3+2*2 where the answer is 7. One pass with a running term handles precedence but not parentheses: keep the last operator, and push each term on a stack, multiplying or dividing it into the previous term, then sum the stack at the end. That is enough when the input has no parentheses, as in LeetCode 227. The shunting yard route handles parentheses, precedence and associativity in O(n) time.

Parentheses can also be handled in one pass. That is the usual answer to LeetCode 224, which has +, -, parentheses and a unary minus. Keep a running result and a current sign. On (, push both onto a stack and restart. On ), pop them, multiply the inner result by the saved sign and add it to the saved result. A leading minus works because the sign is only a multiplier.

Recursive descent is the other common method. It writes one function per precedence level: an expression function sums terms, a term function multiplies factors, and a factor function reads a number or a bracketed expression by calling the expression function again. Nested brackets have the same shape as a nested list, where depth plays the role of parentheses. Adding a precedence level adds a function, which is how the same method extends to the type inference and abstract syntax tree task that candidates also report for a toy language.

Edge cases:

• Validation. Shunting yard does not reject every invalid input. For example, 1 2 + is not a valid infix expression but is parsed as 1 + 2. It does reject mismatched parentheses.
• Longest-match exceptions. In C++ the sequence <:: is special-cased, so < can be its own token, as the working draft (lex.pptoken) states. Researchers have added other lexical disambiguation tactics such as follow restrictions.
• Multi-digit and negative operands. LeetCode 150 carries -11 as one token, so a scanner for postfix input must not split a signed literal into a sign and a number.
• Token kinds. Python's scanner returns comments as tokens and reports every operator under one generic operator token type, with exact_type giving the specific operator.
• Rounding. Python's // floors, so use int(a / b) or divide absolute values and restore the sign when the problem says truncate.
• Unary minus. A - at the start or after ( is a sign, not a subtraction. Decide which in the tokenizer or the converter and say so.

The same tokenize-then-evaluate shape appears in a spreadsheet and dependency engine, which reads a formula before it can compute a cell, in event and log processing problems, which cut raw lines into fields, and in profiler and stack trace problems, which parse trace text.

How to answer it in an interview

The spoken structure: name the three stages, say why 65 must be one token, give the pop order, then the cost and the result.

Common mistakes

• "I split the string on spaces." (wrong) The input may have no spaces or arbitrary ones. (right) "I scan characters and group them into tokens, so 65 stays whole."
• "I evaluate left to right." (wrong) That gives 10 for 3+2*2. (right) "I respect precedence, with a stack or by converting to postfix."
• "I pop a, then b, and compute a op b." (wrong) That reverses subtraction and division. (right) "I pop b first, then a, and compute a op b."
• "I list > before >= in my regex alternation." (wrong) Python's re takes the first alternative that matches, not the longest. (right) "I list >= before >, as TOKEN_RE does, or I walk a trie."
• "Integer division is just //." (wrong) In Python // floors, so -7 / 2 gives -4. (right) "The problem says truncate toward zero, so I use int(a / b)."

Follow-up questions

How do you evaluate reverse Polish notation?

Scan the tokens, push each number, and on an operator pop b then a, compute a op b and push the result. One value remains at the end. It takes O(n) time because each token is pushed and popped at most once.

Why does the pop order matter when evaluating postfix?

Subtraction and division are not commutative. For 3 134 - the first pop gives 134 as b and the second gives 3 as a, so the result is 3 minus 134, which is -131.¹

How do you tokenize when two patterns match?

Take the longest match, and break a tie with a fixed rule such as "the pattern listed first wins". Candidates report this as the heart of a command-tokenizing problem, where shortcut patterns overlap. The usual fast way to find the longest match is the trie walk described under Step 2.

What if no pattern matches at a position?

There are two choices: emit the single character as a literal token, or raise an error that reports its position. Agree with the interviewer which one is wanted before you code. A calculator can reasonably raise an error, while a command tokenizer may pass leftover characters through as literal text.

Does the shunting yard algorithm reject invalid input?

Not all of it. It rejects mismatched parentheses but accepts 1 2 + as 1 + 2. If the task says the input may be invalid, add a check that every operator finds two operands and the stack ends with one value.

How do you evaluate an expression with no parentheses in one pass?

Track the current number and the last operator. On + or - push the signed number; on * or / combine it with the top of the stack; at the end sum the stack. LeetCode 227 allows exactly this input.

Sources

1. Python documentation: tokenize, tokenizer for Python source — Python Software Foundation, 26 Oct 2026
2. Shunting yard algorithm — Wikipedia (secondary; cites Dijkstra's 1961 report), 26 Oct 2026
3. Maximal munch — Wikipedia (secondary, pointer only), 7 Mar 2025
4. C++ working draft, lex.pptoken: preprocessing tokens — ISO C++ standards committee (working draft), 26 Oct 2026
5. Basic Calculator II (LeetCode 227) — LeetCode, 26 Oct 2026
6. Evaluate Reverse Polish Notation (LeetCode 150) — LeetCode, 26 Oct 2026
7. Basic Calculator (LeetCode 224) — LeetCode, 26 Oct 2026