Это одна из задач LeetCode, которую мне понравилось решать. Я решил это в Golang, и я уже новичок в Go, который начал изучать его всего за одну неделю.

Интуиция

Эта проблема представляет собой еще одну версию реализации программы-калькулятора, которая принимает строку и вычисляет ее. Вам придется решать, сравнивая внутренние скобки с внешними, пока не получите окончательный результат. Эти проблемы лучше всего описываются стеком: вы просто реализуете CallStack, который при открытии новой скобки вы отправляете в стек, а при ее закрытии просто извлекаете из стека. При последнем закрытии мы вызываем Eval, чтобы получить окончательный результат.

У нас есть 3 операции, которые можно выполнить в нашем калькуляторе, и о них есть несколько известных фактов:

• И: это правда, пока вы не найдете ложь (достаточно одной ложной)
• ИЛИ: это ложь, пока вы не найдете истину (достаточно одной истины)
• Не: это противоположность аргумента it.

Таким образом, нам не нужно сохранять все значения для каждой операции, чтобы знать ее окончательный результат. Если мы решаем И, просто сохраните, если вы нашли ложно или нет, если ИЛИ, сохраните, нашли ли вы истинное или нет, а если НЕ, то это уже будет одно значение, которое вы оцените как противоположное.

Подход

Мы реализуем специальную структуру: CallStack, которая имеет два фрагмента: один для операции, а другой для значения, которое мы собираемся оценить.
В стеке вызовов есть методы:

• Push: используется для передачи значений и операций в два имеющихся у нас фрагмента. Операции помещают новое значение в два среза, а значения (t или f) просто изменяют последнее введенное значение в срезе значений.
• Pop: удалите последнее значение из двух фрагментов, оцените извлеченное значение с помощью операции извлечения и используйте результат для изменения нового последнего значения после извлечения.
• Eval: вызывается, когда это последняя закрывающая скобка для оценки последнего оставшегося значения в срезе значений с последней оставшейся операцией в срезе операций.

Решение можно более оптимизировать, прекратив вычисление Ands, как только вы обнаружите ложь, и Ors, как только вы обнаружите истину, я оставлю это вам, если хотите :)

Сложность

• Временная сложность:
  На)

• Пространственная сложность:
  На)

Код

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