Go数据结构与算法04-栈上: 如何实现一个计算器
序
- Go 数据结构与算法系列文章,本系列文章主要会包括常见的数据结构与算法实现,同时会包括 Go 标准库代码的分析理解,讲到对应章节的时候优先学习分析 Go 的源码实现,例如 slice、list、sort 等,然后可能会有一些常见的案例实现,同时这也是 极客时间-数据结构与算法之美 的课程笔记
- 本文代码仓库: https://github.com/mohuishou/go-algorithm 🌟🌟🌟🌟🌟
- RoadMap: 持续更新中,预计一周更新 1 ~ 2 篇文章,预计到 202101 月底前更新完成
- 获取更新: Github、知乎、RSS、开发者头条
- 上一个系列刚刚完成了 Go 设计模式,如果感兴趣也可以进行查看
栈
定义
栈是一种“操作受限”的线性表,后进者先出,先进者后出。
比较典型的例子就是我们在叠盘子的时候,叠的时候从下到上一个一个磊起来,取的时候,再从上到下一个一个的拿出来。
说到先入后出这种特性,在 Go 中你第一时间想到了什么?不知道是否和我的答案一样, defer
实现
存在两种实现方式,第一种是数组实现的顺序栈,第二种是链表链式栈
数组实现
数组实现我们直接使用了 slice
,并且借助 slice
实现了自动扩容
// 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
}
链表实现
链式栈的实现我们利用双向循环链表,简化栈的插入操作
// 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的一种解法,并且我们这个实现更加复杂,原题只需要计算加减法
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()
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!