Leet code string decode problems

evaluate.go

package main

import (
	"bytes"
	"container/list"
	"fmt"
	"strconv"
	"strings"
)

func reverse(input string) string {
	inputBytes := []byte(input)
	for i, j := 0, len(inputBytes)-1; i < j; i, j = i+1, j-1 {
		inputBytes[i], inputBytes[j] = inputBytes[j], inputBytes[i]
	}

	return string(inputBytes)
}

func evaluate(expr string) (string, error) {
	stack := list.New()
	repeatStack := list.New()
	var buf bytes.Buffer
	var repeat bytes.Buffer

	for i := 0; i < len(expr); i++ {
		switch expr[i] {
		case '[':
			repeats := repeat.String()
			numRepeats := 1
			if repeats != "" {
				repeat.Reset()
				n, err := strconv.ParseInt(repeats, 10, 32)
				if err != nil {
					return "", err
				}
				numRepeats = int(n)
			}
			repeatStack.PushFront(numRepeats)
			stack.PushFront(expr[i])
		case ']':
			openingParensFound := false
			var repeatBuf bytes.Buffer
			for stack.Len() > 0 {
				t := stack.Front()
				b := t.Value.(byte)
				stack.Remove(t)
				if b == '[' {
					openingParensFound = true
					break
				}
				repeatBuf.WriteByte(b)
			}
			if !openingParensFound {
				return "", fmt.Errorf("no opening parens found")
			}
			repeated := reverse(repeatBuf.String())
			if repeatStack.Len() > 0 {
				t := repeatStack.Front()
				numRepeats := t.Value.(int)
				repeatStack.Remove(t)
				repeated = strings.Repeat(repeated, numRepeats)
			}
			// if there are more parents to be popped out from the stack, push back result into the stack
			if stack.Len() > 0 {
				for i := 0; i < len(repeated); i++ {
					stack.PushFront(repeated[i])
				}
			} else {
				buf.WriteString(repeated)
			}
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			repeat.WriteByte(expr[i])
		default:
			if stack.Len() > 0 {
				repeats := repeat.String()
				if repeats != "" {
					// treat the digits as a literal
					for i := 0; i < len(repeats); i++ {
						stack.PushFront(repeats[i])
					}
					repeat.Reset()
				}
				stack.PushFront(expr[i])
			} else {
				repeats := repeat.String()
				if repeats != "" {
					// treat as a literal
					for i := 0; i < len(repeats); i++ {
						buf.WriteByte(repeats[i])
					}

					repeat.Reset()
				}
				buf.WriteByte(expr[i])
			}
		}
	}

	if stack.Len() > 0 {
		return "", fmt.Errorf("error evaluating input %s", expr)
	}

	return buf.String(), nil
}

func main() {
	testInputs := [][]string{
		{"z4[y]zzz2[abc]", "zyyyyzzzabcabc"},
		{"2[abc]3[cd]ef", "abcabccdcdcdef"},
		{"2[abc]3[3cd]ef", "abcabc3cd3cd3cdef"},
		{"2[abc]2[3[cd]]ef", "abcabccdcdcdcdcdcdef"},
		{"[abc]2[10[c]]ef", "abcccccccccccccccccccccef"},
		{"[abc]2[10[c]2[a]]ef", "abcccccccccccaaccccccccccaaef"},
		{"foo[bar]2[foo3[bar]]foo", "foobarfoobarbarbarfoobarbarbarfoo"},
		{"a2[b3[c]4[d]5[e]]f", "abcccddddeeeeebcccddddeeeeef"},
		{"a2[ba2[cd]ab]", "abacdcdabbacdcdab"},
		{"abc[2[a[abc]]]foo", "abcaabcaabcfoo"},
	}

	for i := range testInputs {
		input := testInputs[i][0]
		expected := testInputs[i][1]
		output, err := evaluate(input)
		if err != nil {
			panic(fmt.Sprintf("error %v evaluating input %s", err, input))
		}
		if output == expected {
			fmt.Println("evaluate input", input, "success.", "got expected", output)
		} else {
			fmt.Println("evaluate input", input, "failure. expected", expected, "got", output)
		}
	}
}

