Parse Lisp Expression


  • 0

    Click here to see the full article post


  • 0
    C

    We can solve the problem with O(N) time and O(N) space by using a recursive approach. Basically, every recursive call will correspond to a new scope of the for '(<expr>)'. We need to precompute the matching parenthesis for a '('. Also, we pass the dictionary storing the variable -> value mapping by reference. Whenever we evaluate a 'let' clause, we need to use an additional dictionary <temp> to remember the initial values of the variables in the current score. Before returning from the current score, we 'clean up' the dictionary using <temp>. Basically, every scope should leave the variable -> value dictionary as it found it.

    This leads to an O(N) time / O(N) memory solution. It's O(N) time since we never go through the same character in an expression more than once. It's O(N) memory since the variable -> value dictionary can't have more than O(N) entries, and the temporary dictionary for a given scope can't have more than O(# of variables in scope). Summing up, the temporary dictionaries are O(N) memory as well.


  • 0

    @catalin7 I think your comment is essentially correct - we can achieve O(N) time complexity when managing the context - but glossed over the details of this "persistent dictionary" which I think are non-trivial.

    Let context = collections.defaultdict(list), the current updated context, and scope = [collections.defaultdict(list)]. Then:

    When we enter an evaluate method, we will append a new collections.defaultdict(list) to scope.

    When we assign (key = val), we will do context[key].append(val) and scope[key].append(val).

    When we want to evaluate a variable key, we will peek at context[key][-1].

    When we exit our evaluate function, we will pop from context all the key value pairs in scope.pop().


  • 0
    C

    @awice Sorry for not explaining it clearer: I don't mean using a persistent dictionary. I mean something of the following form (for the 'let' clause) - expr is expression, dict is the current variable dictionary, old_dict is the temporary dictionary (local to this scope only - aka this function call). l and r are the current bounds. It's not that important to understand this part, the snipped below demonstrates how to use dict and old_dict in order to keep the memory usage O(N):

              unordered_map<string, int> old_dict; // local to the current scope only
              while (true) { // processing 'let' tokens
                    // Before returning from the current scope we call this in order to reset the 'dict'
                    auto clean_up = [&] (const unordered_map<string, int>& old_dict) {
                        for (auto entry : old_dict)
                            dict[entry.first] = entry.second;
                    };
    
                    while (expr[l] == ' ') l++;
                    if (expr[l] >= 'a' && expr[l] <= 'z') {
                        auto variable = parseVariable(expr, l);
    
                        if (!old_dict.count(variable)) { // this means dict[variable] is the initial value of 'variable', before entering the scope
                            old_dict[variable] = dict[variable];
                        }
    
                        while (expr[l] == ' ') l++;
    
                        if (l > r) {
                            auto ret = dict[variable];
                            clean_up(old_dict);
                            // before returning we reset 'dict'
                            return ret;
                        }
    
                        auto new_expr = parseStuff(expr, l, dict); // recursively parses a new expression, 'dict' has up-to-date values from this scope; dict passed by reference
    
                        dict[variable] = new_expr;
                    } else {
                        auto ret = parseStuff(expr, l, dict); // same as above
                        clean_up(old_dict);
                        // before returning we reset 'dict'
                        return ret;
                    }
                }

  • 0

    I think you need a stack of "old_dict"? What about (let x 1 (let x 2 (let x 3 (add x 0)))) ?


  • 0
    C

    @awice Yes, because I'm doing the parsing recursively I implicitly store a stack of old_dict's (rather, C++ does). E.g. if I have K 'let' blocks one in another, I will be storing a stack of K old_dict's. The key part is that every old_dict stores at most O(# of variables in its scope), therefore the combined sum of memory over all K old_dict's is O(M), where M is the total number of variables across all let blocks. Of course, O(M) is actually O(size of expression), so the total memory of my O(K) old_dict's will still be O(N).

    For your example (let x 1 (let x 2 (let x 3 (add x 0)))), I would be storing 3 levels of old_dict's, since there are 3 let expression one in another.

    Every old_dict would be storing x = value from previous scope, meaning exactly one value. Notice that there are 3 x's across all scopes, so in total my 3 old_dict's would store 3 values.
    Notice that value from previous scope is actually just dict[x], for the first time we find x in scope.

    level 0: old_dict_0[x] = 0 (Since x is not in dict at this point, old_dict[x] = 0 - it can be everything really for the level 0 scope), dict[x] = 1
    level 1: old_dict_1[x] = 1 (the value from the level 0 scope), dict[x] = 2
    level 2: old_dict_2[x] = 2 (the value from the level 1 scope), dict[x] = 3

    But the stack of old_dict's is automatically managed by the recursion, so I don't have to worry about it. I only need to worry about the maximum amount of memory required by the old_dict's, and this is O(# of variables) = O(size of expression) as I shown above.

    Fundamentally, old_dict for a scope only stores what changed in that specific scope for dict.


  • 0
    A

    Solution failed at
    "(add (add 1 2) (add (multi 1 5) 4))"


  • 0

    @avlgood-foxmail-com Use "mult" instead of "multi".


  • 0
    D

    Best solution scans expression one time and takes O(N) time complexity. But implementation is more complex.


  • 0
    K

    @awice
    Hi,Thanks for your solution and explanation!
    But I think this line(the 5th line) is redundant:
    scope.add(new HashMap());


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.