这是我喜欢解决的 leetcode 问题之一。我用 golang 解决了这个问题，而且我已经是一个 go 新手了，刚开始学习一周。
直觉
这个问题是实现计算器程序的另一个版本，该程序接受一个字符串并对其求值。您必须通过评估内部括号和外部括号来解决问题，直到得到最终结果。这些问题最好用堆栈来描述，您只需实现一个 callstack，当打开新括号时，您将 push 到堆栈，而当关闭它时，您只需从堆栈中 pop 。最后关闭时我们调用 eval 来获得最终结果。
我们可以在计算器中完成 3 种运算，并且有一些关于它们的已知事实：
- and：它是真的，直到你找到一个假的（一个假就足够了）
- 或：在找到真值之前它都是假的（一个真值就足够了）
- not：与 it 的论证相反。
因此，我们不需要维护每个操作的所有值来知道它的最终结果。如果我们正在解决 and，只需维护是否找到一个是否为假，如果或，则保持是否找到真值，如果不是，那么它已经是一个值，您将评估它的相反值。
立即学习“go语言免费学习笔记（深入）”；
方法
我们实现了一个自定义结构：callstack，它有 2 个切片，一个用于操作，一个用于我们要评估的值。
调用堆栈有方法：
- push：用于将值和操作推送到我们拥有的 2 个切片。操作将新值推送到 2 个切片，并且值（t 或 f）仅修改值切片中最后输入的值。
- pop：从 2 个切片中删除最后一个值，使用弹出操作评估弹出的值，并使用结果修改弹出后的 new 最后一个值。
- eval：当它是最后一个右括号时调用，以使用操作切片中的最后一个剩余操作来评估值切片中的最后一个剩余值。
一旦发现错误，就结束 ands 的评估，一旦找到 true，就结束对 ors 的评估，可以进一步优化解决方案，如果你愿意，我会将其留给你做:)
复杂
时间复杂度：
o(n)空间复杂度：
o(n)
代码
type CallStack struct {
operations []string
values []int
}
func NewCallStack() *CallStack {
return &CallStack{
operations: make([]string, 0),
values: make([]int, 0),
}
}
func (s *CallStack) pushOperation(op string) {
s.operations = append(s.operations, op)
var newVal int
switch op {
case Not:
newVal = 0
default:
newVal = 1
}
s.values = append(s.values, newVal)
}
func (s *CallStack) pushValue(op string, char string) {
switch op {
case And:
if char == "f" {
s.values[len(s.values)-1] = -1
}
case Or:
if char == "t" {
s.values[len(s.values)-1] = -1
}
default: // Not
if char == "t" {
s.values[len(s.values)-1] = 1
} else {
s.values[len(s.values)-1] = -1
}
}
}
func (s *CallStack) Push(char string) {
switch char {
case Not, And, Or:
s.pushOperation(char)
default:
s.pushValue(s.operations[len(s.operations) - 1], char)
}
}
func eval(op string, val int) bool {
switch op {
case And:
if val == 1 {
return true
} else {
return false
}
case Or:
if val == -1 {
return true
} else {
return false
}
default: // Not
if val < 0 {
return true
} else {
return false
}
}
}
func addResult(op string, val int, res bool) int {
switch op {
case And:
if res {
return val
} else {
return -1
}
case Or:
if res {
return -1
} else {
return val
}
default: // Not
if res {
return 1
} else {
return -1
}
}
}
func (s *CallStack) Pop() {
op := s.operations[len(s.operations)-1]
s.operations = s.operations[:len(s.operations)-1]
val := s.values[len(s.values)-1]
s.values = s.values[:len(s.values)-1]
result := eval(op, val)
currOp := s.operations[len(s.operations)-1] // current last operation
currVal := s.values[len(s.values)-1] // current last value
s.values[len(s.values)-1] = addResult(currOp, currVal, result)
}
func (s *CallStack) Eval() bool {
// now the length of slices is 1
op := s.operations[0]
val := s.values[0]
return eval(op, val)
}
const (
Not string = "!"
And string = "&"
Or string = "|"
)
func parseBoolExpr(expression string) bool {
stack := NewCallStack()
for i := 0; i < len(expression); i++ {
char := string(expression[i])
switch char {
case "(", ",":
// ignore opennings & commas
continue
case ")":
if i == len(expression) - 1 {
// it's the last closing
return stack.Eval()
} else {
stack.Pop()
}
default:
stack.Push(char)
}
}
return true
}
