/* -*-go-*-
 *
 * Same-fringe solver.
 */

package main

import (
	"fmt"
	"io"
	"os"
)

///--------------------------------------------------------------------------
/// Utilities.

var prog = os.Args[0]

func bail(msg string) {
	fmt.Fprintf(os.Stderr, "%s: %s\n", prog, msg)
	os.Exit(1)
}

///--------------------------------------------------------------------------
/// Iteration protocol.
///
/// A data type implements the iteration protocol by providing a method which
/// simply writes its consistuent elements to a provided channel.  The
/// iteration machinery runs this method in a separate goroutine.

// A convenient abbreviation.
type any interface {}

type Iterable interface {
	// Simply put the items to the channel CH one at a time.
	Iterate(ch chan<- any)
}

// An iterator.
type Iterator <-chan any

// Returns an iterator for a given iterable thing.
func MakeIterator(it Iterable) Iterator {
	ch := make(chan any)
	go func () {
		it.Iterate(ch)
		close(ch)
	} ()
	return ch
}

// Returns the next item from an iterator IT.  If there is indeed an item
// available, return it and true; otherwise return nil and false.
func (it Iterator) Next() (any, bool) {
	item, anyp := <-it
	return item, anyp
}

// Answer whether the iterators return the same items in the same order.
// Equality is determined using `=='.  Maybe we'll do better some day.
func SameIterators(ia, ib Iterator) bool {
	for {
		a, any_a := ia.Next()
		b, any_b := ib.Next()
		if !any_a { return !any_b }
		if a != b { break }
	}
	return false
}

///--------------------------------------------------------------------------
/// Node structure.

// Just a simple binary tree.
type Node struct {
	data byte
	left, right *Node
}

// Iteration is easy.  Note that recursion is fine here: this is just a
// simple function.
func (n *Node) Iterate(ch chan<- any) {
	if n == nil { return }
	n.left.Iterate(ch)
	ch <- n.data
	n.right.Iterate(ch)
}

// Parse a tree from a textual description.  The syntax is simple:
//
//	tree ::= empty | `(' tree char tree `)'
//
// where the ambiguity is resolved by declaring that a `(' is a tree if we're
// expecting a tree.
func ParseTree(s string) *Node {
	var parse func(int) (*Node, int)
	n := len(s)
	i := 0
	parse = func(i int) (*Node, int) {
		if i < n && s[i] == '(' {
			left, i := parse(i + 1)
			if i >= n { bail("no data") }
			data := s[i]
			right, i := parse(i + 1)
			if i >= n || s[i] != ')' { bail("missing )") }
			return &Node { data, left, right }, i + 1
		}
		return nil, i
	}
	t, i := parse(0)
	if i < n { bail("trailing junk") }
	return t
}

///--------------------------------------------------------------------------
/// Main program.

func main() {
	switch len(os.Args) {
	case 2:
		t := ParseTree(os.Args[1])
		i := MakeIterator(t)
		for {
			item, winp := i.Next()
			if !winp { break }
			fmt.Printf("%c", item)
		}
		fmt.Printf("\n")
	case 3:
		ia := MakeIterator(ParseTree(os.Args[1]))
		ib := MakeIterator(ParseTree(os.Args[2]))
		if SameIterators(ia, ib) {
			io.WriteString(os.Stdout, "match\n")
		} else {
			io.WriteString(os.Stdout, "no match\n")
		}
	default:
		bail("bad args")
	}
}

///----- That's all, folks --------------------------------------------------