0540HardMathStringStackRecursion

Till Keypad Expression

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 market-stall till lets the trader type a whole price calculation on the keypad before pressing total. The keystrokes arrive as the string s, which contains decimal digits, the four operator keys +, -, * and /, and the bracket keys ( and ). There are no spaces, every operator sits between two operands, and no number is preceded by a sign.

Work out what the till should display, following these rules:

* and / bind more tightly than + and -.
Operators that bind equally tightly are applied from left to right, so 60/4/5 is 3.
A bracketed section is worked out first and then used as a single operand.
/ is whole-number division that throws away any fractional part, rounding toward zero. So (0-9)/4 is -2, not -3.
No division by zero occurs.

Return the displayed value. Do not pass the string to a built-in expression evaluator.

Examples

Example 1

Input: s = "9+40/6*2"
Output: 21

The tighter operators go first: 40/6 discards the remainder and gives 6, then 6*2 is 12, and finally 9+12 is 21.

Example 2

Input: s = "(70-90)/6"
Output: -3

The bracket gives -20, and dividing -20 by 6 rounds the quotient toward zero, so the till shows -3.

Example 3

Input: s = "4*(8+2*(9-6))-50/4"
Output: 44

The inner bracket is 9-6 = 3, so 2*3 = 6 and the outer bracket is 8+6 = 14. Then 4*14 = 56, and 50/4 = 12, leaving 56-12 = 44.

Constraints

1 <= s.length <= 10^4
s contains only the characters '0'-'9', '+', '-', '*', '/', '(' and ')'.
s is a well-formed expression in which every operator is binary.
The final value and every value reached along the way lie between -2^31 and 2^31 - 1.

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 calculate(s: str) -> int:

Java

public int calculate(String s)

The intended approach

Time O(n) in the length of s; each character is pushed and folded at most once.Space O(n) for the two stacks, which is the depth reached by fully bracketed input.

Walk the string once, pushing each complete number onto a value stack and each operator onto an operator stack. Before pushing an operator, fold every operator already waiting whose binding strength is at least as great, which both enforces that `*` and `/` beat `+` and `-` and makes equally binding operators fold left to right. An opening bracket is pushed as a barrier that folding will not cross; a closing bracket folds back down to that barrier and removes it. Folding pops the right operand first, and division computes the quotient of the magnitudes and then re-applies the sign, which rounds toward zero. Both stacks are ordinary lists, so deeply bracketed input costs memory rather than call depth.

Pythonentry point: calculate

def calculate(s):
    # O(n) time, one left-to-right pass over the characters with a value stack
    # and an operator stack. A waiting operator is folded as soon as an operator
    # of the same or weaker binding strength arrives, which is what makes two
    # equally binding operators fold left to right. Both stacks are real lists
    # rather than a recursive call chain, so 10^4 nested brackets are fine.
    strength = {"+": 1, "-": 1, "*": 2, "/": 2}
    vals = []
    ops = []

    def fold():
        op = ops.pop()
        b = vals.pop()
        a = vals.pop()
        if op == "+":
            vals.append(a + b)
        elif op == "-":
            vals.append(a - b)
        elif op == "*":
            vals.append(a * b)
        else:
            q = abs(a) // abs(b)
            if (a < 0) != (b < 0):
                q = -q
            vals.append(q)

    i = 0
    n = len(s)
    while i < n:
        ch = s[i]
        if "0" <= ch <= "9":
            num = 0
            while i < n and "0" <= s[i] <= "9":
                num = num * 10 + (ord(s[i]) - 48)
                i += 1
            vals.append(num)
            continue
        if ch == "(":
            ops.append(ch)
        elif ch == ")":
            while ops[-1] != "(":
                fold()
            ops.pop()
        else:
            while ops and ops[-1] != "(" and strength[ops[-1]] >= strength[ch]:
                fold()
            ops.append(ch)
        i += 1
    while ops:
        fold()
    return vals[0]

The obvious version

A hand-written descent over the grammar with a shared cursor: a whole expression is a run of chunks joined by `+` and `-`, a chunk is a run of atoms joined by `*` and `/`, and an atom is either a run of digits or a bracketed whole expression. Each level consumes its operands strictly left to right, so association falls out of the loop order.

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 bf_calculate(s):
    at = [0]
    n = len(s)

    def atom():
        if s[at[0]] == "(":
            at[0] += 1
            v = whole()
            at[0] += 1
            return v
        start = at[0]
        while at[0] < n and "0" <= s[at[0]] <= "9":
            at[0] += 1
        return int(s[start:at[0]])

    def chunk():
        v = atom()
        while at[0] < n and s[at[0]] in "*/":
            op = s[at[0]]
            at[0] += 1
            w = atom()
            if op == "*":
                v = v * w
            else:
                q = abs(v) // abs(w)
                if (v < 0) != (w < 0):
                    q = -q
                v = q
        return v

    def whole():
        v = chunk()
        while at[0] < n and s[at[0]] in "+-":
            op = s[at[0]]
            at[0] += 1
            w = chunk()
            if op == "+":
                v = v + w
            else:
                v = v - w
        return v

    return whole()

How this problem was checked

Reference solution executed against 15 test cases — 15 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