Quick hacked-up shunting yard algorithm

shuntingyard.go

package main

import (
	"io"
	"log"
	"strings"
)

type (
	Operator   string
	Number     string
	Var        string
	OpenParen  struct{}
	CloseParen struct{}
)

var precedence = map[Operator]int{
	"*": 5, "/": 5,
	"+": 6, "-": 6,
	"<": 8, ">": 8, "<=": 8, ">=": 8,
	"==": 9, "!=": 9,
	"&&": 13,
	"||": 14,
}

func tokenize(in io.RuneReader, out chan interface{}) {
	defer close(out)

	var last rune
	read := func() (r rune, done bool) {
		if last != 0 {
			r, last = last, 0
		} else {
			var err error
			if r, _, err = in.ReadRune(); err == io.EOF {
				return 0, true
			} else if err != nil {
				log.Fatalf("error: read: %s", err)
			}
		}
		return r, false
	}
	unread := func(r rune) {
		last = r
	}

	var done bool
	for {
		token := make([]rune, 1)
		if token[0], done = read(); done {
			break
		}

		switch r := token[0]; {
		case r >= '0' && r <= '9':
			for {
				if r, done = read(); done {
					break
				}
				if r < '0' || r > '9' {
					unread(r)
					break
				}
				token = append(token, r)
			}
			out <- Number(token)
		case r >= 'a' && r <= 'z':
			for {
				if r, done = read(); done {
					break
				}
				if r < 'a' || r > 'z' {
					unread(r)
					break
				}
				token = append(token, r)
			}
			out <- Var(token)
		case r == ' ':
		case r == '(':
			out <- OpenParen{}
		case r == ')':
			out <- CloseParen{}
		default:
			for {
				if r, done = read(); done {
					break
				}
				if r >= '0' && r <= '9' {
					unread(r)
					break
				}
				if r >= 'a' && r <= 'z' {
					unread(r)
					break
				}
				if r == ' ' {
					unread(r)
					break
				}
				token = append(token, r)
			}
			switch op := string(token); op {
			case "||", "&&":
				out <- Operator(op)
			case "+", "-", "/", "*":
				out <- Operator(op)
			case "<", ">", "<=", ">=", "==", "!=":
				out <- Operator(op)
			default:
				log.Printf("error: unknown op %q", op)
				return
			}
		}
	}
}

func shunting(in chan interface{}) (out []interface{}) {
	var ops []interface{}
	for tok := range in {
		switch tok := tok.(type) {
		case Number, Var:
			out = append(out, tok)
		case Operator:
			for len(ops) > 0 {
				if op, ok := ops[len(ops)-1].(Operator); !ok || precedence[tok] <= precedence[op] {
					break
				}
				out, ops = append(out, ops[len(ops)-1]), ops[:len(ops)-1]
			}
			ops = append(ops, tok)
		case OpenParen:
			ops = append(ops, tok)
		case CloseParen:
			for len(ops) > 0 {
				if _, ok := ops[len(ops)-1].(OpenParen); ok {
					ops = ops[:len(ops)-1]
					break
				}
				out, ops = append(out, ops[len(ops)-1]), ops[:len(ops)-1]
			}
		}
	}
	for len(ops) > 0 {
		out, ops = append(out, ops[len(ops)-1]), ops[:len(ops)-1]
	}
	return out
}

func main() {
	for _, expr := range []string{
		"a > 10",
		"a + b / c",
		"a || b && c",
		"(a || b) && c",
		"a > 10 && b == 3 || c + 1 <= 10",
	} {
		tokens := make(chan interface{})
		go tokenize(strings.NewReader(expr), tokens)

		log.Printf("infix %q, postfix %v\n", expr, shunting(tokens))
	}
}