LeetCode en Golang : analyser une expression booléenne

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 y a quelques faits connus à leur sujet :

• ET : c'est vrai jusqu'à ce que vous trouviez un faux (un faux suffit)
• OU : c'est faux jusqu'à ce qu'on trouve un vrai (un vrai suffit)
• Non : 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 ET, maintenez simplement si vous avez trouvé un faux ou non, si OU, maintenez si vous avez trouvé un vrai ou non, et si NON, alors ce sera déjà une valeur que vous évaluerez par rapport à celle opposée.

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 que nous avons. 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 : supprimez la dernière valeur des 2 tranches, évaluez la valeur sautée avec l'opération sautée et utilisez le résultat pour modifier la nouvelle dernière valeur après le popping.
• Eval : appelé lorsque c'est 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 de Ors une fois que vous trouvez un vrai, je vous laisse faire si vous le souhaitez :)

Complexité

• Complexité temporelle :
  O(n)

• Complexité spatiale :
  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
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!