gistfile1.go

/*
 * A quick example how to generate expression trees using
 * the Go programming language.
 */

package main

import (
    "strings"
    "container/vector"
)

/* Supported operators. Operators on left have higher priority. */
const ops_set = "/*-+"

type Node struct {
    p,value int
    left, right *Node
}

/* PrintTree:
 * @node: the tree node that we print
 *
 * Print the expression tree in prefix order. 
 */
func PrintTree(node *Node) string {
    var value string
    if node == nil {
        return ""
    }
    if node.p < 0 {
        value = string(node.value + '0')
    } else {
        value = string(ops_set[node.p])
    }
    return PrintTree(node.left) + value + PrintTree(node.right)
}

func main() {
    var expr string = "1+2*3"
    var values, ops vector.Vector
    var op *Node

    println("Original expression: " + expr)
    println("Parsing expression ...")

    /* We first separate operands and operators in separate queues. */
    for i := 0; i < len(expr); i++ {
        node := new(Node)
        idx := strings.IndexRune(ops_set, int(expr[i]))
        if idx != -1 {
            node.p = idx;
            node.value = int(expr[i])
            ops.Push(node)
        } else {
            node.value = int(expr[i] - '0')
            node.p = -1
            values.Push(node)
        }
    }
    println("Construction expression tree ...")
    /* Now we gradualy empty the two queues and construct the expression tree. */
    for ops.Len() > 0 {
        op = ops.Pop().(*Node) /* Pop() gives us an iterface, so we have to cast. */
        val1 := values.Pop().(*Node)
        val2 := values.Pop().(*Node)
        if val1 == nil || val2 == nil {
            panic("The given expression is faulty")
        }
        op.left = val2
        op.right = val1
        values.Push(op) /* Enqueue the new root back to the values. */
    }
    println("Expression from tree: " + PrintTree(op))
}