operator_tree.go

package main

import (
	"bytes"
	"container/list"
	"fmt"
	"strconv"
	"strings"
)

type Operation interface {
	Evaluate() string
	Command() string
}

type operationRepeat struct {
	repeats int
	buf     string
}

type operationBuffer struct {
	buf string
}

type operationStack struct {
	stack *list.List
}

type operationNode struct {
	repeats int
	buf     string
	nodes   *list.Element
}

func NewOperationStack() *operationStack {
	return &operationStack{stack: list.New()}
}

func (os *operationStack) Add(node interface{}) {
	os.stack.PushBack(node)
}

func (os *operationStack) Reduce(repeats int, buf string) {
	front := os.stack.Front()
	node := &operationNode{repeats: repeats, buf: buf, nodes: front}
	os.stack.Init()
	os.stack.PushFront(node)
}

func (os *operationStack) Command() string {
	// operation stack not reduced
	if os.stack.Len() != 1 {
		return ""
	}

	element := os.stack.Front()
	node := element.Value.(*operationNode)

	nodes := []*list.Element{}
	acc := ""
	var next *list.Element

	for n := node.nodes; n != nil; n = next {
		if v, ok := n.Value.(*operationNode); ok {
			// prepend
			nodes = append([]*list.Element{n}, nodes...)
			next = v.nodes

			continue
		}

		next = nil
		// we now accumulate the repeat nodes
		for r := n; r != nil; r = r.Next() {
			repeater := r.Value.(*operationRepeat)
			cmd := repeater.Command()
			if cmd == "" {
				continue
			}
			if acc == "" {
				acc += cmd
			} else {
				acc += " + " + cmd
			}
		}

		break
	}

	// process the execution stack and apply the repeater commands in reverse order
	for _, n := range nodes {
		v := n.Value.(*operationNode)
		if v.buf != "" {
			if acc != "" {
				acc = fmt.Sprintf("%d x (%s + \"%s\")", v.repeats, acc, v.buf)
			} else {
				acc = fmt.Sprintf("%d x (%s)", v.repeats, v.buf)
			}
		} else {
			acc = fmt.Sprintf("%d x (%s)", v.repeats, acc)
		}
	}

	if node.buf != "" {
		if acc != "" {
			acc = fmt.Sprintf("%d x (%s + \"%s\")", node.repeats, acc, node.buf)
		} else {
			acc = fmt.Sprintf("%d x (%s)", node.repeats, node.buf)
		}
	} else {
		acc = fmt.Sprintf("%d x (%s)", node.repeats, acc)
	}

	return acc
}

func (os *operationStack) Evaluate() string {
	// operation stack not reduced
	if os.stack.Len() != 1 {
		return ""
	}

	element := os.stack.Front()
	node := element.Value.(*operationNode)

	nodes := []*list.Element{}
	acc := ""
	var next *list.Element

	for n := node.nodes; n != nil; n = next {
		if v, ok := n.Value.(*operationNode); ok {
			nodes = append([]*list.Element{n}, nodes...)
			next = v.nodes

			continue
		}

		next = nil

		// we now accumulate the repeat nodes
		for r := n; r != nil; r = r.Next() {
			repeater := r.Value.(*operationRepeat)
			acc += repeater.Evaluate()
		}

		break
	}

	// process the execution stack and apply the repeaters in reverse order
	for _, n := range nodes {
		v := n.Value.(*operationNode)
		acc += v.buf
		acc = strings.Repeat(acc, v.repeats)
	}

	acc += node.buf

	return strings.Repeat(acc, node.repeats)
}

func (r *operationRepeat) Command() string {
	return fmt.Sprintf("(%d x %s)", r.repeats, r.buf)
}

func (r *operationRepeat) Evaluate() string {
	return strings.Repeat(r.buf, r.repeats)
}

func (b *operationBuffer) Evaluate() string {
	return b.buf
}

func (b *operationBuffer) Command() string {
	return "Buffer " + b.buf
}

