Golang 中的 LeetCode：解析布林表達式

這是我喜歡解決的 LeetCode 問題之一。我用 Golang 解決了這個問題，而且我已經是一個 Go 新手了，剛開始學習一週。

直覺

這個問題是實現計算器程式的另一個版本，該程式接受一個字串並對其求值。您必須透過評估內部括號和外部括號來解決問題，直到您得到最終結果。這些問題最好用堆疊來描述，您只需實作一個 CallStack，當開啟新括號時，您將 Push 到堆疊，而當關閉它時，您只需從堆疊中 Pop 。最後關閉時我們呼叫 Eval 來獲得最終結果。

我們可以在計算器中完成 3 種運算，並且有一些關於它們的已知事實：

• AND：它是真的，直到你找到一個假的（一個假就夠了）
• 或：它是假的，直到你找到一個真（一個真就夠了）
• Not：它與 it 的論證相反。

因此，我們不需要維護每個操作的所有值來知道它的最終結果。 如果我們正在解決AND，只需維護是否找到一個是否為假，如果或，則保持是否找到真值，如果不是，那麼它已經是一個值，您將評估它的相反值。

方法

我們實作了一個自訂結構：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
}

以上是Golang 中的 LeetCode：解析布林表達式的詳細內容。更多資訊請關注PHP中文網其他相關文章！