lsyf / lsyf.github.io Goto Github PK

package tree

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

type node struct {
	left, right *node
	Value       int
}

type BiTree struct {
	root *node
	len  int
}

func NewBiTree() *BiTree {
	return &BiTree{}
}

func (t *BiTree) Add(v int) {
	n := t.root
	if n == nil {
		t.root = &node{Value: v}
		t.len++
		return
	}
	for {
		switch {
		case v < n.Value:
			if n.left == nil {
				new := &node{Value: v}
				n.left = new
				t.len++
				return
			}
			n = n.left
		default:
			if n.right == nil {
				new := &node{Value: v}
				n.right = new
				t.len++
				return
			}
			n = n.right
		}
	}

}

func (t *BiTree) Delete(v int) *node {
	p, n := find(t.root, v)

	switch {
	case n == nil:
		return nil
	case n.left == nil || n.right == nil:
		a := If(n.left == nil, n.right, n.left)
		replace(p, n, a)
		return n
	default:
		maxP, max := findMax(n.left)
		replace(maxP, max, nil)
		if n != t.root {
			replace(p, n, max)
		} else {
			t.root = max
		}
		if n.left != max {
			max.left = n.left
		}
		max.right = n.right
		return n
	}
}

func replace(p, a, b *node) {
	switch {
	case p == nil:
		return
	case p.left == a:
		p.left = b
	default:
		p.right = b
	}
}

func If(condition bool, v1, v2 *node) *node {
	if condition {
		return v1
	}
	return v2
}

func findMax(root *node) (p, n *node) {
	n = root
	for {
		switch {
		case n == nil:
			return nil, nil
		case n.right == nil:
			return p, n
		default:
			p = n
			n = n.right
		}
	}
}
func find(root *node, v int) (p, n *node) {
	n = root
	for {
		switch {
		case n == nil:
			return nil, nil
		case v == n.Value:
			return p, n
		case v < n.Value:
			p = n
			n = n.left
			continue
		default:
			p = n
			n = n.right
			continue
		}
	}

}

func (t *BiTree) Search(v int) *node {
	_, n := find(t.root, v)
	return n
}

func (t *BiTree) Print(a int) string {

	if t.root == nil {
		return ""
	}
	data := make([]string, 0, t.len)
	s := &stack{list.New()}
	switch a {
	case 10:
		n := t.root
		m := make(map[*node]bool)
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			if n == nil {
				continue
			}
			if m[n] { //由于每个节点都会入栈两次，第一次标记，第二次打印值
				data = append(data, strconv.Itoa(n.Value))
			} else {
				s.push(n.right)
				s.push(n.left)
				s.push(n)
				m[n] = true
			}
		}
	case 20:
		n := t.root
		m := make(map[*node]bool)
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			if n == nil {
				continue
			}
			if m[n] {
				data = append(data, strconv.Itoa(n.Value))
			} else {
				s.push(n.right)
				s.push(n)
				s.push(n.left)
				m[n] = true
			}
		}
	case 30:
		n := t.root
		m := make(map[*node]bool)
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			if n == nil {
				continue
			}
			if m[n] {
				data = append(data, strconv.Itoa(n.Value))
			} else {
				s.push(n)
				s.push(n.right)
				s.push(n.left)
				m[n] = true
			}
		}

	case 11:
		//先序遍历方案1：
		//对每个节点压入栈，打印值，同样处理左孩子；
		//到达左下角后，栈弹出节点处理右孩子

		n := t.root
		for !s.empty() || n != nil { //如果栈为空并且节点为空，代表没有节点能够处理
			if n != nil { //节点不为空的话处理左孩子
				data = append(data, strconv.Itoa(n.Value))
				s.push(n)
				n = n.left
			} else { //节点为空的话 弹出栈顶节点，处理其右孩子
				n = s.pop().right
			}
		}
	case 12:
		//先序遍历方案2：
		//按照栈先入后出结构，对每个节点打印值，先压入右孩子，再压入左孩子
		//栈弹出各个节点依次处理

		n := t.root
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			data = append(data, strconv.Itoa(n.Value))
			if n.right != nil {
				s.push(n.right)
			}
			if n.left != nil {
				s.push(n.left)
			}
		}
	case 21:
		//中序遍历方案1：
		//对每个节点压入栈，同样处理左孩子；
		//到达左下角后，栈弹出节点，打印值，处理右孩子
		n := t.root
		for !s.empty() || n != nil {
			if n != nil {
				s.push(n)
				n = n.left
			} else {
				n = s.pop()
				data = append(data, strconv.Itoa(n.Value))
				n = n.right
			}
		}
	case 31:
		//后序遍历方案1：
		// 左右根 翻转是 根右左
		//按照栈先入后出结构，对每个节点打印值，先压入左孩子，再压入右孩子
		//栈弹出各个节点依次处理
		//最后翻转
		n := t.root
		s.push(t.root)
		for !s.empty() {
			n = s.pop()
			data = append(data, strconv.Itoa(n.Value))
			if n.left != nil {
				s.push(n.left)
			}
			if n.right != nil {
				s.push(n.right)
			}
		}
		for i, j := 0, len(data)-1; i < j; i, j = i+1, j-1 {
			data[i], data[j] = data[j], data[i]
		}

	case 4:
		n := t.root
		s.push(t.root)
		q := &queue{list.New()}
		q.put(t.root)
		for !q.empty() {
			n = q.poll()
			if n == nil {
				continue
			}
			data = append(data, strconv.Itoa(n.Value))
			q.put(n.left)
			q.put(n.right)
		}
	}
	return strings.Join(data, ",")
}

