Remove parentheses from a plus/minus expression

Question: Remove parentheses from a plus/minus expression

Companies: Google, Meta

Difficulty: Hard

Problem statement

Write a function simplify(expr: str) -> str that removes every parenthesis from an expression and gives each term the sign it really has.

Input. A valid expression made of:

• operands: variable names (letters, digits and _, starting with a letter, such as a or x1) and non-negative integers
• the binary operators + and -
• unary minus at the start of the expression or right after (
• parentheses, nested to any depth
• spaces, which you should ignore

There is no multiplication or division.

Output. An equivalent expression with no parentheses and no spaces:

• Keep the terms in the order they appear in the input.
• Each term has the sign it gets once all enclosing groups are expanded.
• Drop a leading +, but keep a leading -.
• Do not combine like terms: x-(x) becomes x-x.
• If the expression has no operands, return "0".

Constraints. 1 <= len(expr) <= 10^5. Nesting depth can be close to len(expr), so avoid deep recursion. Aim for O(n) time.

Example 1

simplify("m-(n-(p+q))")  ->  "m-n+p+q"

p and q are inside two groups that each have a - in front. The two minus signs cancel.

Example 2

simplify("-(u - 4) + (-(v))")  ->  "-u+4-v"

Part 2 (follow-up). Write simplify_combined(expr), which also combines like terms and sums the integers into one constant at the end. For example, "k-(j-k)+5-2" becomes "2k-j+3".

Approach

Clarify first. The input is a valid expression made of operands (variable names like a or x1, and non-negative integers), +, -, parentheses and spaces. There is no multiplication. The task is to remove every parenthesis and give each term the sign it really has. Settle these points before coding:

• Term order. Keep terms in the order they appear. a-(b+c) becomes a-b-c, not a-c-b.
• Leading sign. Drop a leading +, keep a leading -. -(a-b) becomes -a+b.
• Unary minus. A - can start the expression or follow (, as in (-a+b). It can also follow another operator (a--b) if the interviewer allows it. Treat a run of signs as one sign: count the minuses.
• Combining like terms. The base task does not combine a-a into 0. Ask. It is the usual Part 2 (see Follow-ups).

Key idea. The sign a term really has is the product of its own sign and the signs in front of every ( that encloses it. a-(b-(c+d)) has d inside two groups, each with a - in front, so d gets (-1)(-1)(+1) = +1.

Brute force. Repeatedly find an innermost (...) group, flip the signs inside it if a - stands in front, and splice it back without the parentheses. Each pass is O(n) and there can be O(n) nesting levels, so this is O(n^2). It also needs care with +- and -- after each splice. It is a fine thing to describe; do not code it.

Optimal: a stack of group signs, one pass.

1. Keep stack, where stack[-1] is the sign (+1 or -1) that applies to everything in the current group. Start with [+1] for the whole expression.
2. Keep pending, the sign written just before the next operand or group. Reset it to +1 after each operand and after each (. On -, flip it. On +, leave it.
3. On (, push stack[-1] * pending and reset pending.
4. On ), pop.
5. On an operand, its real sign is stack[-1] * pending. Emit +name or -name, then reset pending.

At the end, strip a leading +. If there were no operands at all (for example ()), return "0".

Invariant. When an operand is read, stack[-1] equals the product of the signs in front of every open group around it. A ) pops exactly the sign that its ( pushed, so the invariant holds after it. Each character is handled once, so the pass is linear.

Code

from __future__ import annotations


def _tokens(expr: str) -> list[str]:
    """Split into operands, '+', '-', '(' and ')'. Raises on bad characters."""
    out: list[str] = []
    i, n = 0, len(expr)
    while i < n:
        ch = expr[i]
        if ch.isspace():
            i += 1
        elif ch in "+-()":
            out.append(ch)
            i += 1
        elif ch.isalnum() or ch == "_":
            j = i
            while j < n and (expr[j].isalnum() or expr[j] == "_"):
                j += 1
            out.append(expr[i:j])
            i = j
        else:
            raise ValueError(f"unexpected character {ch!r} at {i}")
    return out


def _signed_terms(expr: str) -> list[tuple[int, str]]:
    """Return (sign, operand) for each operand, in order, with parentheses resolved."""
    stack = [1]      # sign applied to the current group
    pending = 1      # sign written just before the next operand or group
    terms: list[tuple[int, str]] = []
    for tok in _tokens(expr):
        if tok == "+":
            continue
        if tok == "-":
            pending = -pending
        elif tok == "(":
            stack.append(stack[-1] * pending)
            pending = 1
        elif tok == ")":
            if len(stack) == 1:
                raise ValueError("unbalanced ')'")
            stack.pop()
        else:
            terms.append((stack[-1] * pending, tok))
            pending = 1
    if len(stack) != 1:
        raise ValueError("unbalanced '('")
    return terms


def simplify(expr: str) -> str:
    """Remove all parentheses, keeping term order: 'a-(b-c)' -> 'a-b+c'."""
    terms = _signed_terms(expr)
    if not terms:
        return "0"
    s = "".join(("+" if sign > 0 else "-") + name for sign, name in terms)
    return s[1:] if s[0] == "+" else s


def simplify_combined(expr: str) -> str:
    """Follow-up: also combine like terms. 'a-(b-a)+3-1' -> '2a-b+2'."""
    coeff: dict[str, int] = {}   # insertion order = first appearance
    constant = 0
    for sign, name in _signed_terms(expr):
        if name.isdigit():
            constant += sign * int(name)
        else:
            coeff[name] = coeff.get(name, 0) + sign
    parts: list[str] = []
    for name, c in coeff.items():
        if c == 0:
            continue
        mag = "" if abs(c) == 1 else str(abs(c))
        parts.append(("+" if c > 0 else "-") + mag + name)
    if constant:
        parts.append(("+" if constant > 0 else "-") + str(abs(constant)))
    if not parts:
        return "0"
    s = "".join(parts)
    return s[1:] if s[0] == "+" else s


if __name__ == "__main__":
    assert simplify("a-(b+c)") == "a-b-c"
    assert simplify("a-(b-(c+d))") == "a-b+c+d"
    assert simplify("-(a-b)") == "-a+b"
    assert simplify(" ( x1 + ( - y ) ) ") == "x1-y"
    assert simplify("a--b") == "a+b"
    assert simplify("((a))") == "a"
    assert simplify("()") == "0"
    assert simplify("p-(q-(r-(s-t)))") == "p-q+r-s+t"
    assert simplify("a-(3-b)") == "a-3+b"
    assert simplify_combined("a-(b-a)+3-1") == "2a-b+2"
    assert simplify_combined("x-(x)") == "0"
    assert simplify_combined("-(a+a+a)+b") == "-3a+b"
    for bad in ["(a", "a)", "a*b"]:
        try:
            simplify(bad)
            raise AssertionError(bad)
        except ValueError:
            pass
    print("ok")

Complexity

• simplify: O(n) time for an expression of length n. Each character is tokenized once and each token is handled once. Space is O(n) for the tokens and the output, plus O(d) for the stack, where d is the nesting depth.
• simplify_combined: O(n) time (expected, for the hash map) and O(n) space. The map holds at most one entry per distinct variable.

Test cases

• "a-(b+c)" -> "a-b-c"
• "a-(b-(c+d))" -> "a-b+c+d" (two minus groups cancel for c and d)
• "-(a-b)" -> "-a+b" (leading - kept)
• " ( x1 + ( - y ) ) " -> "x1-y" (spaces, multi-character names, unary minus after ()
• "a--b" -> "a+b" (a run of signs)
• "((a))" -> "a" (redundant nesting)
• "p-(q-(r-(s-t)))" -> "p-q+r-s+t" (alternating deep nesting)
• "a-(3-b)" -> "a-3+b" (integer operands)
• "()" -> "0" (no operands)
• "(a", "a)", "a*b" -> ValueError
• Combined: "a-(b-a)+3-1" -> "2a-b+2"; "x-(x)" -> "0"; "-(a+a+a)+b" -> "-3a+b"

Follow-ups

1. Combine like terms. Use the same sign pass, but add each sign into a map from variable to coefficient instead of emitting it. Sum integer operands into one constant. Print in order of first appearance, skip zero coefficients, and print a rather than 1a. Shown as simplify_combined. Ask whether output should be sorted by variable name instead.
2. Integer coefficients and scalar multiplication, such as 2a - 3(b - 2c). The stack now holds an integer multiplier, not just a sign. On (, push stack[-1] * pending * k, where k is the number written just before the (. An operand's coefficient is stack[-1] * pending * its own number. Still one pass, O(n).
3. Keep the expression but drop only redundant parentheses. Now the output keeps some parentheses: a-(b+c) stays as is, but a+(b+c) becomes a+b+c. A group is redundant if a + (or nothing) stands in front of it, or if it holds a single operand. Build a small parse tree, then print it, adding parentheses only where the parent operator is - and the child is a sum or difference. Adding * and / brings in precedence rules: a child needs parentheses when its operator binds more loosely than the parent's, and also on the right of - or / when the precedence is equal.
4. Products of variables ((a+b)(a-b)). This is LeetCode 770 territory. Represent each sub-expression as a polynomial: a map from a sorted tuple of variables to an integer coefficient. Use two stacks (operands and operators) or recursive descent. Multiplying two polynomials is the product of their term counts, so state that output size can grow exponentially with nesting.
5. Very long or deeply nested input. The iterative stack already avoids recursion limits. For streaming input, emit each term as it is read; only the stack of depth d must be kept in memory.

Interviewer expectations

Mid-level (L4)

• Gets the sign rule right, including nested minus groups and a leading -.
• Writes the stack-of-signs pass or a clean recursive version, with no O(n^2) string splicing.
• Tests nested, leading-minus and unary-minus cases without being prompted.

Senior (L5)

• Asks about term order, combining like terms, unary minus and invalid input before coding.
• States the invariant (top of stack = product of enclosing signs) and why ) restores it.
• Moves to combining like terms (Part 2) and to integer coefficients by changing only what the stack holds, not by rewriting the solution.

Staff (L6+)

• Separates tokenizing, sign resolution and output formatting, so each follow-up changes one layer.
• Explains when a parse tree is needed (keeping minimal parentheses, precedence with * and /, polynomial products) and its cost compared to the flat sign pass.
• Covers validation and error reporting, streaming or very deep input, and how the output size grows for polynomial products.