different-ways-to-add-parentheses.go

// https://leetcode.com/problems/different-ways-to-add-parentheses/

func diffWaysToCompute(input string) []int {
    numbers, operators := parse(input)
    
    return generate(numbers, operators)
}

func generate(numbers []int, operators []rune) []int {
    if len(numbers) < 2 {
        return numbers
    }
    
    if len(numbers) == 2 {
        return []int{eval(numbers[0], numbers[1], operators[0])}
    }
    
    result := []int{}
    
    for i := 0; i < len(operators); i++ {
        left := generate(numbers[:i+1], operators[:i])
        operator := operators[i]
        right := generate(numbers[i+1:], operators[i+1:])
        
        if len(right) == 0 {
            result = append(result, left...)
        }
        
        if len(left) == 0 {
            result = append(result, right...)
        }
        
        for _, a := range left {
            for _, b := range right {
                c := eval(a, b, operator)
                result = append(result, c)
            }
        }
    }
    
    return result
}

func eval(a, b int, operator rune) int {
    switch operator {
    case '-':
        return a - b
    case '+':
        return a + b
    case '*':
        return a * b
    case '/':
        return a / b
    }
    
    panic("unsupported operation")
}

func parse(input string) ([]int, []rune) {
    numbers := []int{}
    operators := []rune{}
    currNumber := 0
    
    for _, ch := range input {
        if isDigit(ch) {
            digit := int(ch - rune('0'))
            currNumber = currNumber * 10 + digit
            continue
        }
        
        numbers = append(numbers, currNumber)
        currNumber = 0
        operators = append(operators, ch)
    }
    
    numbers = append(numbers, currNumber)
    
    return numbers, operators
}

func isDigit(ch rune) bool {
    return ch >= rune('0') && ch <= rune('9')
}