type stack struct {
	list *list.List
}

func (s *stack) push(v *node) {
	s.list.PushBack(v)
}

func (s *stack) empty() bool {
	return s.list.Len() == 0
}
func (s *stack) pop() *node {
	e := s.list.Back()
	if e != nil {
		s.list.Remove(e)
		return e.Value.(*node)
	}
	return nil
}

type queue struct {
	list *list.List
}

func (s *queue) put(v *node) {
	s.list.PushBack(v)
}

func (s *queue) empty() bool {
	return s.list.Len() == 0
}
func (s *queue) poll() *node {
	e := s.list.Front()
	if e != nil {
		s.list.Remove(e)
		return e.Value.(*node)
	}
	return nil
}

package main

import (
	"container/list"
	"fmt"
	"strconv"
	"unicode"
)

func main() {
	fmt.Println(cacl("1+22*3"))
}

func cacl(expr string) int {
	stack := &stack{list.New()}
	expr = in2post(expr)
	for i := 0; i < len(expr); i++ {
		s := string(expr[i])
		// 数字：直接压栈
		if unicode.IsDigit(rune(expr[i])) {
			j := i
			num := ""
			for ; j < len(expr) && unicode.IsDigit(rune(expr[j])); j++ { //获取整个数字
				num += string(expr[j])
			}
			stack.push(num)
			i = j //数字后都会跟有逗号，则跳过j-1
		} else {
			// 操作符：取出两个数字计算值，再将结果压栈
			num1, _ := strconv.Atoi(stack.pop())
			num2, _ := strconv.Atoi(stack.pop())
			switch s {
			case "+":
				stack.push(strconv.Itoa(num1 + num2))
			case "-":
				stack.push(strconv.Itoa(num1 - num2))
			case "*":
				stack.push(strconv.Itoa(num1 * num2))
			case "/":
				stack.push(strconv.Itoa(num1 / num2))
			}
		}
	}
	result, _ := strconv.Atoi(stack.top())
	return result
}

func in2post(expr string) (str string) {
	stack := stack{list.New()}
	for i := 0; i < len(expr); i++ {
		s := string(expr[i])
		switch s {
		case " ":
		case "(": //直接入栈
			stack.push(s)
		case ")": //弹出所有运算符，直至(
			for !stack.empty() {
				s = stack.pop()
				if s == "(" {
					break
				}
				str += s
			}
		case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9": //数字直接输出
			j := i
			num := ""
			for ; j < len(expr) && unicode.IsDigit(rune(expr[j])); j++ { //获取整个数字
				num += string(expr[j])
			}
			str = str + num + ","
			i = j - 1
		default: //运算符：遇到更高级别运算符则弹出
			for !stack.empty() {
				top := stack.top()
				if top == "(" || isLower(top, s) {
					break
				}
				str += top
				stack.pop()
			}
			// 低优先级的运算符入栈
			stack.push(s)
		}
	}
	// 栈不空则全部输出
	for !stack.empty() {
		str += stack.pop()
	}

	return str
}

func isLower(top string, newTop string) bool {
	// 注意 a + b + c 的后缀表达式是 ab + c +，不是 abc + +
	switch top {
	case "+", "-":
		if newTop == "*" || newTop == "/" {
			return true
		}
	case "(":
		return true
	}
	return false
}

type stack struct {
	list *list.List
}

func (s *stack) push(v string) {
	s.list.PushBack(v)
}

func (s *stack) empty() bool {
	return s.list.Len() == 0
}
func (s *stack) top() string {
	return s.list.Back().Value.(string)
}

