Reverse Polish Calculator in Go

Question

I'm very new to Go (this is my first real program), and I was hoping to see if there was anything I was missing about the language or any ways to make it more idiomatic.

calculator.go

package calculator
import (
 "../stack"
 "unicode"
 "strconv"
)
func Calculate(input string) int {
 stack := new(stack.Stack)
 for i := 0; i < len(input); i++{
 c := rune(input[i])
 if unicode.IsDigit(c) {
 stack.Push(parseNumber(input, &i))
 }
 switch c {
 case '+':
 b := stack.Pop()
 a := stack.Pop()
 stack.Push(a + b)
 case '-':
 b := stack.Pop()
 a := stack.Pop()
 stack.Push(a - b)
 case '*':
 b := stack.Pop()
 a := stack.Pop()
 stack.Push(a * b)
 case '/':
 b := stack.Pop()
 a := stack.Pop()
 stack.Push(a / b)
 }
 }
 if(stack.Size() > 1) {
 panic("Input did not fully simplify")
 }
 return stack.Pop()
}
func parseNumber(input string, i *int) int {
 initialIndex := *i
 for unicode.IsDigit(rune(input[*i])) {
 *i++
 }
 num, _ := strconv.Atoi(input[initialIndex : *i])
 return num
}

calculator_test.go

package calculator
import (
 "testing"
)
func TestCalculate(t *testing.T) {
 tests := map[string]int{
 "3 4 +":7,
 "3 4 -":-1,
 "3 4 *":12,
 "3 4 /":0,
 "1 1 + 2 -":0,
 "5 10 * 2 /":25,
 }
 for input, expected := range tests {
 result := Calculate(input)
 if(result != expected) {
 t.Log("Calculate failed. Expected ",expected, ", got ", result)
 t.Fail()
 }
 }
}

stack.go

package stack
type Stack struct {
 i int
 // fixed size
 data [100]int
}
func (s *Stack) Push(i int) {
 if(s.i + 1 >= len(s.data)){
 panic("Out of memory!")
 }
 s.data[s.i] = i
 s.i++
}
func (s *Stack) Pop() int {
 if(s.i - 1 < 0){
 panic("Can't pop when there is no data!")
 }
 s.i--
 return s.data[s.i]
}
func (s *Stack) Size() int {
 return s.i
}

stack_test.go Not very proud of this. Is there any way I can reduce the duplicated code? Are there any built in assert methods?

package stack
import (
 "testing"
)
func TestStack(t *testing.T) {
 s := new(Stack)
 if(s.Size() != 0) {
 t.Fail()
 }
 s.Push(1)
 if(s.Size() != 1) {
 t.Fail()
 }
 s.Push(2)
 if(s.Size() != 2) {
 t.Fail()
 }
 s.Push(3)
 if(s.Size() != 3) {
 t.Fail()
 }
 if(s.Pop() != 3) {
 t.Log("Didn't pop in order!")
 t.Fail() 
 }
 if(s.Size() != 2) {
 t.Fail()
 }
 if(s.Pop() != 2) {
 t.Log("Didn't pop in order!")
 t.Fail() 
 }
 if(s.Size() != 1) {
 t.Fail()
 }
 if(s.Pop() != 1) {
 t.Log("Didn't pop in order!")
 t.Fail() 
 }
 if(s.Size() != 0) {
 t.Fail()
 }
}

Answer 1

1. Don't use relative import paths.

Such as "../stack". Instead, use full import paths like (e.g.) "github.com/kyranstar/RPN/stack". That would be a reasonable path to use if you put your source somewhere like $GOPATH/github.com/kyranstar/some-repo-name/, since you're a GitHub user. This is discussed in How to write Go code.

So for example:

$GOPATH/src/github.com
└── kyranstar
 └── RPN
 ├── calculator
 │  ├── calculator.go
 │  └── calculator_test.go
 └── stack
 ├── stack.go
 └── stack_test.go

