Evaluates string expressions with positives integers, parentheses and +/- operators only.

go-simple-calculator.md

go-simple-calculator

Evaluates string expressions with positives integers, parentheses and +/- operators only.

Method #1 - Calculate & Replace

Naive way to solve an expression, like a human would do with paper and pen.

Example:

	Input	Output
Iteration #1	25 - (8 - (2 + 3))	25 - (8 - 5)
Iteration #2	25 - (8 - 5)	25 - 3
Iteration #3	25 - 3	22

See replace.go for implementation details.

Method #2 - Postfix

Transforms an infix expression into a postfix expression and evaluates the postfix expression.

Usage:

p := postfix.FromInfix("25 - (8 + 2)") // []string{"25", "8", "2", "+", "-"}
res := postfix.Evaluate(p) // 15

See postfix.go.

Limitations

• Only positives integers
• Only +/- operators, won't support division, multiplication, powers, etc.
• There is no input validation
• Clearly more readability-oriented than performance-oriented

postfix.go

package postfix

import (
	"strconv"
	"strings"

	"github.com/emirpasic/gods/stacks/arraystack"
)

// Evaluate evaluates a postfix expression
func Evaluate(tokens []string) int {
	stack := arraystack.New()
	l := len(tokens)

	for i := 0; i < l; i++ {
		token := tokens[i]

		if isNumeric(token) {
			i, _ := strconv.Atoi(token)
			stack.Push(i)
		}

		if isOperator(token) {
			op := token
			a, aOk := stack.Pop()
			b, bOk := stack.Pop()
			if aOk && bOk {
				stack.Push(calc(op, b.(int), a.(int)))
			}
		}
	}

	if !stack.Empty() {
		result, _ := stack.Pop()
		return result.(int)
	}

	return 0
}

// FromInfix tranforms a infix expression into a postfix expression
func FromInfix(infix string) []string {
	tokens := tokens(infix)
	l := len(tokens)
	operators := arraystack.New()
	result := []string{}

	for i := 0; i < l; i++ {
		token := tokens[i]

		if isNumeric(token) {
			result = append(result, token)

		} else if token == "(" {
			operators.Push(token)

		} else if token == ")" {
			operator, ok := operators.Pop()
			for ok && operator != "(" {
				result = append(result, operator.(string))
				operator, ok = operators.Pop()
			}

		} else if isOperator(token) {
			for !operators.Empty() {
				peek, ok := operators.Peek()
				if ok && peek == "(" {
					break
				}
				operator, _ := operators.Pop()
				result = append(result, operator.(string))
			}
			operators.Push(token)
		}
	}

	for !operators.Empty() {
		operator, _ := operators.Pop()
		result = append(result, operator.(string))
	}

	return result
}

func tokens(infix string) []string {
	result := []string{}
	cur := ""
	l := len(infix)
	for i := 0; i < l; i++ {
		char := infix[i : i+1]

		if isOperator(char) || char == "(" || char == ")" {
			if cur != "" {
				result = append(result, cur)
			}
			result = append(result, char)
			cur = ""
		} else if isNumeric(char) {
			cur = cur + char
		}
	}
	if cur != "" {
		result = append(result, cur)
	}
	return result
}

func isNumeric(char string) bool {
	if i, err := strconv.Atoi(char); err == nil {
		if i >= 0 {
			return true
		}
	}
	return false
}

func isOperator(char string) bool {
	if len(char) == 1 {
		return strings.ContainsAny(char, "+-")
	}
	return false
}

func calc(op string, a int, b int) int {
	if op == "+" {
		return a + b
	}
	if op == "-" {
		return a - b
	}
	return 0
}

postfix_test.go

package postfix

