缘起

最近阅读<<自制编程语言>>一书
开头一章便是教读者使用lex/yacc工具
制作四则运算器
其中yacc的移进/归约的思想很有启发
于是使用golang练习之

目标

  • 制作一个四则运算器, 从os.Stdin读入一行表达式, 然后输出计算过程和结果
  • 支持+ - * /
  • 支持左右括号
  • 支持负数

难点

  • 记号扫描(lexer)
    • 逐字符扫描记号
    • 单字符记号可直接识别, + - * / ( )
    • 多字符记号, 此处只有浮点数, 通过有限状态的转换进行识别
      • + ‘-‘ = INT_STATUS
      • + ‘\d’ = INT_STATUS
      • + ‘.’ = DOT_STATUS
      • + ‘SPACE | + | - | * | / | ( | )’ = INITIAL
      • + ‘\d’ = FRAG_STATUS
      • + ‘SPACE | + | - | * | / | ( | )’ = INITIAL
  • 运算优先级
      • /优先级最高, 可以立即归约计算
    • 括号次之, 遇到右括号, 应当触发+ -归约
    • 程序末尾, 没有新的记号剩余, 对+ -进行归约
  • 识别负数
    • 简单起见, 本程序总是使用浮点数作为基本计算单位
    • 把负号识别为浮点数的可选部分: 浮点数 = -?\d+(.\d+)?

总体流程

  • 从os.Stdin读入一行表达式字符串
  • 逐字符扫描记号流, 放入记号队列
  • 逐记号出队, 置入计算栈
  • 判断栈顶是否符合归约条件, 是则进行计算
  • 记号队列空, 对计算栈进行最终计算
  • 输出结果

main.go

从os.Stdin循环读入行
调用lexer.Parse获得记号流
调用parser.Parse进行计算

  1. func main() {
  2.     reader := bufio.NewReader(os.Stdin)
  4.     for {
  5.         fmt.Printf("=> ")
  6.         arrBytes, _, err := reader.ReadLine()
  7.         if err != nil {
  8.             panic(err.Error())
  9.         }
  10.         line := strings.TrimSpace(string(arrBytes))
  12.         expression := line
  13.         tokens, e := lexer.Parse(expression)
  14.         if e != nil {
  15.             println(e.Error())
  17.         } else {
  18.             e,v := parser.Parse(tokens)
  19.             if e != nil {
  20.                 println(e.Error())
  21.             }
  23.             fmt.Println(strconv.FormatFloat(v, 'f', 10, 64))
  24.         }
  25.     }
  26. }

tokens/tokens.go

定义记号

  1. package tokens
  3. type TOKENS string
  5. const IntLiteral TOKENS = "INT"
  6. const DoubleLiteral TOKENS = "DBL"
  7. const ADD TOKENS = "ADD"
  8. const SUB TOKENS = "SUB"
  9. const MUL TOKENS = "MUL"
  10. const DIV TOKENS = "DIV"
  11. const LB TOKENS = "LB"
  12. const RB TOKENS = "RB"
  13. const UNKNOWN TOKENS = "UNKNOWN"
  15. type Token struct {
  16.     Token TOKENS
  17.     Value string
  18.     Position int
  19. }
  23. func OfRune(t TOKENS, r rune, from int)  *Token {
  24.     return &Token {
  25.         Token: t,
  26.         Value : string(r),
  27.         Position: from,
  28.     }
  29. }
  31. func OfString(t TOKENS, s string, from int)  *Token {
  32.     return &Token {
  33.         Token: t,
  34.         Value : s,
  35.         Position: from,
  36.     }
  37. }

states/states.go

定义lexer的状态

  1. type STATES int
  3. const INITIAL STATES = 1
  4. const INT_STATUS STATES = 11
  5. const DOT_STATUS STATES = 12
  6. const FRAG_STATUS STATES = 13

lexer/lexer.go

