Katkat
Back

Payout-Split Formula Where Every Step Is a Whole Positive Share

Jane StreetSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Write a parser and evaluator for arithmetic formulas that describe splitting a prize pool into whole-unit shares, where every intermediate computed amount must be a positive whole number or the entire formula is rejected. Tests recursive-descent parsing combined with evaluation rules where a single bad step invalidates the whole result.

A tournament organizer writes payout-splitting formulas as plain arithmetic strings: positive integer literals combined with +, -, *, /, and parentheses, using ordinary precedence (* and / bind tighter than + and -; operators of equal precedence apply left to right). A formula models dividing pools of currency or work units into whole shares, so every value produced while evaluating it — including every intermediate result, not just the final one — must be a positive whole number. If any step produces zero, a negative number, or a non-whole number, the entire formula is invalid, regardless of what later operations might otherwise have produced from it.

Write:

def evaluate_share_formula(expression: str) -> int | bool:
    ...

Return the final integer value if the formula and every one of its intermediate steps are valid. Return the Python value False if any step is invalid.

Rules

  • A literal is one or more digits representing a positive integer; 0 on its own is invalid.
  • A subtraction step fails as soon as the left side no longer exceeds the right side, since that yields zero or a negative number.
  • A division step fails when dividing by zero, and it also fails whenever the two numbers don't divide evenly — fractional quotients are rejected outright rather than rounded or cut off.
  • Addition and multiplication of two valid positive integers are always valid.
  • Whitespace may appear anywhere between tokens and should be ignored.

Examples

evaluate_share_formula("((9 * 4) / 6) + 10")
# 9*4=36, 36/6=6 (exact), 6+10=16 -> 16

evaluate_share_formula("(20 - 6) / 2")
# 20-6=14, 14/2=7 -> 7

evaluate_share_formula("(5 - 9) + 100")
# 5-9=-4, already invalid -> False

evaluate_share_formula("15 / 4")
# 15 does not divide evenly by 4 -> False

In the third example, -4 + 100 would equal 96, but that never matters: the subtraction step alone already breaks the rule, so the whole formula is False.

Constraints

  • The input is always syntactically well-formed: digits, + - * /, matched parentheses, and optional spaces, with no unary minus and no leading zeros in a literal.
  • Expression length is at most 500 characters, with nesting depth at most 50.
  • You must implement your own parsing; do not assume a decomposition helper is provided.

Hints

Hint 1

Write the tokenizer first and keep it dumb — numbers, operators, and parentheses, nothing smart. Let the parser carry all the logic.

Hint 2

Standard two-level recursive descent (an expression made of terms, a term made of factors) naturally gives you the right precedence for free.

Hint 3

Check the positive-whole-number rule immediately after computing each intermediate value, not at the end — that's what makes a bad step propagate upward through every parent call.

Hint 4

Using a sentinel exception (or returning a special marker) for 'invalid' and catching it once at the top level is cleaner than threading a boolean through every recursive return.

Follow-up questions

  • How would you extend the grammar to support unary minus on a literal, given that the whole scheme currently assumes all literals are positive?
  • If the formula could be several megabytes long, how would you avoid Python's recursion limit while keeping the same precedence rules?
  • How would you modify the evaluator to report *which* subexpression first became invalid, instead of only a boolean?
  • Suppose exact equality to zero should be allowed (representing a forfeited share) but negative values should not — how much of the implementation would need to change?