import (
	"strings"
	"testing"

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

func TestIsNumeric(t *testing.T) {
	assert.False(t, isNumeric(" "))
	assert.False(t, isNumeric("+"))
	assert.False(t, isNumeric("-"))
	assert.False(t, isNumeric("/"))
	assert.False(t, isNumeric("*"))
	assert.False(t, isNumeric("A"))   // Intentional
	assert.False(t, isNumeric("B"))   // Intentional
	assert.False(t, isNumeric("1 "))  // Intentional
	assert.False(t, isNumeric("-1"))  // Intentional
	assert.False(t, isNumeric("2.5")) // Intentional
	assert.False(t, isNumeric("2,5")) // Intentional
	assert.True(t, isNumeric("0"))
	assert.True(t, isNumeric("1"))
	assert.True(t, isNumeric("2"))
	assert.True(t, isNumeric("251"))
	assert.True(t, isNumeric("0251"))
}

func TestIsOperator(t *testing.T) {
	assert.False(t, isOperator(" "))
	assert.False(t, isOperator("a"))
	assert.False(t, isOperator("A"))
	assert.False(t, isOperator("!"))
	assert.False(t, isOperator("&"))
	assert.False(t, isOperator("*"))  // Intentional
	assert.False(t, isOperator("/"))  // Intentional
	assert.False(t, isOperator("- ")) // Intentional
	assert.True(t, isOperator("-"))
	assert.True(t, isOperator("+"))
}

func TestTokens(t *testing.T) {
	assert.Equal(t, []string{"25", "+", "8"}, tokens("25+8"))
	assert.Equal(t, []string{"25", "+", "8"}, tokens("25 + 8"))
	assert.Equal(t, []string{"25", "-", "8"}, tokens("25 - 8"))
	assert.Equal(t, []string{"25", "-", "(", "8", "+", "2", ")"}, tokens("25 - (8 + 2)"))
}

func TestFromInfix(t *testing.T) {
	assert.Equal(t, "3 4 +", fromInfix("3 + 4"))
	assert.Equal(t, "1 2 + 3 +", fromInfix("1+2+3"))
	assert.Equal(t, "25 3 + 2 +", fromInfix("25+3+2"))
	assert.Equal(t, "25 8 2 + -", fromInfix("25 - (8 + 2)"))
}

func fromInfix(infix string) string {
	return strings.Join(FromInfix(infix), " ")
}

func TestEval(t *testing.T) {
	assert.Equal(t, 3, Evaluate(FromInfix("2 + 1")))
	assert.Equal(t, 6, Evaluate(FromInfix("1 + 2 + 3")))
	assert.Equal(t, 10, Evaluate(FromInfix("3 + 3 + (2 + 2)")))
	assert.Equal(t, 13, Evaluate(FromInfix("4 + 5 + (2 - 4 + (3 + 3))")))
	assert.Equal(t, 13, Evaluate(FromInfix("(4 + 5 + (2 - 4 + (3 + 3)))")))
	assert.Equal(t, 11, Evaluate(FromInfix("(4 + 5 + (2 - 4 + (3 + 3))) - 2")))
	assert.Equal(t, 15, Evaluate(FromInfix("25 - (8 + 2)")))
	assert.Equal(t, 15, Evaluate(FromInfix("(25 - (8 + 2))")))
	assert.Equal(t, 16, Evaluate(FromInfix("(25 + 1 - (8 + 2))")))
	assert.Equal(t, 14, Evaluate(FromInfix("(25 - 1 - (8 + 2))")))
	assert.Equal(t, 23, Evaluate(FromInfix("(25 - 1 - (8 - (2 + 5)))")))
}

func BenchmarkTokens(b *testing.B) {
	for n := 0; n < b.N; n++ {
		tokens("(4 + 5 + (2 - 4 + (3 + 3))) - 2")
	}
}

func BenchmarkFromInfix(b *testing.B) {
	for n := 0; n < b.N; n++ {
		FromInfix("(4 + 5 + (2 - 4 + (3 + 3))) - 2")
	}
}

func BenchmarkEvaluate(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Evaluate([]string{"4", "5", "+", "2", "4", "-", "3", "3", "+", "+", "+", "2", "-"})
	}
}

func BenchmarkEvaluateFromInfix(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Evaluate(FromInfix("(4 + 5 + (2 - 4 + (3 + 3))) - 2"))
	}
}

replace.go

package replace

import (
	"strconv"
	"strings"

	"github.com/emirpasic/gods/stacks/arraystack"
)

const plus = "+"
const minus = "-"
const divide = "/"
const multiply = "*"
const leftParenthesis = "("
const rightParenthesis = "("

// Evaluate parses infix notation expressions and returns result
func Evaluate(str string) int {
	return calc(simplify(strip(str)))
}

func strip(str string) string {
	str = strings.Replace(str, " ", "", -1)
	return str
}

func simplify(str string) string {
	l := len(str)
	stack := arraystack.New()

	lastExp := ""
	lastExpResult := 0
	for i := 0; i < l; i++ {
		if str[i:i+1] == "(" {
			stack.Push(i)
		}

		if str[i:i+1] == ")" {
			start, _ := stack.Pop()
			exp := str[start.(int) : i+1]

			toEval := exp
			if len(lastExp) > 0 {
				toEval = strings.Replace(toEval, lastExp, strconv.Itoa(lastExpResult), 1)
			}
			lastExpResult = calc(toEval[1 : len(toEval)-1])

			lastExp = exp
		}
	}
	return strings.Replace(str, lastExp, strconv.Itoa(lastExpResult), 1)
}

func calc(str string) int {
	str = strip(str)
	sum := 0

	additions := strings.Split(str, plus)
	for _, addition := range additions {
		tokens := strings.Split(addition, minus)
		operand, _ := strconv.Atoi(tokens[0])
		sum = sum + operand

		l := len(tokens)
		for i := 1; i < l; i++ {
			substraction := tokens[i]
			operand, _ := strconv.Atoi(substraction)
			sum = sum - operand
		}
	}

	return sum
}

replace_test.go

package replace

import (
	"testing"

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

func TestEvaluate(t *testing.T) {
	assert.Equal(t, 3, Evaluate("2 + 1"))
	assert.Equal(t, 6, Evaluate("1 + 2 + 3"))
	assert.Equal(t, 10, Evaluate("3 + 3 + (2 + 2)"))
	assert.Equal(t, 13, Evaluate("4 + 5 + (2 - 4 + (3 + 3))"))
	assert.Equal(t, 13, Evaluate("(4 + 5 + (2 - 4 + (3 + 3)))"))
	assert.Equal(t, 11, Evaluate("(4 + 5 + (2 - 4 + (3 + 3))) - 2"))
	assert.Equal(t, 15, Evaluate("25 - (8 + 2)"))
	assert.Equal(t, 15, Evaluate("(25 - (8 + 2))"))
	assert.Equal(t, 16, Evaluate("(25 + 1 - (8 + 2))"))
	assert.Equal(t, 14, Evaluate("(25 - 1 - (8 + 2))"))
	assert.Equal(t, 23, Evaluate("(25 - 1 - (8 - (2 + 5)))"))
}

func TestCalc(t *testing.T) {
	assert.Equal(t, 6, calc("3 + 3"))
	assert.Equal(t, 1, calc("2 - 1"))
	assert.Equal(t, 1, calc("-1 + 2"))
	assert.Equal(t, 9, calc("3 + 4 + 2"))
	assert.Equal(t, 7, calc("3 + 4 + 2 - 2"))
	assert.Equal(t, 1, calc("-1 + 2"))
	assert.Equal(t, -4, calc("-2 + -2"))
}

func BenchmarkEvaluate(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Evaluate("(4 + 5 + (2 - 4 + (3 + 3))) - 2")
	}
}