This is one of the LeetCode problems I enjoyed solving. I solved it in Golang, and I'm already a Go newbie, who started learning in it since just one week.
LeetCode: Parsing Boolean Expression (Hard)
Intuition
This problem is another version of implementing a calculator program that takes a string and evaluates it. You have to solve by evaluating the inner parenthesis to the outer ones until you get the final result. These problems are best described by a stack, you're just implementing a CallStack that when opening a new parenthesis, you Push to the stack, and when closing it you just Pop from the stack. At the last closing we call Eval to get the final result.
We have 3 operations that can be done in our calculator, and there are some known facts about them:
- AND: it's true until you find a false (one false is enough)
- OR: it's false until you find a true (one true is enough)
- Not: it's the opposite of the it's argument.
So, we don't need to maintain all the values for each operation to know it's final result. If we're solving an AND, just maintain if you found a false or not, if OR, maintain if you found a true or not, and if NOT, then it's already gonna be one value that you'll evaluate to it's opposite one.
Approach
We implement a custom struct: CallStack, that has 2 slices, one for the operation and one for the value that we're gonna evaluate.
The call stack has methods:
-
Push: used to push values & operations to the 2 slices we have. Operations push new value to the 2 slices, and values (
torf) just modify the last entered value in the values slice. - Pop: remove last value from the 2 slices, evaluate the popped value with the popped operation and use the result to modify the new last value after popping.
- Eval: called when it's the last closing parenthesis to evaluate the last remaining value in the values slice with the last remaining operation in the operations slice.
The solution can be more optimized by ending the evaluation of Ands once you find a false, and Ors once you find a true, I'll leave that for you to do if you want :)
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
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
}
Top comments (0)