Este é um dos problemas do LeetCode que gostei de resolver. Resolvi em Golang e já sou um novato em Go, que comecei a aprender nele há apenas uma semana.

Intuição

Este problema é outra versão da implementação de um programa de calculadora que pega uma string e a avalia. Você tem que resolver avaliando os parênteses internos com os externos até obter o resultado final. Esses problemas são melhor descritos por uma pilha, você está apenas implementando um CallStack que ao abrir um novo parêntese, você faz Push para a pilha, e ao fechá-lo você apenas faz Pop da pilha. No último fechamento chamamos Eval para obter o resultado final.

Temos 3 operações que podem ser feitas em nossa calculadora, e existem alguns fatos conhecidos sobre elas:

• AND: é verdadeiro até você encontrar um falso (um falso é suficiente)
• OU: é falso até você encontrar um verdadeiro (um verdadeiro é suficiente)
• Não: é o oposto do seu argumento.

Portanto, não precisamos manter todos os valores de cada operação para saber seu resultado final. Se estivermos resolvendo um AND, apenas mantenha se você encontrou um falso ou não, se OR, mantenha se você encontrou um verdadeiro ou não, e se NOT, então já será um valor que você avaliará como oposto.

Abordagem

Implementamos uma estrutura customizada: CallStack, que possui 2 fatias, uma para a operação e outra para o valor que iremos avaliar.
A pilha de chamadas possui métodos:

• Push: usado para enviar valores e operações para as 2 fatias que temos. As operações enviam um novo valor para as 2 fatias e os valores (t ou f) apenas modificam o último valor inserido na fatia de valores.
• Pop: remova o último valor das 2 fatias, avalie o valor exibido com a operação popped e use o resultado para modificar o novo último valor após o popping.
• Eval: chamado quando é o último parêntese de fechamento para avaliar o último valor restante na fatia de valores com a última operação restante na fatia de operações.

A solução pode ser mais otimizada finalizando a avaliação de Ands assim que encontrar um falso, e de Ors quando encontrar um verdadeiro, deixarei isso para você fazer se quiser :)

Complexidade

• Complexidade de tempo:
  Sobre)

• Complexidade do espaço:
  Sobre)

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