Show problems as
Classic problem #736HardHash TableStringStackRecursion

Parse Lisp Expression

Real-world version: Evaluate the Batch Recipe Macro
Tracked in this browser only
Read Parse Lisp Expression on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def evaluate_recipe(program: str) -> int:
Java
public int evaluateRecipe(String program)

More on the same topics