Ming
0%

LeetCode-227

Posted on Edited on In

题目

227. 基本计算器 II

Snipaste_2021-03-11_10-04-20.png

这道题和另一道题目一模一样：

面试题 16.26. 计算器

Blog-面试题 16.26

结果

代码

将数字逐个入栈，遇到乘除号就计算，遇到减号就将其变为相反数，最后求和。

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
func calculate(s string) int {
   stk := make([]int, 0)
   opt := '+'
   num := 0

   for i, v := range s {
      if unicode.IsDigit(v) {
         num = num*10 + int(v-'0')
      }

      if isOpt(v) || i == len(s)-1 {
         switch opt {
         case '+':
            stk = append(stk, num)
         case '-':
            stk = append(stk, -num)
         case '*':
            // stack pop
            top := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            stk = append(stk, top*num)
         case '/':
            // stack pop
            top := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            stk = append(stk, top/num)
         }
         // reset
         opt = v
         num = 0
      }
   }
   return sum(stk)
}

func isOpt(ch rune) bool {
   opts := "+-*/"
   return strings.Contains(opts, string(ch))
}

func sum(nums []int) int {
   ans := 0
   for _, v := range nums {
      ans += v
   }
   return ans
}

另一种解法

之前写的，不同的思路，这个显得很复杂，应该是我代码写的太垃圾的原因。

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
109
110
111
112
113
114
115
116
package main

import (
   "strconv"
   "unicode"
)

func main() {
   println(calculate("3+2*2"))
}

var priority = map[rune]int{
   '+': 0,
   '-': 0,
   '*': 1,
   '/': 1,
}

type elem struct {
   val  int
   flag bool // number or operator
}

func calculate(s string) int {
   return val(expr(s))
}

// convert in-order sequence to after-order sequence
func expr(src string) []elem {
   var exprStk []elem
   var opStk []rune

   // ignore or not when encounter a digit
   var jump bool

   for i, v := range src {
      switch {
      case unicode.IsSpace(v):
         continue
      case unicode.IsDigit(v):
         if !jump {
            exprStk = append(exprStk, elem{val: nextNum(src, i)})
            jump = true
         }
      default: // operator: + - * /
         jump = false
         if len(opStk) == 0 || priority[v] > priority[opStk[len(opStk)-1]] {
            opStk = append(opStk, v)
            continue
         }
         for len(opStk) != 0 {
            // pop the operators which have higher or same priority
            top := opStk[len(opStk)-1]
            if priority[v] <= priority[top] {
               exprStk = append(exprStk, elem{
                  val:  int(top),
                  flag: true,
               })
               opStk = opStk[:len(opStk)-1]
            } else {
               break
            }
         }
         opStk = append(opStk, v)
      }
   }

   // push the rest operators into the exprStk
   for len(opStk) != 0 {
      top := opStk[len(opStk)-1]
      exprStk = append(exprStk, elem{
         val:  int(top),
         flag: true,
      })
      opStk = opStk[:len(opStk)-1]
   }
   return exprStk
}

func val(expr []elem) int {
   stk := make([]int, 0)
   for _, v := range expr {
      switch v.flag {
      case false: // number
         stk = append(stk, v.val)
      case true: // operator
         b := stk[len(stk)-1]
         stk = stk[:len(stk)-1]
         a := stk[len(stk)-1]
         stk = stk[:len(stk)-1]
         switch v.val {
         case '+':
            stk = append(stk, a+b)
         case '-':
            stk = append(stk, a-b)
         case '*':
            stk = append(stk, a*b)
         case '/':
            stk = append(stk, a/b)
         }
      }
   }
   return stk[0]
}

func nextNum(expr string, index int) int {
   var str string
   for i := index; i < len(expr); i++ {
      if !unicode.IsDigit(rune(expr[i])) {
         break
      }
      str += string(expr[i])
   }
   ans, _ := strconv.ParseInt(str, 10, 64)
   return int(ans)
}

复杂度

时间复杂度：O（n），遍历数组stk

空间复杂度：O（n），使用数组stk