| 1 | /* -*-go-*- |
| 2 | * |
| 3 | * Same-fringe solver. |
| 4 | */ |
| 5 | |
| 6 | package main |
| 7 | |
| 8 | import ( |
| 9 | "fmt"; |
| 10 | "io"; |
| 11 | "os"; |
| 12 | ) |
| 13 | |
| 14 | ///-------------------------------------------------------------------------- |
| 15 | /// Utilities. |
| 16 | |
| 17 | var prog = os.Args[0]; |
| 18 | |
| 19 | func bail(msg string) { |
| 20 | fmt.Fprintf(os.Stderr, "%s: %s\n", prog, msg); |
| 21 | os.Exit(1); |
| 22 | } |
| 23 | |
| 24 | ///-------------------------------------------------------------------------- |
| 25 | /// Iteration protocol. |
| 26 | /// |
| 27 | /// A data type implements the iteration protocol by providing a method which |
| 28 | /// simply writes its consistuent elements to a provided channel. The |
| 29 | /// iteration machinery runs this method in a separate goroutine. |
| 30 | |
| 31 | // A convenient abbreviation. |
| 32 | type any interface {} |
| 33 | |
| 34 | type Iterable interface { |
| 35 | // Simply put the items to the channel CH one at a time. |
| 36 | Iterate(ch chan<- any); |
| 37 | } |
| 38 | |
| 39 | // An iterator. |
| 40 | type Iterator <-chan any; |
| 41 | |
| 42 | // Returns an iterator for a given iterable thing. |
| 43 | func MakeIterator(it Iterable) Iterator { |
| 44 | ch := make(chan any); |
| 45 | go func () { |
| 46 | it.Iterate(ch); |
| 47 | close(ch); |
| 48 | } (); |
| 49 | return ch; |
| 50 | } |
| 51 | |
| 52 | // Returns the next item from an iterator IT. If there is indeed an item |
| 53 | // available, return it and true; otherwise return nil and false. |
| 54 | func (it Iterator) Next() (any, bool) { |
| 55 | item, anyp := <-it; |
| 56 | return item, anyp; |
| 57 | } |
| 58 | |
| 59 | // Answer whether the iterators return the same items in the same order. |
| 60 | // Equality is determined using `=='. Maybe we'll do better some day. |
| 61 | func SameIterators(ia, ib Iterator) bool { |
| 62 | for { |
| 63 | a, any_a := ia.Next(); |
| 64 | b, any_b := ib.Next(); |
| 65 | if !any_a { return !any_b } |
| 66 | if a != b { break } |
| 67 | } |
| 68 | return false; |
| 69 | } |
| 70 | |
| 71 | ///-------------------------------------------------------------------------- |
| 72 | /// Node structure. |
| 73 | |
| 74 | // Just a simple binary tree. |
| 75 | type Node struct { |
| 76 | data byte; |
| 77 | left, right *Node; |
| 78 | } |
| 79 | |
| 80 | // Iteration is easy. Note that recursion is fine here: this is just a |
| 81 | // simple function. |
| 82 | func (n *Node) Iterate(ch chan<- any) { |
| 83 | if n == nil { return } |
| 84 | n.left.Iterate(ch); |
| 85 | ch <- n.data; |
| 86 | n.right.Iterate(ch); |
| 87 | } |
| 88 | |
| 89 | // Parse a tree from a textual description. The syntax is simple: |
| 90 | // |
| 91 | // tree ::= empty | `(' tree char tree `)' |
| 92 | // |
| 93 | // where the ambiguity is resolved by declaring that a `(' is a tree if we're |
| 94 | // expecting a tree. |
| 95 | func ParseTree(s string) *Node { |
| 96 | var parse func(int) (*Node, int); |
| 97 | n := len(s); |
| 98 | i := 0; |
| 99 | parse = func(i int) (*Node, int) { |
| 100 | if i < n && s[i] == '(' { |
| 101 | left, i := parse(i + 1); |
| 102 | if i >= n { bail("no data") } |
| 103 | data := s[i]; |
| 104 | right, i := parse(i + 1); |
| 105 | if i >= n || s[i] != ')' { bail("missing )") } |
| 106 | return &Node { data, left, right }, i + 1; |
| 107 | } |
| 108 | return nil, i; |
| 109 | }; |
| 110 | t, i := parse(0); |
| 111 | if i < n { bail("trailing junk") } |
| 112 | return t; |
| 113 | } |
| 114 | |
| 115 | ///-------------------------------------------------------------------------- |
| 116 | /// Main program. |
| 117 | |
| 118 | func main() { |
| 119 | switch len(os.Args) { |
| 120 | case 2: |
| 121 | t := ParseTree(os.Args[1]); |
| 122 | i := MakeIterator(t); |
| 123 | for { |
| 124 | item, winp := i.Next(); |
| 125 | if !winp { break } |
| 126 | fmt.Printf("%c", item); |
| 127 | } |
| 128 | fmt.Printf("\n"); |
| 129 | case 3: |
| 130 | ia := MakeIterator(ParseTree(os.Args[1])); |
| 131 | ib := MakeIterator(ParseTree(os.Args[2])); |
| 132 | if SameIterators(ia, ib) { |
| 133 | io.WriteString(os.Stdout, "match\n"); |
| 134 | } else { |
| 135 | io.WriteString(os.Stdout, "no match\n"); |
| 136 | } |
| 137 | default: |
| 138 | bail("bad args"); |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | ///----- That's all, folks -------------------------------------------------- |