Stack and Reverse Polish Notation Calculator

rpn.go

package rpn

import (
    "stack"
    "strconv"
    "strings"
)

var operators = map[string]func(int, int) int{
    "+": func(left int, right int) int { return left + right },
    "-": func(left int, right int) int { return left - right },
    "/": func(left int, right int) int { return left / right },
    "*": func(left int, right int) int { return left * right },
}

/*
Evaluate a postfix expression. The following operators are supported: + - * /
*/
func Evaluate(input string) int {
    parts := strings.Split(input, " ")
    var s stack.Stack

    for _, part := range parts {
        if operator, ok := operators[part]; ok {
            right := s.Pop()
            left := s.Pop()
            s.Push(operator(left, right))
        } else if number, err := strconv.Atoi(part); err == nil {
            s.Push(number)
        } else {
            panic("Didn't recognize input.")
        }
    }

    if s.Size() != 1 {
        panic("Unbalanced expression!")
    }

    return s.Pop()
}

rpn_test.go

package rpn

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestBalancedExpression(t *testing.T) {
    result := Evaluate("15 7 +")
    assert.Equal(t, 22, result)
}

func TestCompositeExpression(t *testing.T) {
    result := Evaluate("15 5 + 7 2 - * 10 /")
    assert.Equal(t, 10, result)
}

func TestUnrecognizedOperator(t *testing.T) {
    defer func() {
        if recover() == nil {
            t.Errorf("Should have failed on unrecognized operator.")
        }
    }()

    Evaluate("15 5 ^")
}

func TestUnbalancedExpression(t *testing.T) {
    defer func() {
        if recover() == nil {
            t.Errorf("Should have failed to process unbalanced expression.")
        }
    }()

    Evaluate("15 7 + 12")
}

stack.go

package stack

import (
    "fmt"
    "strings"
)

/*
Stack A simple array-based stack.
*/
type Stack struct {
    ptr  int     // points to the top of stack
    data [20]int // the stack items
    size int     // number of elements
}

/*
Push adds an item to the stack.
*/
func (s *Stack) Push(value int) {
    s.ptr++
    s.data[s.ptr] = value
    s.size++
}

/*
Pop removes and returns the top of the stack.
*/
func (s *Stack) Pop() int {

    value := s.data[s.ptr]
    s.data[s.ptr] = 0
    s.ptr--
    s.size--
    return value
}

/*
Peek will return the value at the top of the stack without removing it.
*/
func (s *Stack) Peek() int {
    return s.data[s.ptr]
}

func (s Stack) String() string {
    parts := make([]string, 0)

    for index, value := range s.data[0 : s.ptr+1] {
        parts = append(parts, fmt.Sprintf("[%d:%d]", index, value))
    }

    return strings.Join(parts, " ")
}

/*
Empty returns true if there are no items in the stack.
*/
func (s *Stack) Empty() bool {
    return s.size == 0
}

/*
Size returns the number of items in the stack
*/
func (s *Stack) Size() int {
    return s.size
}

stack_test.go

package stack

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestPushToStack(t *testing.T) {
    var s Stack
    expected := 3

    s.Push(expected)

    assert.False(t, s.Empty())
    assert.Equal(t, expected, s.Peek())
}

func TestPopFromStack(t *testing.T) {
    var s Stack
    expected := 3

    s.Push(expected)
    result := s.Pop()

    assert.Equal(t, expected, result)
    assert.Equal(t, len(s.data), 10)
    assert.True(t, s.Empty())
}

func TestPushMultipleValues(t *testing.T) {
    var s Stack
    values := []int{3, 7, 9}

    for _, val := range values {
        s.Push(val)
    }

    assert.Equal(t, values[len(values)-1], s.Peek())
    assert.False(t, s.Empty())
}

func TestPopMultipleValues(t *testing.T) {
    var s Stack
    values := []int{3, 7, 9}
    expectedValues := []int{9, 7, 3}

    for _, val := range values {
        s.Push(val)
    }

    for _, expected := range expectedValues {
        assert.Equal(t, expected, s.Pop())
    }

    assert.True(t, s.Empty())
}