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.


Log in to reply
 

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