func toOperations(expr string) ([]Operation, error) {
	stack := list.New()
	repeatStack := list.New()

	var buf bytes.Buffer
	var repeat bytes.Buffer
	var operations []Operation
	var contextPushed bool
	opstack := NewOperationStack()

	for i := 0; i < len(expr); i++ {
		switch expr[i] {
		case '[':
			contextPushed = true
			if stack.Len() == 0 {
				s := buf.String()
				if s != "" {
					operations = append(operations, &operationBuffer{buf: s})
					buf.Reset()
				}
			} else {
				s := buf.String()
				if s != "" {
					repeatOp := operationRepeat{repeats: 1, buf: s}
					opstack.Add(&repeatOp)
					buf.Reset()
				}
			}
			repeats := repeat.String()
			numRepeats := 1
			if repeats != "" {
				repeat.Reset()
				n, err := strconv.ParseInt(repeats, 10, 32)
				if err != nil {
					return nil, err
				}
				numRepeats = int(n)
			}
			repeatStack.PushFront(numRepeats)
			stack.PushFront(expr[i])
		case ']':
			if stack.Len() == 0 {
				return nil, fmt.Errorf("no opening parens found")
			}
			t := stack.Front()
			stack.Remove(t)

			numRepeats := 1
			if repeatStack.Len() > 0 {
				t := repeatStack.Front()
				numRepeats = t.Value.(int)
				repeatStack.Remove(t)
			}
			if stack.Len() == 0 || !contextPushed {
				//reduce
				opstack.Reduce(numRepeats, buf.String())
			} else {
				// shift
				repeatOp := operationRepeat{repeats: numRepeats, buf: buf.String()}
				opstack.Add(&repeatOp)
			}
			buf.Reset()
			contextPushed = false
			if stack.Len() == 0 {
				operations = append(operations, opstack)
				opstack = NewOperationStack()
			}
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			repeat.WriteByte(expr[i])
		default:
			repeats := repeat.String()
			if repeats != "" {
				// treat as a literal
				for i := 0; i < len(repeats); i++ {
					buf.WriteByte(repeats[i])
				}

				repeat.Reset()
			}
			buf.WriteByte(expr[i])
		}
	}

	if stack.Len() > 0 {
		return nil, fmt.Errorf("error evaluating input %s", expr)
	}

	s := buf.String()
	if s != "" {
		operations = append(operations, &operationBuffer{buf: s})
	}

	return operations, nil
}

func main() {
	testInputs := [][]string{
		{"z4[y]zzz2[abc]", "zyyyyzzzabcabc"},
		{"2[abc]3[cd]ef", "abcabccdcdcdef"},
		{"2[abc]3[3cd]ef", "abcabc3cd3cd3cdef"},
		{"2[abc]2[3[cd]]ef", "abcabccdcdcdcdcdcdef"},
		{"[abc]2[10[c]]ef", "abcccccccccccccccccccccef"},
		{"[abc]2[10[c]2[a]]ef", "abcccccccccccaaccccccccccaaef"},
		{"foo[bar]2[foo3[bar]]foo", "foobarfoobarbarbarfoobarbarbarfoo"},
		{"a2[b3[c]4[d]5[e]]f", "abcccddddeeeeebcccddddeeeeef"},
		{"a2[ba2[cd]ab]", "abacdcdabbacdcdab"},
		{"abc[2[a[abc]]]foo", "abcaabcaabcfoo"},
	}

	for i := range testInputs {
		input := testInputs[i][0]
		expected := testInputs[i][1]
		ops, err := toOperations(input)
		if err != nil {
			panic(fmt.Sprintf("error %v evaluating input %s", err, input))
		}
		fmt.Println("evaluating", input)
		commands := make([]string, len(ops))
		output := ""
		for i, op := range ops {
			commands[i] = op.Command()
			output += op.Evaluate()
		}
		fmt.Println(strings.Join(commands, ","))
		if output == expected {
			fmt.Println("evaluate input", input, "success.", "got expected", output)
		} else {
			fmt.Println("evaluate input", input, "failure. expected", expected, "got", output)
		}
	}
}