Este es uno de los problemas de LeetCode que disfruté resolviendo. Lo resolví en Golang y ya soy un novato en Go, que comencé a aprender en Golang desde hace solo una semana.

Intuición

Este problema es otra versión de la implementación de un programa de calculadora que toma una cadena y la evalúa. Tienes que resolver evaluando los paréntesis internos con los externos hasta obtener el resultado final. Estos problemas se describen mejor mediante una pila; simplemente está implementando una CallStack que, al abrir un nuevo paréntesis, empuja a la pila y, al cerrarla, simplemente saca de la pila. En el último cierre llamamos a Eval para obtener el resultado final.

Tenemos 3 operaciones que se pueden realizar en nuestra calculadora, y hay algunos datos conocidos sobre ellas:

• Y: es verdadero hasta que encuentres un falso (un falso es suficiente)
• O: es falso hasta que encuentres un verdadero (un verdadero es suficiente)
• No: es lo opuesto a su argumento.

Por lo tanto, no necesitamos mantener todos los valores de cada operación para saber su resultado final. Si estamos resolviendo un Y, solo manténgalo si encontró un falso o no, si O, manténgalo si encontró verdadero o no, y si NO, entonces ya será un valor que evaluará a su opuesto.

Acercarse

Implementamos una estructura personalizada: CallStack, que tiene 2 cortes, uno para la operación y otro para el valor que vamos a evaluar.
La pila de llamadas tiene métodos:

• Push: se usa para enviar valores y operaciones a los 2 sectores que tenemos. Las operaciones envían un nuevo valor a los 2 sectores, y los valores (t of) simplemente modifican el último valor ingresado en el sector de valores.
• Pop: elimina el último valor de los 2 sectores, evalúa el valor extraído con la operación de extracción y usa el resultado para modificar el último valor nuevo después de extraerlo.
• Eval: se llama cuando es el último paréntesis de cierre para evaluar el último valor restante en el segmento de valores con la última operación restante en el segmento de operaciones.

La solución se puede optimizar más finalizando la evaluación de Ands una vez que encuentres un falso, y de Ors una vez que encuentres un verdadero, lo dejaré para que lo hagas si quieres :)

Complejidad

• Complejidad del tiempo:
  En)

• Complejidad espacial:
  En)

Código

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