Go数据结构与算法04-栈上: 如何实现一个计算器

序

  • Go 数据结构与算法系列文章，本系列文章主要会包括常见的数据结构与算法实现，同时会包括 Go 标准库代码的分析理解，讲到对应章节的时候优先学习分析 Go 的源码实现，例如 slice、list、sort 等，然后可能会有一些常见的案例实现，同时这也是 极客时间-数据结构与算法之美 的课程笔记
  • 本文代码仓库: https://github.com/mohuishou/go-algorithm 🌟🌟🌟🌟🌟
  • RoadMap: 持续更新中，预计一周更新 1 ~ 2 篇文章，预计到 202101 月底前更新完成
  • 获取更新: Github、知乎、RSS、开发者头条
  • 上一个系列刚刚完成了 Go 设计模式，如果感兴趣也可以进行查看

栈

定义

栈是一种“操作受限”的线性表，后进者先出，先进者后出。
比较典型的例子就是我们在叠盘子的时候，叠的时候从下到上一个一个磊起来，取的时候，再从上到下一个一个的拿出来。
说到先入后出这种特性，在 Go 中你第一时间想到了什么？不知道是否和我的答案一样， defer
01_stack.drawio.svg

实现

存在两种实现方式，第一种是数组实现的顺序栈，第二种是链表链式栈

数组实现

数组实现我们直接使用了 slice ，并且借助 slice 实现了自动扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Stack Stack
type Stack struct {
	items   []string
	current int
}

// NewStack NewStack
func NewStack() *Stack {
	return &Stack{
		items:   make([]string, 10),
		current: 0,
	}
}

// Push 入栈
func (s *Stack) Push(item string) {
	s.current++
	// 判断底层 slice 是否满了，如果满了就 append
	if s.current == len(s.items) {
		s.items = append(s.items, item)
		return
	}
	s.items[s.current] = item
}

// Pop 出栈
func (s *Stack) Pop() string {
	if s.current == 0 {
		return ""
	}
	item := s.items[s.current]
	s.current--
	return item
}

链表实现

链式栈的实现我们利用双向循环链表，简化栈的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// node 节点
type node struct {
	prev, next *node
	value      string
}

// Stack 链式栈
type Stack struct {
	root *node
	len  int
}

// NewStack NewStack
func NewStack() *Stack {
	n := &node{}
	n.next = n
	n.prev = n
	return &Stack{root: n}
}

// Push 入栈
func (s *Stack) Push(item string) {
	n := &node{value: item}
	s.root.prev.next = n
	n.prev = s.root.prev
	n.next = s.root
	s.root.prev = n
	s.len++
}

// Pop 出栈
func (s *Stack) Pop() string {
	item := s.root.prev
	if item == s.root {
		return ""
	}

	s.root.prev = item.prev
	item.prev.next = s.root
	// 避免内存泄漏
	item.prev = nil
	item.next = nil
	s.len--
	return item.value
}

典型问题

实现一个计算器

我们实现了支持+、-、*、/、(、) 的计算器，这也是leetcode#244的一种解法，并且我们这个实现更加复杂，原题只需要计算加减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package calculation

import (
	"fmt"
	"strconv"
)

// 操作符的优先级
var operatorPriority = map[string]int{
	"+": 0,
	"-": 0,
	"*": 1,
	"/": 1,
	"(": 2,
	")": 2,
}

// Calculator 计算器
type Calculator struct {
	nums      *StackInt
	operators *Stack
	exp       string
}

// NewCalculator NewCalculator
func NewCalculator(exp string) *Calculator {
	return &Calculator{
		nums:      NewStackInt(),
		operators: NewStack(),
		exp:       exp,
	}
}

// Calculate 获取计算结果
func (c *Calculator) Calculate() int {
	l := len(c.exp)
	for i := 0; i < l; i++ {
		switch e := (c.exp[i]); e {
		case ' ':
			continue
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			// 一直往后获取数字，如果下一个还是数字说明这一个数还不完整
			j := i
			for j < l && c.exp[j] <= '9' && c.exp[j] >= '0' {
				j++
			}
			n, _ := strconv.Atoi(c.exp[i:j])
			i = j - 1
			c.nums.Push(n)
		case '+', '-', '*', '/':
			// 从计算符栈中获取栈顶元素，如果当前操作符的优先级低于栈顶元素的优先级
			// 并且栈顶元素不为空，和括号
			// 那么从数据栈中取两个数据和栈顶操作符进行计算
			pre := c.operators.Pop()
			for pre != "" && pre != "(" && operatorPriority[string(e)] <= operatorPriority[pre] {
				c.nums.Push(c.calc(pre))
				pre = c.operators.Pop()
			}
			if pre != "" {
				c.operators.Push(pre)
			}
			c.operators.Push(string(e))
		case '(':
			c.operators.Push(string(e))
		case ')':
			// 碰到右括号之后就一直不断操作符栈中弹出元素，并且取两个数据进行计算
			// 直到碰到左括号为止
			for o := c.operators.Pop(); o != "(" && o != ""; o = c.operators.Pop() {
				c.nums.Push(c.calc(o))
			}
		default:
			panic("invalid exp")
		}
	}
	// 最后如果不存在操作符，说明数据栈中的栈顶元素就是最后结果
	o := c.operators.Pop()
	if o == "" {
		return c.nums.Pop()
	}
	// 如果存在，就把最后的数据进行计算后返回
	return c.calc(o)
}

// calc 单次计算操作，o: 计算符
func (c *Calculator) calc(o string) int {
	b := c.nums.Pop()
	a := c.nums.Pop()

	fmt.Printf("%d %s %d\n", a, o, b)

	switch o {
	case "+":
		return a + b
	case "-":
		return a - b
	case "*":
		return a * b
	case "/":
		return a / b
	}

	return 0
}

// calculate 计算器，支持加减乘除
func calculate(s string) int {
	return NewCalculator(s).Calculate()
}