记号扫描

  1. type tLexerState struct {
  2.     state states.STATES
  3.     tokens []*tokens.Token
  4.     buffer []rune
  5.     i0 int
  6.     i1 int
  7.     d0 int
  8.     d1 int
  9. }
  11. func (me *tLexerState) AppendToken(t *tokens.Token) {
  12.     me.tokens = append(me.tokens, t)
  13. }
  16. func (me *tLexerState) AppendChar(it rune) {
  17.     me.buffer = append(me.buffer, it)
  18. }
  20. func (me *tLexerState) BufferSize() int {
  21.     return len(me.buffer)
  22. }
  24. func (me *tLexerState) IntSize() int {
  25.     return me.i1 - me.i0 + 1
  26. }
  28. func (me *tLexerState) FragSize() int {
  29.     return me.d1 - me.d0 + 1
  30. }
  33. func Parse(line string) ([]*tokens.Token, error) {
  34.     var state = &(tLexerState{
  35.         state: states.INITIAL,
  36.         tokens: make([]*tokens.Token, 0),
  37.         buffer: make([]rune, 0),
  38.         i0 : 0,
  39.         i1 : 0,
  40.         d0: 0,
  41.         d1: 0,
  42.     })
  44.     for i, it := range line + "\n" {
  45.         e := parseChar(state, i, it)
  46.         if e != nil {
  47.             return nil, e
  48.         }
  49.     }
  51.     return state.tokens, nil
  52. }
  54. func parseChar(state *tLexerState, i int, it rune) error {
  55.     var e error = nil
  57.     switch state.state {
  58.     case states.INITIAL:
  59.         e = parseCharWhenInitial(state, i, it)
  60.         break
  62.     case states.INT_STATUS:
  63.         e = parseCharWhenInt(state, i, it)
  64.         break
  66.     case states.DOT_STATUS:
  67.         e = parseCharWhenDot(state, i, it)
  68.         break
  70.     case states.FRAG_STATUS:
  71.         e = parseCharWhenFrag(state, i, it)
  72.         break
  73.     }
  75.     return e
  76. }
  78. func parseCharWhenInitial(state *tLexerState, i int, it rune) error {
  79.     if is_minus(it) || is_0_to_9(it) {
  80.         state.state = states.INT_STATUS
  81.         state.buffer = make([]rune, 0)
  82.         state.buffer = append(state.buffer, it)
  83.         state.i0 = i
  84.         state.i1 = i
  86.     } else if is_space(it){
  87.         return nil
  89.     } else if is_add(it) {
  90.         state.AppendToken(tokens.OfRune(tokens.ADD, it, i))
  91.     } else if is_sub(it) {
  92.         state.AppendToken(tokens.OfRune(tokens.SUB, it, i))
  93.     } else if is_mul(it) {
  94.         state.AppendToken(tokens.OfRune(tokens.MUL, it, i))
  95.     } else if is_div(it) {
  96.         state.AppendToken(tokens.OfRune(tokens.DIV, it, i))
  97.     } else if is_lb(it) {
  98.         state.AppendToken(tokens.OfRune(tokens.LB, it, i))
  99.     }  else if is_rb(it) {
  100.         state.AppendToken(tokens.OfRune(tokens.RB, it, i))
  101.     } else {
  102.         return errors.New(fmt.Sprintf("parseCharWhenInitial, invalid char %c at %d", it, i))
  103.     }
  105.     return nil
  106. }
  109. func parseCharWhenInt(state *tLexerState, i int, it rune) error {
  110.     if is_0_to_9(it) {
  111.         if state.BufferSize() >= 10 {
  112.             return errors.New(fmt.Sprintf("too large int number at %v", i))
  113.         } else {
  114.             state.AppendChar(it)
  115.             state.i1 = i
  116.         }
  117.     } else if is_dot(it) {
  118.         state.AppendChar(it)
  119.         state.state = states.DOT_STATUS
  121.     } else if is_space(it) {
  122.         state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
  123.         state.state = states.INITIAL
  125.     } else if is_rb(it) {
  126.         state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
  127.         state.AppendToken(tokens.OfRune(tokens.RB, it, i))
  128.         state.state = states.INITIAL
  130.     }  else if is_add(it) {
  131.         state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
  132.         state.AppendToken(tokens.OfRune(tokens.ADD, it, i))
  133.         state.state = states.INITIAL
  135.     } else if is_sub(it) {
  136.         state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
  137.         state.AppendToken(tokens.OfRune(tokens.SUB, it, i))
  138.         state.state = states.INITIAL
  140.     } else if is_mul(it) {
  141.         state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
  142.         state.AppendToken(tokens.OfRune(tokens.MUL, it, i))
  143.         state.state = states.INITIAL
  145.     } else if is_div(it) {
  146.         state.AppendToken(tokens.OfString(tokens.IntLiteral, string(state.buffer), state.i1))
  147.         state.AppendToken(tokens.OfRune(tokens.DIV, it, i))
  148.         state.state = states.INITIAL
  150.     } else {
  151.         return errors.New(fmt.Sprintf("parseCharWhenInt, invalid char %c at %d", it, i))
  152.     }
  154.     return nil
  155. }
  158. func parseCharWhenDot(state *tLexerState, i int, it rune) error {
  159.     if is_0_to_9(it) {
  160.         state.state = states.FRAG_STATUS
  161.         state.AppendChar(it)
  162.         state.d0 = i
  163.         state.d1 = i
  164.     } else {
  165.         return errors.New(fmt.Sprintf("parseCharWhenDot, invalid char %c at %d", it, i))
  166.     }
  168.     return nil
  169. }
  172. func parseCharWhenFrag(state *tLexerState, i int, it rune) error {
  173.     if is_0_to_9(it) {
  174.         if state.FragSize() >= 10 {
  175.             return errors.New(fmt.Sprintf("too many chars for a double value at %d", i))
  176.         } else {
  177.             state.AppendChar(it)
  178.             state.d1 = i
  179.         }
  180.     } else if is_space(it) {
  181.         state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
  182.         state.state = states.INITIAL
  184.     } else if is_add(it) {
  185.         state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
  186.         state.AppendToken(tokens.OfRune(tokens.ADD, it, i))
  187.         state.state = states.INITIAL
  189.     } else if is_sub(it) {
  190.         state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
  191.         state.AppendToken(tokens.OfRune(tokens.SUB, it, i))
  192.         state.state = states.INITIAL
  194.     } else if is_mul(it) {
  195.         state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
  196.         state.AppendToken(tokens.OfRune(tokens.MUL, it, i))
  197.         state.state = states.INITIAL
  199.     } else if is_div(it) {
  200.         state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
  201.         state.AppendToken(tokens.OfRune(tokens.DIV, it, i))
  202.         state.state = states.INITIAL
  204.     } else if is_rb(it) {
  205.         state.AppendToken(tokens.OfString(tokens.DoubleLiteral, string(state.buffer), state.i1))
  206.         state.AppendToken(tokens.OfRune(tokens.RB, it, i))
  207.         state.state = states.INITIAL
  209.     } else {
  210.         return errors.New(fmt.Sprintf("parseCharWhenFrag, invalid char %c at %d", it, i))
  211.     }
  213.     return nil
  214. }

