# Posts published in “Recursion”

Problem:

You are given a stringĀ expressionĀ representing a Lisp-like expression to return the integer value of.

The syntax for these expressions is given as follows.

• An expression is either an integer, a let-expression, an add-expression, a mult-expression, or an assigned variable. Expressions always evaluate to a single integer.
• (An integer could be positive or negative.)
• A let-expression takes the formĀ (let v1 e1 v2 e2 ... vn en expr), whereĀ letĀ is always the stringĀ "let", then there are 1 or more pairs of alternating variables and expressions, meaning that the first variableĀ v1is assigned the value of the expressionĀ e1, the second variableĀ v2Ā is assigned the value of the expressionĀ e2, and so onĀ sequentially; and then the value of this let-expression is the value of the expressionĀ expr.
• An add-expression takes the formĀ (add e1 e2)Ā whereĀ addĀ is always the stringĀ "add", there are always two expressionsĀ e1, e2, and this expression evaluates to the addition of the evaluation ofĀ e1Ā and the evaluation ofĀ e2.
• A mult-expression takes the formĀ (mult e1 e2)Ā whereĀ multĀ is always the stringĀ "mult", there are always two expressionsĀ e1, e2, and this expression evaluates to the multiplication of the evaluation ofĀ e1Ā and the evaluation ofĀ e2.
• For the purposes of this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally for your convenience, the names “add”, “let”, or “mult” are protected and will never be used as variable names.
• Finally, there is the concept of scope. When an expression of a variable name is evaluated,Ā within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on scope.

Evaluation Examples:

Note:

• The given stringĀ expressionĀ is well formatted: There are no leading or trailing spaces, there is only a single space separating different components of the string, and no space between adjacent parentheses. The expression is guaranteed to be legal and evaluate to an integer.
• The length ofĀ expressionĀ is at most 2000. (It is also non-empty, as that would not be a legal expression.)
• The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer.

Idea:

Recursive parsing

Time complexity: O(n^2) in worst case O(n) in practice

Space complexity: O(n)

Problem:

Given a chemicalĀ formulaĀ (given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Example 1:

Example 2:

Example 3:

Note:

• All atom names consist of lowercase letters, except for the first character which is uppercase.
• The length ofĀ formulaĀ will be in the rangeĀ [1, 1000].
• formulaĀ will only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.

Idea:

Recursion

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++

Java