leetcode day 30: RPN

Take an array of strings in RPN and evaluate it.

This is all about managing the stack. I started trying to code a Stack class, but dumped that for simply using append and slicing to manage the stack. Performance was okay: 73% runtime, 41% memory; probably good enough for a pass.

func evalRPN(tokens []string) int {
    stack := []int{}
    for _,token := range(tokens) {
        switch token {
            case "+":
            op2 := stack[len(stack)-1]
            op1 := stack[len(stack)-2]
            stack = stack[:len(stack)-1]
            stack[len(stack)-1] = op1 + op2

            case "-":
            op2 := stack[len(stack)-1]
            op1 := stack[len(stack)-2]
            stack = stack[:len(stack)-1]
            stack[len(stack)-1] = op1 - op2

            case "/":
            op2 := stack[len(stack)-1]
            op1 := stack[len(stack)-2]
            stack = stack[:len(stack)-1]
            stack[len(stack)-1] = op1 / op2
    
            case "*":
            op2 := stack[len(stack)-1]
            op1 := stack[len(stack)-2]
            stack = stack[:len(stack)-1]
            stack[len(stack)-1] = op1 * op2

            default:
              i, err := strconv.Atoi(token)
              if err != nil {
                  panic(fmt.Sprintf("unparseable token %s", token))
              }
              stack = append(stack, i)
        }
    }
    return stack[len(stack)-1]
}

My guess is that if I used a real stack pointer to manage the stack, it’d be faster.

func evalRPN(tokens []string) int {
    stack := make([]int, 10000)
    sp := -1
    for _,token := range(tokens) {
        switch token {
            case "+":
            op2 := stack[sp]
            op1 := stack[sp-1]
            sp--
            stack[sp] = op1 + op2

            case "-":
            op2 := stack[sp]
            op1 := stack[sp-1]
            sp--
            stack[sp] = op1 - op2

            case "/":
            op2 := stack[sp]
            op1 := stack[sp-1]
            sp--
            stack[sp] = op1 / op2

            case "*":
            op2 := stack[sp]
            op1 := stack[sp-1]
            sp--
            stack[sp] = op1 * op2

            default:
              i, err := strconv.Atoi(token)
              if err != nil {
                  panic(fmt.Sprintf("unparseable token %s", token))
              }
              sp++
              stack[sp] = i
        }
    }
    return stack[sp]
}

And no, it is not! Exact same runtime percentile, and used a little less memory (35th percentile).

Couple of quite elegant idea in the solutions; I really liked this one:

func evalRPN(tokens []string) int {
    stack := make([]int, 10000)
    sp := -1
    ops := map[string]func(int,int) int{
        "+": func(i, j int) int { return i + j},
        "-": func(i, j int) int { return i - j},
        "/": func(i, j int) int { return i / j},
        "*": func(i, j int) int { return i * j},
    }
    for _,token := range(tokens) {
        i, err := strconv.Atoi(token)
        if err != nil {
            // operator
            stack[sp-1] = ops[token](stack[sp-1], stack[sp])
            sp--
        } else {
            sp++
            stack[sp] = i
        }
    }
    return stack[sp]
}

We get rid of the switch altogether using the fact that the tokens are either valid numbers or operators, and we make the operators into anonymous functions in a map. If the token fails to convert to a number, then we look it up and call the appropriate function. This is far more fragile though, since any bad token will result in a “no such key” error on the ops map…and we only gain 3% in the runtime. I’ll settle for the first one as good enough for a pass.