0174HardMathStringStackRecursion

Bracketed Offset Total

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A surveyor's notebook records how much a benchmark has moved as one long offset line, for example 40-(6+9). The line is a string expr built only from digits, +, -, round brackets and spaces.

Reading rules for the line:

+ and - between two pieces add and subtract, applied left to right.
A bracketed group is read on its own, and whatever sits in front of the group applies to its whole value.
- may also appear as a sign in front of a single number or a bracketed group, as in -7 or -(4+2). + is never used that way.
Spaces carry no meaning.

Return the total offset the line describes. Passing the line to a language-provided expression evaluator is not allowed.

Examples

Example 1

Input: expr = "7 - (2 + 9)"
Output: -4

The bracketed group is worth 11, and the minus in front of it applies to all of it, so the line reads 7 - 11.

Example 2

Input: expr = "-(6-11)+4"
Output: 9

The group is worth -5, the leading sign flips it to 5, and the trailing 4 brings the total to 9.

Example 3

Input: expr = "((3+12)-(5-1))-8"
Output: 3

The inner groups are 15 and 4, so the outer group is 11, and subtracting 8 leaves 3.

Constraints

1 <= expr.length <= 3 * 10^5
expr holds only digits, '+', '-', '(', ')' and ' '
expr is always a well-formed offset line
'+' never appears as a sign in front of a number or a group
'-' may appear as a sign in front of a number or a group
Two operators never sit next to each other
Every number and every running total fits in a signed 32-bit integer

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def evaluate_offsets(expr: str) -> int:

Java

public int evaluateOffsets(String expr)

The intended approach

Time O(n)Space O(n)

Carry a running total, the sign that applies to the number being read, and the number itself. On `(` park the running total and the pending sign on a stack and start a fresh total for the group; on `)` close the group, multiply it by the parked sign and add the parked total back. Because the parked sign already covers the whole group, no group ever has to be re-read, and one pass over the characters is enough.

Pythonentry point: evaluate_offsets

def evaluate_offsets(expr):
    # Every character is touched once, so time is O(n). The stack keeps two
    # entries per open bracket, which is O(n) space when brackets nest deeply.
    total = 0
    sign = 1
    number = 0
    parked = []
    for char in expr:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char == '+':
            total += sign * number
            number = 0
            sign = 1
        elif char == '-':
            total += sign * number
            number = 0
            sign = -1
        elif char == '(':
            parked.append(total)
            parked.append(sign)
            total = 0
            sign = 1
        elif char == ')':
            total += sign * number
            number = 0
            total *= parked.pop()
            total += parked.pop()
            sign = 1
    return total + sign * number

The obvious version

Repeatedly locate the innermost bracketed group, replace it with its own value as a signed number, and stop when no brackets remain. A helper sums a bracket-free line, folding any run of signs into one.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def _flat_total(text):
    total = 0
    index = 0
    size = len(text)
    while index < size:
        sign = 1
        while index < size and text[index] in '+-':
            if text[index] == '-':
                sign = -sign
            index += 1
        value = 0
        seen = False
        while index < size and text[index].isdigit():
            value = value * 10 + int(text[index])
            index += 1
            seen = True
        if not seen and index < size:
            index += 1
        total += sign * value
    return total


def bf_evaluate_offsets(expr):
    text = expr.replace(' ', '')
    while '(' in text:
        close = text.index(')')
        opens = text.rindex('(', 0, close)
        inner = _flat_total(text[opens + 1:close])
        marker = '+' if inner >= 0 else '-'
        text = text[:opens] + marker + str(abs(inner)) + text[close + 1:]
    return _flat_total(text)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in