/kata.go Secret
Created
September 28, 2021 12:15
evaluateExp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package kata | |
import ( | |
"rachel/tree" | |
) | |
func EvaluateExp(s string) int { | |
count := 0 | |
trees := tree.FullBinaryTreesFor(s) | |
for _, tree := range trees { | |
if evalBinaryTree(tree) { | |
count ++ | |
} | |
} | |
return count | |
} | |
func evalBinaryTree(tree *tree.BinaryTree) bool { | |
if tree.Left == nil && tree.Right == nil { | |
return tree.Value == 'T' | |
} | |
switch tree.Value { | |
case '&': | |
return evalBinaryTree(tree.Left) && evalBinaryTree(tree.Right) | |
case '|': | |
return evalBinaryTree(tree.Left) || evalBinaryTree(tree.Right) | |
case '^': | |
return evalBinaryTree(tree.Left) != evalBinaryTree(tree.Right) | |
} | |
return false | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package tree | |
type BinaryTree struct { | |
Value byte | |
Left *BinaryTree | |
Right *BinaryTree | |
} | |
func FullBinaryTreesFor(s string) []*BinaryTree { | |
length := len(s) | |
if length == 1 { | |
return []*BinaryTree{&BinaryTree{Value: s[0]}} | |
} | |
var result []*BinaryTree | |
for i := 0; i < (length-1)/2; i++ { | |
e := i*2+1 // Odd index | |
ltrees := FullBinaryTreesFor(s[:e]) | |
rtrees := FullBinaryTreesFor(s[(e+1):]) | |
for _, ltree := range ltrees { | |
for _, rtree := range rtrees { | |
result = append(result, &BinaryTree{s[e], ltree, rtree}) | |
} | |
} | |
} | |
return result | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Love that you used binary trees!!