Problem statement

https://leetcode.com/problems/parse-lisp-expression/

Solution

Quite painful problem, where we first need to understand how scope works here. Let us use auxiliary function evl, which will deal with list of tokens: variables and numbers and which start with one of the 3 options: sum, mult or let. If we have sum or mult, we check for each token if it is string or number: if it is string, that is variable, we return corresponding value. If it is integer, we just return it. This can be done easily, using trick d.get(x, x). Now, if we have let, then we iterate over pairs of our tokens and put updated values into dictionary.

Now, we iterate over our expression and if we have:

  1. Open bracket (, then we first need to process our tokens if they start with let: it can happen, for example in (let x 2 (mult x 5)): when we go to the second open bracket we need to update the dictionary before entering the deeper layer. Then we add our tokens and dictionary into stack and make our tokens empty.
  2. If we have closing bracket ), then we need again to process our tokens, extract last tokens and dictionary for stack and update the outside layer.
  3. If we have space symbol, it means we need to start new token
  4. In any other case, it means, that we continue to build our last token.

Complexity

Both time and space I think O(n) (I am not 100 percent sure).

Code

class Solution:
    def evaluate(self, expression):
        tokens, stack, d = [''], [], {}
        def getval(x): return d.get(x, x)
        
        def process(tokens):  
            if tokens[0] in ['add', 'mult']:
                a, b = int(getval(tokens[1])), int(getval(tokens[2]))
                return str(a + b) if tokens[0] == 'add' else str(a * b)
            else:
                for i in range(1, len(tokens)//2): 
                    d[tokens[2*i-1]] = getval(tokens[2*i])
                return getval(tokens[-1]) 
            
        for c in expression:
            if c == '(':
                if tokens[0] == 'let': process(tokens)
                stack.append((tokens, dict(d)))
                tokens = ['']
            elif c == ')':
                val = process(tokens)
                tokens, d = stack.pop()
                tokens[-1] += val
            elif c == ' ': tokens.append('')
            else: tokens[-1] += c
        return int(tokens[0])