漫画：用 Bitmap 与 AST 做一个配置化时长系统

“

本文通过编故事的方式讲解bitmap&AST的一个应用场景。这个故事发生在一个网络游戏公司里面，主要登场人物

左边：导师，名字不重要

右边：实习生，三多

三多在一家游戏公司做实习生，一天下午他正在划水，被导师叫了过去：

三多心里骂娘，但是一想到自己下个月又得交房租了，还是满含泪水打开了需求文档，需求文档大概的意思如下：

三多开始一边薅头发，一边设计系统，干到晚上12点，搞出了第一版系统架构图：

其中DB表的schema为：

于是三多第二天给导师看设计：

于是三多重新设计了技术方案：

三多把技术方案设计好后，就开始写代码，然后项目上线，一切顺利，直到几天后...

三多导师随便抄起家伙画了个图然后丢给三多让他去实现：

于是三多实现了这套时长系统，由于系统能力非常灵活，老板让PM配置了一些非常复杂的时长表达式，被玩家们赐予了亲切的称号：耍猴公司~

下面这段代码是个AST的最小demo，有兴趣的读者可以看看：

package main

import (
 "fmt"
 "reflect"
 "strconv"
 "strings"
)

const (
 Number   = 0
 Operator = 1
)

type Node struct {
 Type  int
 Value string
 Left  *Node
 Right *Node
}

// input: 1 + 4 - 2
// result:
//     -
//        /   \
//     +  2
//      /   \
//    1  4
func getAst(expr string) *Node {

 operator := make(map[string]int)
 operator["+"] = Operator
 operator["-"] = Operator

 nodeList := make([]Node, 0)
 var root *Node

 expr = strings.Trim(expr, " ")
 words := strings.Split(expr, " ")
 for _, word := range words {

  var node Node

  if _, ok := operator[word]; ok {
   node.Type = Operator
  } else {
   node.Type = Number
  }
  node.Value = word
  nodeList = append(nodeList, node)
 }

 for i := 0; i < len(nodeList); i++ {
  if root == nil {
   root = &nodeList[i]
   continue
  }

  switch nodeList[i].Type {
  case Operator:
   nodeList[i].Left = root
   root = &nodeList[i]
  case Number:
   root.Right = &nodeList[i]
  }
 }

 return root
}

func getResult(node *Node) string {
 switch node.Type {
 case Number:
  return node.Value
 case Operator:
  return calc(getResult(node.Left), getResult(node.Right), node.Value)
 }
 return ""
}

func calc(left, right string, operator string) string {
 leftVal, _ := TransToInt(left)
 rightVal, _ := TransToInt(right)
 val := 0
 switch operator {
 case "+":
  val = leftVal + rightVal
 case "-":
  val = leftVal - rightVal
 }
 return TransToString(val)
}


func main() {
 expr := `1 + 4 - 2 + 100 - 20 + 12 `
 //expr := ` 1 + 4 `

 ast := getAst(expr)
 result := getResult(ast)

 fmt.Println(result)
}

func TransToString(data interface{}) (res string) {
 val := reflect.ValueOf(data)
 return strconv.FormatInt(val.Int(), 10)
}

func TransToInt(data interface{}) (res int, err error) {
 return strconv.Atoi(strings.TrimSpace(data.(string)))
}

推荐阅读

• 漫画：不一样的链表成环检测，Go 语言实现