面试题：Go布尔类型在复杂逻辑判断与布尔代数优化中的实践

Question

给定一个表示逻辑表达式的字符串，例如 "(true AND false) OR (true AND true)"，在Go语言中编写一个函数来解析并计算该逻辑表达式的值，使用布尔代数规则。你需要处理括号以正确确定运算优先级。请描述你的设计思路和关键实现步骤，并给出完整代码。

Answer 1

设计思路

1. 词法分析：将输入的字符串分割成一个个的词法单元（token），包括逻辑值（true、false）、逻辑运算符（AND、OR）和括号。
2. 语法分析：使用栈来处理括号和运算优先级。当遇到左括号时，开始一个新的子表达式处理；遇到右括号时，结束当前子表达式处理并将结果压入栈。
3. 计算逻辑值：根据布尔代数规则，对逻辑运算符和逻辑值进行计算。

关键实现步骤

1. 定义词法单元类型：创建一个结构体来表示不同类型的词法单元，如逻辑值、运算符和括号。
2. 词法分析函数：编写一个函数将输入字符串分割成词法单元数组。
3. 语法分析和计算函数：利用栈来处理运算优先级，根据布尔代数规则计算逻辑表达式的值。

完整代码

package main

import (
    "fmt"
    "strings"
)

// 定义词法单元类型
type Token struct {
    value string
    kind  string
}

// 词法分析函数
func tokenize(input string) []Token {
    var tokens []Token
    words := strings.FieldsFunc(input, func(c rune) bool {
        return c == '(' || c == ')' || c == ' '
    })
    for _, word := range words {
        switch word {
        case "true", "false":
            tokens = append(tokens, Token{value: word, kind: "bool"})
        case "AND", "OR":
            tokens = append(tokens, Token{value: word, kind: "operator"})
        case "(":
            tokens = append(tokens, Token{value: word, kind: "left_paren"})
        case ")":
            tokens = append(tokens, Token{value: word, kind: "right_paren"})
        }
    }
    return tokens
}

// 计算逻辑表达式的值
func evaluate(tokens []Token) bool {
    var stack []bool
    var operatorStack []string
    for _, token := range tokens {
        switch token.kind {
        case "bool":
            stack = append(stack, token.value == "true")
        case "operator":
            for len(operatorStack) > 0 && operatorStack[len(operatorStack)-1] != "(" {
                operator := operatorStack[len(operatorStack)-1]
                operatorStack = operatorStack[:len(operatorStack)-1]
                right := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                left := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                if operator == "AND" {
                    stack = append(stack, left && right)
                } else {
                    stack = append(stack, left || right)
                }
            }
            operatorStack = append(operatorStack, token.value)
        case "left_paren":
            operatorStack = append(operatorStack, token.value)
        case "right_paren":
            for operatorStack[len(operatorStack)-1] != "(" {
                operator := operatorStack[len(operatorStack)-1]
                operatorStack = operatorStack[:len(operatorStack)-1]
                right := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                left := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                if operator == "AND" {
                    stack = append(stack, left && right)
                } else {
                    stack = append(stack, left || right)
                }
            }
            operatorStack = operatorStack[:len(operatorStack)-1]
        }
    }
    for len(operatorStack) > 0 {
        operator := operatorStack[len(operatorStack)-1]
        operatorStack = operatorStack[:len(operatorStack)-1]
        right := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        left := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if operator == "AND" {
            stack = append(stack, left && right)
        } else {
            stack = append(stack, left || right)
        }
    }
    return stack[0]
}

func main() {
    input := "(true AND false) OR (true AND true)"
    tokens := tokenize(input)
    result := evaluate(tokens)
    fmt.Println(result)
}