LeetCode in Golang: Parsen eines booleschen Ausdrucks

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 durchgefü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 UND lösen, behalten Sie einfach bei, wenn Sie ein gefunden haben falsch oder nicht, wenn ODER, behalten Sie bei, ob Sie wahr gefunden haben oder nicht, und wenn NICHT, dann wird es bereits ein Wert sein, den Sie mit seinem Gegenteil auswerten.

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 verfügt über 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 weiter optimiert werden, indem die Auswertung von Ands beendet wird, sobald Sie ein „Falsch“ finden, und von Ors, sobald Sie ein „Wahr“ finden. Das überlasse ich Ihnen, wenn Sie möchten :)

Komplexität

• Zeitliche Komplexität:
  O(n)

• Raumkomplexität:
  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
}

Das obige ist der detaillierte Inhalt vonLeetCode in Golang: Parsen eines booleschen Ausdrucks. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!