-
Notifications
You must be signed in to change notification settings - Fork 5
/
parsing-a-boolean-expression.go
100 lines (94 loc) · 2.32 KB
/
parsing-a-boolean-expression.go
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
// @Title: 解析布尔表达式 (Parsing A Boolean Expression)
// @Author: KivenC
// @Date: 2019-07-08 11:39:07
// @Runtime: 0 ms
// @Memory: 2.6 MB
// // way 1
// func parseBoolExpr(expression string) bool {
// switch expression{
// case "":return true
// case "t":return true
// case "f":return false
// }
// if expression[0]=='!'{
// return !parseBoolExpr(expression[2:len(expression)-1])
// }
// if expression[0]=='&'{
// exps:=split(expression[2:len(expression)-1])
// for i:=range exps{
// if !parseBoolExpr(exps[i]){
// return false
// }
// }
// return true
// }
// if expression[0]=='|'{
// exps:=split(expression[2:len(expression)-1])
// for i:=range exps{
// if parseBoolExpr(exps[i]){
// return true
// }
// }
// return false
// }
// return true
// }
// func split(s string)[]string{
// stack:=make([]byte,0)
// result:=make([]string,0)
// for i:=0;i<len(s);i++{
// if s[i]=='('||s[i]=='{'{
// stack=append(stack,s[i])
// }
// if s[i]==')'||s[i]=='}'{
// stack=stack[:len(stack)-1]
// }
// if len(stack)==0&&s[i]==','{
// result=append(result,s[:i])
// s=s[i+1:]
// i=0
// }
// }
// result=append(result,s)
// return result
// }
// way 2
// 双栈
func parseBoolExpr(expression string) bool {
v, op := []rune{}, []rune{} // 双栈,分别记录表达式和操作符
tf := []rune{'f', 't'}
for _, c := range expression {
switch c {
case ',':
break
case '|', '&', '!':
op = append(op, c)
case ')':
t, f := 0, 0 // 用于标记是否存在 t/f
for v[len(v)-1] != '(' {
if v[len(v)-1] == 'f' {
f = 1
} else {
t = 1
}
v = v[:len(v)-1]
}
v = v[:len(v)-1] // 将左括号 ( 出栈
switch op[len(op)-1] {
case '|':
// 存在 t 即为真
v = append(v, tf[t])
case '&':
// 存在 f 即为假
v = append(v, tf[1-f])
case '!':
// 存在 f 为真
v = append(v, tf[f])
}
op = op[:len(op)-1]
default:
v = append(v, c)
}
}
return v[0] == 't'
}