parser/tStackNode.go

定义计算栈的一个节点. 计算栈中有两种节点: 已归约的值节点, 和尚未计算的记号节点

  1. type tStackNodeType int
  2. const NODE_VALUE tStackNodeType = 1
  3. const NODE_TOKEN tStackNodeType = 2
  5. type tStackNode struct {
  6.     flag tStackNodeType
  7.     token *tokens.Token
  8.     value float64
  9. }
  12. func newValueNode(value float64) *tStackNode {
  13.     return &tStackNode{
  14.         flag: NODE_VALUE,
  15.         value: value,
  16.         token: nil,
  17.     }
  18. }
  21. func newTokenNode(token *tokens.Token) *tStackNode {
  22.     return &tStackNode{
  23.         flag: NODE_TOKEN,
  24.         token: token,
  25.         value: 0,
  26.     }
  27. }
  30. func (me *tStackNode) getTokenType() tokens.TOKENS {
  31.     switch me.flag {
  32.     case NODE_VALUE:
  33.         return tokens.DoubleLiteral
  35.     case NODE_TOKEN:
  36.         switch me.token.Token {
  37.         case tokens.IntLiteral:
  38.             fallthrough
  39.         case tokens.DoubleLiteral:
  40.             return tokens.DoubleLiteral
  41.         default:
  42.             return me.token.Token
  43.         }
  44.     }
  46.     return tokens.UNKNOWN
  47. }
  50. func (me *tStackNode) getDoubleValue() float64 {
  51.     switch me.flag {
  52.     case NODE_VALUE:
  53.         return me.value
  55.     case NODE_TOKEN:
  56.         switch me.token.Token {
  57.         case tokens.IntLiteral:
  58.             fallthrough
  59.         case tokens.DoubleLiteral:
  60.             v1,e1 := strconv.ParseFloat(me.token.Value, 64)
  61.             if e1 != nil {
  62.                 panic(e1)
  63.             }
  64.             return v1
  65.         }
  66.     }
  68.     panic("value not avaiable")
  69. }