Note that you can do this even if you never have any intention of making this available on github. In that case you'd just be using "github.com/kyranstar" as a convient prefix that won't conflict with anyone else (e.g. I use "bitbucket.org/myname/...", "github.com/myname/...", and "myname-test/..." as Go import prefixes depending on what I'm doing).

You didn't include anything to build a run-able command. If you're fine with just go testing your packages, you don't need to. But if you want to build a standalone non-test program you could either put a simple package main right in .../kyranstar/RPN/anyname.go or if the repo might have multiple commands to build, in .../kyranstar/RPN/cmd/name-of-command/anyname.go. In either case, go build and go install will use the base name of the containing directory as the executable name.

2. Run go fmt (or gofmt, or goimports) on all your Go source.

On your source the changes it makes includes removing extraneous parenthesizes, it's idiomatic to use if x { rather than if(x) {.

3. Slices vs arrays and your stack package.

It's usually better to use slices rather than fixed sizes arrays (like you do in stack.go) unless you actually have a fixed size (e.g. perhaps type CoordinateVector [3]float64).

Then stack can become just something like:

package stack
type Stack []int
func (s Stack) Len() int { return len(s) }
func (s *Stack) Push(i int) { *s = append(*s, i) }
func (s *Stack) Pop() int {
 n := len(*s) - 1
 v := (*s)[n]
 *s = (*s)[:n]
 return v
}

Note, Len() is more common/idiomatic than Size() (and gorename can help rename such things for you including all references anywhere in your $GOPATH). This doesn't have a fixed size like yours does at the slight expense of re-allocations as it grows.

Note that naming a package stack with a single type Stack causes code using it to stutter, e.g. s := new(stack.Stack). There is a blog entry about Package names that addresses this. For example, perhaps such a stack package could have several types like Int, Int64, Float64, etc and then callers would use stack.Int, stack.Int64, stack.Float64, etc.

Alternatively, the changed package becomes so small that it is common to just stick it into a stack.go file in the current (calculator in this case) package and use it as a non-exported package type.

Finally, where you use this you have stack := new(stack.Stack). Note that you are creating a local variable which shadows the import name. You've made it difficult/impossible to use anything from the stack package anywhere else in the function (e.g. to make a second stack for any reason). If for no other reason then to prevent confusion in people reading the code, it's usually best to avoid such things.

4. Strings by byte or rune.

Again there is a blog entry that covers this: Strings, bytes, runes and characters in Go.

You have:

 for i := 0; i < len(input); i++ {
 c := rune(input[i])

this loops by bytes instead of by Unicode code points (called runes in Go). This should normally be:

 for i, c := range input {

But then it iterferes with your parseNumber usage. Sadly, strconv doesn't appear to have a function that will parse out a number from the start of a string and tell you how many bytes/runes were parsed. Since you're only handling digits (and not decimal, negatives, floating point, etc) it'd be pretty use to just make parseNumber such a function.

5. Return error, don't panic!

You should never panic out of a package for anything other than critical unrecoverable programming errors. (For example, the above Stack.Pop will just panic if the caller miss-uses the stack, it's up to the caller to check Len if they need to.) You should instead do something like this:

func Calculate(input string) (int, error) {
 // ...
 if stack.len() != 1 {
 return 0, errors.New("did not fully simplify")
 }
 return stack.Pop(), nil
}

Note that it's recomended that error strings should not be capitalized or end in punctuation. golint can help catch such things.

6. Testing

Instead of:

 t.Log("something")
 t.Fail()

Use t.Error and/or t.Errorf.

Use a slice instead of a map for testcase data. A map isn't needed, and it's unordered. You don't show what input caused the failure which makes it harder than needed for someone fixing a problem down the road. You don't test failure cases (see Go's testing coverage to see what your tests are missing).

So something like this perhaps:

func TestCalculate(t *testing.T) {
 tests := []struct {
 in string
 out int
 }{
 {"3 4 +", 7},
 {"3 4 -", -1},
 {"3 4 *", 12},
 {"3 4 /", 0},
 {"1 1 + 2 -", 0},
 {"5 10 * 2 /", 25},
 }
 for _, d := range tests {
 result, err := Calculate(d.in)
 if err != nil {
 t.Errorf("Calculate(%q) failed: %v", d.in, err)
 }
 if result != d.out {
 t.Errorf("Calculate(%q) gave %v, expected %v",
 d.in, result, d.out)
 }
 }
}

You mention repeated code in stack_test.go and assert methods. Although there are various third party testing/assert packages, I don't recommend them.

Usings what I've just mentioned, if I wanted to test a few series of operations on something I'd likely do something like this:

func TestStack(t *testing.T) {
 const (
 doPush = iota
 doPop
 )
 tests := [][]struct {
 op int
 val int
 l int
 }{
 // Simple ×ばつPush then ×ばつPop:
 {
 {doPush, 1, 1},
 {doPush, 2, 2},
 {doPush, 3, 3},
 {doPop, 3, 2},
 {doPop, 2, 1},
 {doPop, 1, 0},
 },
 // ... other cases here ...
 }
nextTest:
 for i, steps := range tests {
 s := new(Stack)
 for j, d := range steps {
 // Could use t.Log/t.Logf to verbosely
 // log something about the step/op being done.
 switch d.op {
 case doPush:
 s.Push(d.val)
 case doPop:
 if g := s.Pop(); g != d.val {
 t.Errorf("%d:%d poped %v, expected %v",
 i, j, g, d.val)
 continue nextTest
 }
 }
 if g := s.Len(); g != d.l {
 t.Errorf("%d:%d end len %v, expected %v",
 i, j, g, d.l)
 continue nextTest
 }
 }
 }
}

Then it becomes easy for anyone to just add data to the struct for more testcases or more steps.

One complication here is that I wanted it to stop a specific test case on the first failure (since each remaining step depends on the previous ones working). Normally you'd just use t.Fatal in place of t.Error to signal that your test function can't proceed. Here I just continue on with the next test case so I need the (some would call ugly) loop label.

---

In addition to the previously mentioned links, Effictive Go and the Go Author's Go Code Review Comments should be considered required reading.