Evaluate Expressions with Strictly Positive Integer Intermediate Results

Quick Overview

Evaluate arithmetic expressions with a supplied decomposition helper, rejecting nonpositive or fractional intermediate results and preserving exact integer division.

Evaluate Expressions with Strictly Positive Integer Intermediate Results

Company: Jane Street

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Evaluate a string arithmetic expression whose literals are positive integers and whose binary operators are `+`, `-`, `*`, and `/`. Return its integer value if every evaluated subexpression has a strictly positive integer result. If any literal, operand, or intermediate result fails that rule, return Boolean `false` for the whole expression; later operations cannot make that subexpression valid. ### Supplied Decomposition Helper Assume a helper `split(s)` is provided for expressions in this task. It decomposes an expression at its outermost operation and returns either a one-element tuple containing a literal expression or a three-element tuple `(left_expression, operator, right_expression)`. The returned operand expressions may themselves need evaluation. ```text split("3 / 5") -> ("3", "/", "5") split("5") -> ("5",) split("(10 / 2) / 5") -> ("(10 / 2)", "/", "5") ``` The helper determines the decomposition of a valid input expression. This task does not ask you to implement a parser. The source does not specify the helper's behavior for malformed expressions or every unparenthesized operator combination. ### Arithmetic and Output Rules - A literal must be a positive integer after permitted surrounding whitespace and enclosing parentheses are removed. Zero is invalid. - Addition and multiplication use exact integer arithmetic. Subtraction is invalid if its result is zero or negative. - Division is invalid if the divisor is zero or if the dividend is not exactly divisible by the divisor. Do not round or truncate a fractional quotient. - Return the final positive integer, or Boolean `false` when any subexpression is invalid. ### Examples ```text expression = "(3 + (3 * 5)) / 2" result = 9 expression = "((3 - 5) + 12) / 2" result = false expression = "8 / 12" result = false expression = "3 - 3" result = false ``` In the second example, the subtraction yields a negative intermediate result. In the third, division is not exact. The fourth is invalid because this task requires strictly positive results; zero from subtraction is invalid too.

Overview: Evaluate arithmetic expressions with a supplied decomposition helper, rejecting nonpositive or fractional intermediate results and preserving exact integer division.

Read the full Jane Street Software Engineer interview experience this question came from

Community answers

Answer by farkastiberia15

The problem is best solved using a recursive Depth-First Search (DFS) approach, treating the expression as an implicit Abstract Syntax Tree (AST). Since the provided split(s) helper perfectly decomposes the string at the outermost operator, it handles the parsing logic, allowing the algorithm to focus strictly on evaluation and constraint checking. Base Case (Literal Evaluation): When split(s) returns a 1-tuple, the string is a literal (which may be wrapped in whitespace or parentheses). Recursively strip leading/trailing whitespace and outermost matching parentheses. Parse the cleaned string to an integer. If the parsed integer is $\le 0$, return false. Otherwise, return the integer. Recursive Step (Operator Evaluation): When split(s) returns (left, operator, right), recursively evaluate the left and right subexpressions. Short-Circuiting: If either the left or right recursive call returns false, immediately return false up the call stack. There is no need to evaluate the other side if the first side fails. Strict Arithmetic Application: Addition (+): Return left + right. Multiplication (): Return left right. Subtraction (-): If left - right <= 0, return false. Else, return left - right. Division (/): If left % right != 0, return false. (A divide-by-zero check is technically covered since intermediate results must be strictly positive, meaning right will never be 0, but it is best practice to include it). Else, return left / right. Time Complexity: In the best/average case (
Jane Street logo
Jane Street
Aug 22, 2026
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
108
0

Evaluate a string arithmetic expression whose literals are positive integers and whose binary operators are +, -, *, and /. Return its integer value if every evaluated subexpression has a strictly positive integer result. If any literal, operand, or intermediate result fails that rule, return Boolean false for the whole expression; later operations cannot make that subexpression valid.

Supplied Decomposition Helper

Assume a helper split(s) is provided for expressions in this task. It decomposes an expression at its outermost operation and returns either a one-element tuple containing a literal expression or a three-element tuple (left_expression, operator, right_expression). The returned operand expressions may themselves need evaluation.

split("3 / 5")       -> ("3", "/", "5")
split("5")           -> ("5",)
split("(10 / 2) / 5") -> ("(10 / 2)", "/", "5")

The helper determines the decomposition of a valid input expression. This task does not ask you to implement a parser. The source does not specify the helper's behavior for malformed expressions or every unparenthesized operator combination.

Arithmetic and Output Rules

  • A literal must be a positive integer after permitted surrounding whitespace and enclosing parentheses are removed. Zero is invalid.
  • Addition and multiplication use exact integer arithmetic. Subtraction is invalid if its result is zero or negative.
  • Division is invalid if the divisor is zero or if the dividend is not exactly divisible by the divisor. Do not round or truncate a fractional quotient.
  • Return the final positive integer, or Boolean false when any subexpression is invalid.

Examples

expression = "(3 + (3 * 5)) / 2"
result = 9

expression = "((3 - 5) + 12) / 2"
result = false

expression = "8 / 12"
result = false

expression = "3 - 3"
result = false

In the second example, the subtraction yields a negative intermediate result. In the third, division is not exact. The fourth is invalid because this task requires strictly positive results; zero from subtraction is invalid too.