parser/parser.go

  1. type tParser struct {
  2.     tokens []*tokens.Token
  3.     stack []*tStackNode
  4.     total int
  5.     position int
  6. }
  9. func newParser(tokens []*tokens.Token)  *tParser {
  10.     return &tParser{
  11.         tokens: tokens,
  12.         stack: make([]*tStackNode, 0),
  13.         total : len(tokens),
  14.         position: -1,
  15.     }
  16. }
  18. func (me *tParser) showStack() string {
  19.     lst := make([]string, 0)
  20.     for _,it := range me.stack {
  21.         switch it.flag {
  22.         case NODE_VALUE:
  23.             lst = append(lst, strconv.FormatFloat(it.value, 'f', 10, 64))
  24.             break
  25.         case NODE_TOKEN:
  26.             switch it.token.Token {
  27.             case tokens.DoubleLiteral:
  28.                 fallthrough
  29.             case tokens.IntLiteral:
  30.                 lst = append(lst, it.token.Value)
  31.                 break
  33.             default:
  34.                 lst = append(lst, it.token.Value)
  35.                 break
  36.             }
  37.         }
  38.     }
  39.     return strings.Join(lst, " ")
  40. }
  43. func (me *tParser) moreToken() bool {
  44.     return me.position < me.total - 1
  45. }
  47. func (me *tParser) nextToken() *tokens.Token {
  48.     if !me.moreToken() {
  49.         return nil
  50.     }
  52.     me.position++
  53.     return me.currentToken()
  54. }
  56. func (me *tParser) currentToken() *tokens.Token {
  57.     if me.position >= me.total {
  58.         return nil
  59.     }
  60.     return me.tokens[me.position]
  61. }
  63. func (me *tParser) reduce() {
  64.     sCurrentStack := ""
  65.     var fnCheckState = func() {
  66.         sStackState := me.showStack()
  67.         if sStackState != sCurrentStack {
  68.             sCurrentStack = sStackState
  69.             fmt.Printf("stack => %s\n", sStackState)
  70.         }
  71.     }
  73.     for {
  74.         fnCheckState()
  76.         if me.reduceMulOrDiv() {
  77.             continue
  78.         }
  80.         if me.reduceBrackets() {
  81.             continue
  82.         }
  84.         if !me.moreToken() {
  85.             if me.reduceAddOrSub() {
  86.                 break
  87.             }
  88.         }
  90.         fnCheckState()
  91.         //time.Sleep(1*time.Second)
  93.         break
  94.     }
  95. }
  98. func (me *tParser) stackPop() *tStackNode {
  99.     if me.isStackEmpty() {
  100.         return nil
  101.     }
  103.     var iStackSize = len(me.stack)
  104.     var last = me.stack[iStackSize - 1]
  105.     me.stack = me.stack[:(iStackSize-1)]
  106.     return last
  107. }
  109. func (me *tParser) stackPopN(n int) []*tStackNode {
  110.     if me.isStackEmpty() {
  111.         return nil
  112.     }
  114.     var iStackSize = len(me.stack)
  115.     if iStackSize < n {
  116.         return nil
  117.     }
  119.     var lstTailItems = me.stack[(iStackSize - n):]
  120.     me.stack = me.stack[:(iStackSize-n)]
  121.     return lstTailItems
  122. }
  124. func (me *tParser) stackTakeN(n int) []*tStackNode {
  125.     if me.isStackEmpty() {
  126.         return nil
  127.     }
  129.     var iStackSize = len(me.stack)
  130.     if iStackSize < n {
  131.         return nil
  132.     }
  134.     var lstHeadItems = me.stack[:n]
  135.     me.stack = me.stack[n+1:]
  136.     return lstHeadItems
  137. }
  140. func (me *tParser) stackPush(it *tStackNode) {
  141.     me.stack = append(me.stack, it)
  142. }
  144. func (me *tParser) reduceMulOrDiv() bool {
  145.     if me.isStackEmpty() {
  146.         return false
  147.     }
  149.     if me.isStackRMatch(tokens.DoubleLiteral, tokens.MUL, tokens.DoubleLiteral) {
  150.         var lstTailNodes = me.stackPopN(3)
  151.         v1 := lstTailNodes[0].getDoubleValue()
  152.         v2 := lstTailNodes[2].getDoubleValue()
  153.         var v = v1*v2
  154.         me.stackPush(newValueNode(v))
  155.         return true
  157.     } else if me.isStackRMatch(tokens.DoubleLiteral, tokens.DIV, tokens.DoubleLiteral) {
  158.         var lstTailNodes = me.stackPopN(3)
  159.         v1 := lstTailNodes[0].getDoubleValue()
  160.         v2 := lstTailNodes[2].getDoubleValue()
  161.         if v2 == 0 {
  162.             panic(fmt.Sprintf("div by zero, %v / %v", v1, v2))
  163.         }
  164.         var v = v1/v2
  165.         me.stackPush(newValueNode(v))
  166.         return true
  167.     }
  169.     return false
  170. }
  174. func (me *tParser) reduceBrackets() bool {
  175.     if me.isStackEmpty() {
  176.         return false
  177.     }
  179.     if me.isStackRMatch(tokens.RB) {
  180.         rb := me.stackPop()
  181.         var v float64 = 0
  182.         for {
  183.             if me.isStackRMatch(tokens.LB, tokens.DoubleLiteral) {
  184.                 var lstTailNodes = me.stackPopN(2)
  185.                 v += lstTailNodes[1].getDoubleValue()
  186.                 me.stackPush(newValueNode(v))
  187.                 return true
  189.             } else if me.isStackRMatch(tokens.ADD, tokens.DoubleLiteral) {
  190.                 var lstTailNodes = me.stackPopN(2)
  191.                 v1 := lstTailNodes[1].getDoubleValue()
  192.                 v = v + v1
  194.             } else if me.isStackRMatch(tokens.SUB, tokens.DoubleLiteral) {
  195.                 var lstTailNodes = me.stackPopN(2)
  196.                 v1 := lstTailNodes[1].getDoubleValue()
  197.                 v = v - v1
  199.             } else {
  200.                 panic(fmt.Sprintf("LB not found at %v", rb.token.Position))
  201.             }
  202.         }
  203.     }
  206.     return false
  207. }
  210. func (me *tParser) reduceAddOrSub() bool {
  211.     var v float64 = 0
  212.     for {
  213.         if me.isStackEmpty() {
  214.             break
  215.         }
  217.         if me.isStackRMatch(tokens.ADD, tokens.DoubleLiteral) {
  218.             var lstTailNodes = me.stackPopN(2)
  219.             v1 := lstTailNodes[1].getDoubleValue()
  220.             v = v + v1
  222.         } else if me.isStackRMatch(tokens.SUB, tokens.DoubleLiteral) {
  223.             var lstTailNodes = me.stackPopN(2)
  224.             v1 := lstTailNodes[1].getDoubleValue()
  225.             v = v - v1
  227.         } else if len(me.stack)==1 && me.isStackRMatch(tokens.DoubleLiteral) {
  228.             it := me.stackPop()
  229.             v += it.getDoubleValue()
  230.             me.stackPush(newValueNode(v))
  231.             return true
  233.         } else {
  234.             panic("invalid expression")
  235.         }
  236.     }
  238.     return false
  239. }
  242. func (me *tParser) isStackEmpty() bool {
  243.     return len(me.stack) == 0
  244. }
  246. func (me *tParser) isStackRMatch(args...tokens.TOKENS) bool {
  247.     var iArgsSize = len(args)
  248.     if iArgsSize <= 0 {
  249.         return false
  250.     }
  252.     var iStackSize = len(me.stack)
  253.     if iStackSize < iArgsSize {
  254.         return false
  255.     }
  257.     for i,it := range args {
  258.         var n = iStackSize - iArgsSize + i
  259.         var xStackNode = me.stack[n]
  260.         if it != xStackNode.getTokenType() {
  261.             return false
  262.         }
  263.     }
  265.     return true
  266. }
  268. func (me *tParser) isStackLMatch(args...tokens.TOKENS) bool {
  269.     var iArgsSize = len(args)
  270.     if iArgsSize <= 0 {
  271.         return false
  272.     }
  274.     var iStackSize = len(me.stack)
  275.     if iStackSize < iArgsSize {
  276.         return false
  277.     }
  279.     for i,it := range args {
  280.         var xStackNode = me.stack[i]
  281.         if it != xStackNode.getTokenType() {
  282.             return false
  283.         }
  284.     }
  286.     return true
  287. }
  289. func (me *tParser) parse() (error, float64) {
  290.     for {
  291.         t := me.nextToken()
  292.         if t == nil {
  293.             break
  294.         }
  296.         me.stackPush(newTokenNode(t))
  297.         me.reduce()
  298.     }
  300.     var iStackSize = len(me.stack)
  301.     if iStackSize == 1 && me.stack[0].getTokenType() == tokens.DoubleLiteral {
  302.         return nil, me.stack[0].getDoubleValue()
  303.     }
  305.     panic(fmt.Sprintf("failed parsing expression %s", me.showStack()))
  306. }
  309. func Parse(tokens []*tokens.Token) (error, float64) {
  310.     parser := newParser(tokens)
  311.     return parser.parse()
  312. }

