Skip to content

Instantly share code, notes, and snippets.

@cedricblondeau
Last active November 7, 2016 03:37
Show Gist options
  • Save cedricblondeau/15aae6a5d846d7591dbf029e57f4e723 to your computer and use it in GitHub Desktop.
Save cedricblondeau/15aae6a5d846d7591dbf029e57f4e723 to your computer and use it in GitHub Desktop.
Evaluates string expressions with positives integers, parentheses and +/- operators only.

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
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
}
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"))
}
}
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
}
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")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment