python solution using stacks.

  • 3

    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':
                st.append((tokens, dict(d)))
                tokens =  ['']
            elif c == ' ':
            elif c == ')':
                val = evaluate(tokens)
                tokens, d = st.pop()
                tokens[-1] += val
                tokens[-1] += c
        return int(tokens[0])

  • 0

    Why did you use dict(d) ?

  • 0

    @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.