2.2: Calculator

As in 2.1 we are aiming to separate the branching logic from the algorithm, making it pluggable and the algorithm reusable. And in this example, we actually do code two separate branching tables using the same algorithm for two different effects.

This is a simple Reverse Polish Notation calculator, accepting expressions in the form of "2 3 + 1 -" and evaluating a result depending on the branching logic supplied.

We start with a very similar type declaration as in the previous post, a action function and a dispatch table. The Stack is used to record the state of the evaluation.

type (
 ActionFunc  func(string, *Stack)
 ActionTable map[string]ActionFunc
)

The evaluate function accepts the expression, the branching logic and a stack for the state. It loops through the expression and evaluates which action to take depending on the token. If the token is a number the NUMBER action is selected. Otherwise an action is selected depending on the token or a default one if that fails. The action is then executed.

The function ends with popping the top value of the stack and returning it to the caller.

func evaluate(expression []string, actions ActionTable, stack *Stack) interface{} {
 for _, t := range expression {
  var action ActionFunc
  if _, err := strconv.ParseFloat(t, 64); err == nil {
   action = actions["NUMBER"]
  } else {
   var ok bool
   if action, ok = actions[t]; !ok {
    action = actions["__DEFAULT__"]
   }
  }
  action(t, stack)
 }
 return stack.Pop()
}

The main function starts with declaring a branching logic that supports calculating an expression in RPN format using the +, -, *, / and sqrt operators. Then the evaluate algorithm is called and the result is printed.

func main() {

 calcActions := ActionTable{
  "+": func(token string, stack *Stack) {
   stack.Push(stack.PopFloat() + stack.PopFloat())
  },
  "-": func(token string, stack *Stack) {
   v := stack.PopFloat()
   stack.Push(stack.PopFloat() - v)
  },
  "*": func(token string, stack *Stack) {
   stack.Push(stack.PopFloat() * stack.PopFloat())
  },
  "/": func(token string, stack *Stack) {
   v := stack.PopFloat()
   stack.Push(stack.PopFloat() / v)
  },
  "sqrt": func(token string, stack *Stack) {
   stack.Push(math.Sqrt(stack.PopFloat()))
  },
  "NUMBER": func(token string, stack *Stack) {
   v, _ := strconv.ParseFloat(token, 64)
   stack.Push(v)
  },
  "__DEFAULT__": func(token string, stack *Stack) {
   panic(fmt.Sprintf("Unkown token %q", token))
  },
 }

 v := evaluate(os.Args[1:], calcActions, new(Stack))
 fmt.Printf("Result: %f\n", toFloat(v))

Next we create a branching logic that supports building an Abstract Syntax Tree from a RPN expression. The __DEFAULT__ function is selected for all tokens except numbers, building a tree of slices on the stack. The result is then printed twice, once in the raw format of the Go data structure and once in the form of an infix string, built by the astToString function.

 astActions := ActionTable{
  "NUMBER": func(token string, stack *Stack) {
   stack.Push(token)
  },
  "__DEFAULT__": func(token string, stack *Stack) {
   t := stack.Pop()
   if stack.Len() > 0 {
    stack.Push([]interface{}{token, stack.Pop(), t})
   } else {
    stack.Push([]interface{}{token, t})
   }

  },
 }

 v = evaluate(os.Args[1:], astActions, new(Stack))
 fmt.Printf("AST tree: %v\n", v)
 fmt.Printf("AST to string: %q\n", astToString(toInterfaces(v)))

}

func astToString(tree []interface{}) string {
 if len(tree) == 1 {
  return toString(tree[0])
 }
 if len(tree) == 2 {
  op, val := toString(tree[0]), toInterfaces(tree[1])
  s := astToString(val)
  return "( " + op + " " + s + " )"
 }
 op, l, r := toString(tree[0]), toInterfaces(tree[1]), toInterfaces(tree[2])
 s1 := astToString(l)
 s2 := astToString(r)
 return "( " + s1 + " " + op + " " + s2 + " )"
}

At the end of the file, not shown here, are some auxiliary functions. A stack data structure is defined along with three typecasting functions.

Get the full code at GitHub.