栈是一种“操作受限”的线性表，后进者先出，先进者后出。
比较典型的例子就是我们在叠盘子的时候，叠的时候从下到上一个一个磊起来，取的时候，再从上到下一个一个的拿出来。
说到先入后出这种特性，在 Go 中你第一时间想到了什么？不知道是否和我的答案一样， defer
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 calculationimport (
"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()
}
|
