Yuki Ito

Posted on

# The Reverse Polish Notation evaluator using only call stack

I wrote evaluator for RPN(Reverse Polish Notation) using the call stack in Go.

``````package main

import (
"bufio"
"fmt"
"os"
"strconv"
)

func main() {

var v []interface{}
for {
var s string
if _, err := fmt.Fscan(r, &s); err != nil {
break
}

var t interface{}
n, err := strconv.Atoi(s)
if err == nil {
t = n
} else {
t = []rune(s)[0]
}

v = append(v, t)
}

calc(v)  // should be nil
}

type f func(int) f

func calc(v []interface{}) f {
if len(v) == 0 {
return f(func(n int) f {
fmt.Println(n)
return nil
})
}

switch t := v[0].(type) {
case int:
return calc(v[1:])(t)
case rune:
return c(v[1:], t)
default:
panic(t)
}
}

func c(v []interface{}, t rune) f {
switch t {
case '+':
return op(v, func(a, b int) int {
return a + b
})
case '-':
return op(v, func(a, b int) int {
return a - b
})
default:
return op(v, func(a, b int) int {
return a * b
})
}
}

func op(v []interface{}, fn func(int, int) int) f {
return f(func(b int) f {
return f(func(a int) f {
return calc(v)(fn(a, b))
})
})
}
``````

It inputs the space-separated notation like `1 2 + 3 4 + +` and prints like `10`.

I guess it do same things as the usual way to solve RPN(using real stack, not call stack) but unsure. Does it make sense?

I have many suggestions, but is hard to do a code review here.
Starting with those interface{}, you can get rid of them and make some custom structs or check if is a digit or sign. By removing the interface{} you will also get rid of the reflection.

I would say to move the operations in a map like

``````type op func(a, b int) int

var ops = map[Rune]op {
'+': func(a, b int) int {
return a + b
},
'-': func(a, b int) int {
return a - b
}
'*': func(a, b int) int {
return a * b
}
``````

This way you solve a few issues:

• you simplify the code
• I think it will be more verbose
• when you want to add a new operator you don't change the code, just add a new entry in the map
• that `default` was not good, you treat any input as a *, which is obviously wrong. If the input is not recognized it is ok to panic, you literally do not know what to do with it, it is invalid.

Ping me anytime on if you need extra Go reviews on Github or check the #reviews channel on the Gophers slack.