C'est l'un des problèmes de LeetCode que j'ai aimé résoudre. Je l'ai résolu dans Golang, et je suis déjà un débutant en Go, qui a commencé à y apprendre depuis seulement une semaine.

Intuition

Ce problème est une autre version de l'implémentation d'un programme de calcul qui prend une chaîne et l'évalue. Vous devez résoudre en évaluant les parenthèses intérieures par rapport aux parenthèses extérieures jusqu'à ce que vous obteniez le résultat final. Ces problèmes sont mieux décrits par une pile, vous implémentez simplement un CallStack qui, lorsque vous ouvrez une nouvelle parenthèse, vous poussez vers la pile, et lorsque vous la fermez, vous sortez simplement de la pile. A la dernière clôture nous appelons Eval pour avoir le résultat final.

Nous avons 3 opérations qui peuvent être effectuées dans notre calculatrice, et il existe quelques faits connus à leur sujet :

• AND : c'est vrai jusqu'à ce que vous trouviez un faux (un faux suffit)
• OR : c'est faux jusqu'à ce que vous trouviez un vrai (un vrai suffit)
• Not : c'est le contraire de son argument.

Donc, nous n'avons pas besoin de conserver toutes les valeurs de chaque opération pour connaître son résultat final. Si nous résolvons un AND, maintenez simplement si vous avez trouvé un faux ou non, si OU, maintenez si vous avez trouvé vrai ou non, et si NON, alors ce sera déjà une valeur que vous évaluerez à celui qui est en face.

Approche

Nous implémentons une structure personnalisée : CallStack, qui comporte 2 tranches, une pour l'opération et une pour la valeur que nous allons évaluer.
La pile d'appels a des méthodes :

• Push : utilisé pour pousser les valeurs et les opérations vers les 2 tranches dont nous disposons. Les opérations poussent une nouvelle valeur vers les 2 tranches, et les valeurs (t ou f) modifient simplement la dernière valeur saisie dans la tranche de valeurs.
• Pop : supprime la dernière valeur des 2 tranches, évalue la valeur sautée avec l'opération sautée et utilise le résultat pour modifier la nouvelle dernière valeur après le saut.
• Eval : appelé lorsqu'il s'agit de la dernière parenthèse fermante pour évaluer la dernière valeur restante dans la tranche des valeurs avec la dernière opération restante dans la tranche des opérations.

La solution peut être davantage optimisée en mettant fin à l'évaluation de Ands une fois que vous trouvez un faux, et d'Ors une fois que vous avez trouvé un vrai, je vous laisse le faire si vous le souhaitez :)

Complexité

• Complexité temporelle :
  Sur)

• Complexité spatiale :
  Sur)

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