func (s *stack) pop() string {
	e := s.list.Back()
	if e != nil {
		s.list.Remove(e)
		return e.Value.(string)
	}
	return ""
}

package list

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

type Queue struct {
	list *list.List
}

func NewQueue() *Queue {
	list := list.New()
	return &Queue{list}
}

func (q *Queue) Put(v interface{}) {
	q.list.PushBack(v)
}

func (q *Queue) Poll() interface{} {
	e := q.list.Front()
	if e != nil {
		q.list.Remove(e)
		return e.Value
	}
	return nil
}

func (q *Queue) Len() int {
	return q.list.Len()
}

func (q *Queue) String() (str string) {
	data := make([]string, 0, q.Len())
	for e := q.list.Front(); e != nil; e = e.Next() {
		data = append(data, fmt.Sprintf("%v", e.Value))
	}

	str = strings.Join(data, ",")
	str = "[" + str + "]"
	return
}

package list

import (
	"fmt"
	"strings"
)

type Node struct {
	next, pre *Node
	Value     interface{}
}

type LinkedList struct {
	root, tail *Node
	len        int
}

func NewLinkedList() *LinkedList {
	l := new(LinkedList)
	return l
}

func (l *LinkedList) Add(v interface{}) {
	if l.root == nil {
		l.root = &Node{Value: v}
		l.tail = l.root
		l.len++
		return
	}

	n := &Node{Value: v}
	n.pre = l.tail
	l.tail.next = n
	l.tail = n
	l.len++
}

func (l *LinkedList) Get(i int) interface{} {
	if i < 0 || i >= l.len {
		return nil
	}

	switch {
	case i == 0:
		return l.root.Value
	case i == l.len-1:
		return l.tail.Value
	case i < l.len/2: //下标小于长度1/2从头结点遍历
		n := l.root
		for x := 0; x < i-1; x++ {
			n = n.next
		}
		return n.Value
	default: //下标大于长度1/2从尾结点遍历
		n := l.tail
		for x := 0; x < l.len-1-i; x++ {
			n = n.pre
		}
		return n.Value
	}
}

func (l *LinkedList) Remove(i int) interface{} {
	if i < 0 || i >= l.len {
		return nil
	}

	switch {
	case l.len == 1: //长度为1代表只有头结点可删除
		n := l.root
		l.root = nil
		l.tail = nil
		l.len--
		return n.Value
	case i == 0:
		n := l.root
		l.root = l.root.next
		l.root.pre = nil
		l.len--
		return n.Value
	case i == l.len-1:
		n := l.tail
		l.tail = l.tail.pre
		l.tail.next = nil
		l.len--
		return n.Value
	case i < l.len/2: //下标小于长度1/2从头结点遍历
		n := l.root
		for x := 0; x < i-1; x++ {
			n = n.next
		}
		n.pre.next = n.next
		n.next.pre = n.pre
		l.len--
		return n.Value
	default: //下标大于长度1/2从尾结点遍历
		n := l.tail
		for x := 0; x < l.len-1-i; x++ {
			n = n.pre
		}
		n.pre.next = n.next
		n.next.pre = n.pre
		l.len--
		return n.Value
	}
}

func (l *LinkedList) Clear() {
	l.root = nil
	l.tail = nil
	l.len = 0
}
func (l *LinkedList) Contains(v interface{}) bool {
	n := l.root
	for n != nil {
		if n.Value == v {
			return true
		}
		n = n.next
	}
	return false
}

func (l *LinkedList) String() (str string) {
	data := make([]string, 0, l.len)
	n := l.root
	for n != nil {
		data = append(data, fmt.Sprintf("%v", n.Value))
		n = n.next
	}
	str = strings.Join(data, ",")
	str = "[" + str + "]"
	return
}

package list

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

type Stack struct {
	list *list.List
}

func NewStack() *Stack {
	list := list.New()
	return &Stack{list}
}

func (stack *Stack) Push(value interface{}) {
	stack.list.PushBack(value)
}

func (stack *Stack) Pop() interface{} {
	e := stack.list.Back()
	if e != nil {
		stack.list.Remove(e)
		return e.Value
	}
	return nil
}

func (stack *Stack) Peak() interface{} {
	e := stack.list.Back()
	if e != nil {
		return e.Value
	}
	return nil
}

func (stack *Stack) Len() int {
	return stack.list.Len()
}

func (stack *Stack) String() (str string) {
	data := make([]string, 0, stack.Len())
	for e := stack.list.Front(); e != nil; e = e.Next() {
		data = append(data, fmt.Sprintf("%v", e.Value))
	}

	str = strings.Join(data, ",")
	str = "[" + str + "]"
	return
}