0802HardHash TableStringStackRecursion

Evaluate the Batch Recipe Macro

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 plant writes the quantities on its batch sheets in a tiny macro language, and the loader has to reduce each sheet to a single whole number.

A term is one of the following, and nothing else.

An integer literal: an optional - followed by one or more digits, such as 12 or -40. Its value is that integer.
A label: a lowercase letter followed by any number of lowercase letters and digits, such as v or x2 or feedrate. The three words plus, times and with are reserved and are never used as labels. A label's value is the value currently in force for it.
(plus A B), whose value is the value of term A added to the value of term B.
(times A B), whose value is the value of term A multiplied by the value of term B.
(with L1 A1 L2 A2 ... Ln An B), which puts labels into force. After with come one or more pairs, each a label followed by the term giving its value, and then one final term B. The value of the whole with is the value of B.

The rules for a with are these.

The pairs take effect from left to right. Term A1 is reduced before L1 is in force, term A2 is reduced with L1 already in force, term A3 with L1 and L2 in force, and so on. Term B is reduced with all n labels in force.
The same label may appear in more than one pair of a single with. The later pair takes over from the point it appears onward.
A label put into force by a with hides whatever value that label carried outside the with, and only until that with is finished. Once the with is done, the hidden outer value is back in force.

program holds one term. Tokens are separated by single spaces, there is no space just inside a bracket, and there is no leading or trailing space. Every label used as a term has a value in force at the point it is used. Parse the text yourself; do not hand it to a language evaluator such as eval.

Return the value of program.

Examples

Example 1

Input: program = "(with base 5 span (with base 9 (times base 2)) (plus base span))"
Output: 23

The inner `with` puts `base` at 9 only inside itself, so its body `(times base 2)` is 18 and `span` becomes 18. The inner `with` is then finished, so `base` is back at 5 and the body `(plus base span)` is 5 + 18.

Example 2

Input: program = "(with a 3 b (plus a 4) (times a b))"
Output: 21

The pair for `b` is reduced with `a` already at 3, so `b` becomes 3 + 4 = 7, and the body `(times a b)` is 3 * 7.

Example 3

Input: program = "(with x2 7 (plus x2 x2))"
Output: 14

`x2` is a legal label: it starts with a letter and then carries a digit. It is put at 7, so the body `(plus x2 x2)` is 7 + 7.

Constraints

1 <= program.length <= 2000
Tokens in program are separated by single spaces, and program has no leading or trailing space.
program is a legal term and its value is an integer.
The value of program and of every term reduced along the way fits in a signed 32-bit integer.
Every label starts with a lowercase letter and continues with lowercase letters and digits; plus, times and with are never used as labels.

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_recipe(program: str) -> int:

Java

public int evaluateRecipe(String program)

The intended approach

Time O(L) for a program of L characters: one character pass to build the nested tokens, then one job per token, each doing constant work.Space O(L) for the nested token structure, the job stack, the value stack and the per-label value stacks.

Two iterative passes. The first walks the characters once and, with a stack of open brackets, turns the text into nested lists of tokens. The second reduces that structure with a stack of pending jobs instead of recursion: reducing `plus` or `times` queues its two terms and then a fold, and reducing a `with` queues, in order, each pair's term followed by a job that puts that label into force, then the body term, then one job that takes all of the `with`'s labels back out of force. A label maps to a stack of values, so putting a label into force pushes and finishing the `with` pops, which is exactly the hide-then-restore rule; the fixed job order is what makes each pair see the pairs before it.

Pythonentry point: evaluate_recipe

def evaluate_recipe(program):
    # tokenise into nested lists with a stack, so the reader never recurses
    root = []
    frames = [root]
    token = []
    for ch in program:
        if ch == "(":
            if token:
                frames[-1].append("".join(token))
                token = []
            inner = []
            frames[-1].append(inner)
            frames.append(inner)
        elif ch == ")":
            if token:
                frames[-1].append("".join(token))
                token = []
            frames.pop()
        elif ch == " ":
            if token:
                frames[-1].append("".join(token))
                token = []
        else:
            token.append(ch)
    if token:
        frames[-1].append("".join(token))
    tree = root[0]

    # a stack of pending jobs stands in for the recursion: "e" reduces a term,
    # "o" folds the two values that term left behind, "b" puts one label into
    # force, "u" takes a with's labels back out of force
    scope = {}
    jobs = [("e", tree)]
    values = []
    while jobs:
        kind, load = jobs.pop()
        if kind == "e":
            if isinstance(load, str):
                if load[0] == "-" or load[0].isdigit():
                    values.append(int(load))
                else:
                    values.append(scope[load][-1])
                continue
            word = load[0]
            if word == "with":
                pairs = (len(load) - 2) // 2
                jobs.append(("u", [load[2 * j + 1] for j in range(pairs)]))
                jobs.append(("e", load[-1]))
                for j in range(pairs - 1, -1, -1):
                    jobs.append(("b", load[2 * j + 1]))
                    jobs.append(("e", load[2 * j + 2]))
            else:
                jobs.append(("o", word))
                jobs.append(("e", load[2]))
                jobs.append(("e", load[1]))
        elif kind == "o":
            right = values.pop()
            left = values.pop()
            values.append(left + right if load == "plus" else left * right)
        elif kind == "b":
            scope.setdefault(load, []).append(values.pop())
        else:
            for label in load:
                scope[label].pop()
    return values.pop()

The obvious version

Straight recursive descent over the raw text, with no pre-parse: split the inside of a bracket into its top-level pieces by counting bracket depth, then reduce each piece by calling back into the same routine. Scoping is handled by copying the whole label dictionary on entry to a `with`, so the caller's dictionary is never touched and the outer values need no restoring.

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_evaluate_recipe(program):
    def pieces(text):
        out = []
        depth = 0
        cur = []
        for ch in text:
            if ch == "(":
                depth += 1
            elif ch == ")":
                depth -= 1
            if ch == " " and depth == 0:
                out.append("".join(cur))
                cur = []
            else:
                cur.append(ch)
        if cur:
            out.append("".join(cur))
        return out

    def go(text, scope):
        if text[0] != "(":
            if text[0] == "-" or text[0].isdigit():
                return int(text)
            return scope[text]
        part = pieces(text[1:-1])
        if part[0] == "plus":
            return go(part[1], scope) + go(part[2], scope)
        if part[0] == "times":
            return go(part[1], scope) * go(part[2], scope)
        inner = dict(scope)
        i = 1
        while i + 2 < len(part):
            inner[part[i]] = go(part[i + 1], inner)
            i += 2
        return go(part[i], inner)

    return go(program, {})

How this problem was checked

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