python solution using stacks.


  • 3
    T

    Using a stack, when encountering '(', save the current tokens and variable states in the stack.

    def evaluate(self, expression):
        st, d, tokens = [], {}, ['']
    
        def getval(x):
            return d.get(x, x)
    
        def evaluate(tokens):
            if tokens[0] in ('add', 'mult'):
                tmp = map(int, map(getval, tokens[1:]))
                return str(tmp[0] + tmp[1] if tokens[0] == 'add' else tmp[0] * tmp[1])
            else: #let
                for i in xrange(1, len(tokens)-1, 2):
                    if tokens[i+1]:
                        d[tokens[i]] = getval(tokens[i+1])
                return getval(tokens[-1])
    
        for c in expression:
            if c == '(':
                if tokens[0] == 'let':
                    evaluate(tokens)
                st.append((tokens, dict(d)))
                tokens =  ['']
            elif c == ' ':
                tokens.append('')
            elif c == ')':
                val = evaluate(tokens)
                tokens, d = st.pop()
                tokens[-1] += val
            else:
                tokens[-1] += c
        return int(tokens[0])
    

  • 0
    L

    Why did you use dict(d) ?


  • 0
    Z

    @livelearn dict(d) is similar to d.copy(). After put d in the stack, d will possibly be overridden by inner scope. Making a copy of d will prevent this. For example: (let x 4 y (let x 5 x) x) The correct result should be 4. However, without dict(d), the result would be 5 due to the inner scope.


Log in to reply
 

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