Simple recursive python solution


  • 2
    M

    Basic idea is using each operator to divide the whole string into three part:

    sub_str1, operator, sub_str2
    

    then recursively apply "compute" function on each sub_str.

    Take "2*3-4*5" for example:

    compute("2*3-4*5")
    -->compute("2") * compute("3-4*5")
    -->compute("2*3") - compute("4*5")
    -->compute("2*3-4") * compute("5")
    

    The AC code:

    def token_stream(input):
        num = 0
        for ch in input:
            if ch.isdigit():
                num = num * 10 + ord(ch) - ord('0')
            else:
                yield num
                yield ch
                num = 0
        yield num
    
    def calc(num1, operator, num2):
        if operator == '+':
            return num1 + num2
        elif operator == '-':
            return num1 - num2
        elif operator == '*':
            return num1 * num2
        else:
            raise ValueError
    
    def compute(tokens):
        n = len(tokens)
        if n == 1:
            yield tokens[0]
        elif n % 2 == 1:
            for i in range(1, n, 2):
                for num1 in compute(tokens[:i]):
                    for num2 in compute(tokens[i+1:]):
                        yield calc(num1, tokens[i], num2)
        else:
            raise ValueError
    
    class Solution:
        # @param {string} input
        # @return {integer[]}
        def diffWaysToCompute(self, input):
            tokens = tuple(token_stream(input))
            return list(compute(tokens))

Log in to reply
 

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