DEV Community

Yuki Ito
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() {
    r := bufio.NewReader(os.Stdin)

    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))
        })
    })
}
Enter fullscreen mode Exit fullscreen mode

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?

Top comments (1)

Collapse
 
bgadrian profile image
Adrian B.G.

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.