输出

  1. => 1+2*(3-4*(5/6+(7-8*9)))
  2. stack => 1
  3. stack => 1 +
  4. stack => 1 + 2
  5. stack => 1 + 2 *
  6. stack => 1 + 2 * (
  7. stack => 1 + 2 * ( 3
  8. stack => 1 + 2 * ( 3 -
  9. stack => 1 + 2 * ( 3 - 4
  10. stack => 1 + 2 * ( 3 - 4 *
  11. stack => 1 + 2 * ( 3 - 4 * (
  12. stack => 1 + 2 * ( 3 - 4 * ( 5
  13. stack => 1 + 2 * ( 3 - 4 * ( 5 /
  14. stack => 1 + 2 * ( 3 - 4 * ( 5 / 6
  15. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333
  16. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 +
  17. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + (
  18. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7
  19. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 -
  20. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8
  21. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8 *
  22. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 8 * 9
  23. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 72.0000000000
  24. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + ( 7 - 72.0000000000 )
  25. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + -65.0000000000
  26. stack => 1 + 2 * ( 3 - 4 * ( 0.8333333333 + -65.0000000000 )
  27. stack => 1 + 2 * ( 3 - 4 * -64.1666666667
  28. stack => 1 + 2 * ( 3 - -256.6666666667
  29. stack => 1 + 2 * ( 3 - -256.6666666667 )
  30. stack => 1 + 2 * 259.6666666667
  31. stack => 1 + 519.3333333333
  32. 520.3333333333
  33. =>