Dies ist eines der LeetCode-Probleme, die ich gerne gelöst habe. Ich habe es in Golang gelöst und bin bereits ein Go-Neuling, der erst seit einer Woche damit beginnt, darin zu lernen.

Intuition

Dieses Problem ist eine andere Version der Implementierung eines Taschenrechnerprogramms, das einen String nimmt und ihn auswertet. Sie müssen das Problem lösen, indem Sie die inneren Klammern mit den äußeren vergleichen, bis Sie das Endergebnis erhalten. Diese Probleme lassen sich am besten durch einen Stapel beschreiben. Sie implementieren lediglich einen CallStack, der beim Öffnen einer neuen Klammer auf den Stapel drückt und beim Schließen einfach vom Stapel entfernt. Beim letzten Abschluss rufen wir Eval an, um das Endergebnis zu erhalten.

Wir haben drei Operationen, die in unserem Rechner ausgeführt werden können, und es gibt einige bekannte Fakten darüber:

• UND: Es ist wahr, bis Sie ein falsches finden (ein falsches ist genug)
• ODER: Es ist falsch, bis Sie ein Wahres finden (ein Wahres ist genug)
• Nicht: Es ist das Gegenteil des Arguments.

Wir müssen also nicht alle Werte für jede Operation pflegen, um das Endergebnis zu kennen. Wenn wir ein AND lösen, pflegen Sie es einfach, wenn Sie ein gefunden haben falsch oder nicht, wenn ODER, behalten Sie bei, ob Sie einen wahren Wert gefunden haben oder nicht, und wenn NICHT, dann ist es bereits ein Wert, den Sie auswerten werden dazu ist das Gegenteil.

Ansatz

Wir implementieren eine benutzerdefinierte Struktur: CallStack, die zwei Slices hat, eines für die Operation und eines für den Wert, den wir auswerten werden.
Der Aufrufstapel hat Methoden:

• Push: Wird verwendet, um Werte und Operationen auf die beiden Slices zu übertragen, die wir haben. Operationen übertragen neue Werte auf die beiden Slices, und Werte (t oder f) ändern lediglich den zuletzt eingegebenen Wert im Werte-Slice.
• Pop: Entfernen Sie den letzten Wert aus den beiden Slices, werten Sie den Popup-Wert mit der Popup-Operation aus und verwenden Sie das Ergebnis, um den neuen letzten Wert nach dem Popup zu ändern.
• Eval: wird aufgerufen, wenn es sich um die letzte schließende Klammer handelt, um den letzten verbleibenden Wert im Werte-Slice mit der letzten verbleibenden Operation im Operations-Slice auszuwerten.

Die Lösung kann optimiert werden, indem die Auswertung von „Ands“ beendet wird, sobald Sie „falsch“ finden, und „Ors“, sobald Sie „wahr“ finden. Das überlasse ich Ihnen, wenn Sie möchten :)

Komplexität

• Zeitliche Komplexität:
  An)

• Raumkomplexität:
  An)

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