이것은 제가 풀면서 즐겼던 LeetCode 문제 중 하나입니다. Golang으로 풀었고, 불과 일주일 만에 Go를 배우기 시작한 벌써 Go 초보자입니다.

직관

이 문제는 문자열을 가져와서 평가하는 계산기 프로그램을 구현하는 또 다른 버전입니다. 최종 결과를 얻을 때까지 내부 괄호를 외부 괄호로 평가하여 문제를 해결해야 합니다. 이러한 문제는 스택으로 가장 잘 설명됩니다. 새 괄호를 열 때 스택에 푸시하고 닫을 때 스택에서 팝하는 CallStack을 구현하는 것입니다. 마지막 종료 시 Eval을 호출하여 최종 결과를 얻습니다.

계산기에서는 3가지 작업을 수행할 수 있으며 이에 대해 몇 가지 알려진 사실이 있습니다.

• AND: 거짓을 찾을 때까지는 참입니다(하나의 거짓이면 충분합니다)
• OR: 참을 찾을 때까지는 거짓입니다(하나의 참이면 충분합니다)
• 아님: it의 주장과 반대입니다.

따라서 최종 결과를 알기 위해 각 작업의 모든 값을 유지할 필요가 없습니다. AND를 해결하는 경우 다음을 찾았는지 유지하세요. false인지 아닌지, OR이면 true인지 아닌지를 유지하고, NOT이면 이미 반대 값으로 평가할 하나의 값이 됩니다.

접근하다

우리는 사용자 정의 구조체인 CallStack을 구현합니다. 여기에는 2개의 슬라이스가 있습니다. 하나는 작업용이고 다른 하나는 평가할 값용입니다.
호출 스택에는 다음과 같은 메소드가 있습니다:

• 푸시: 우리가 가지고 있는 2개의 슬라이스에 값과 작업을 푸시하는 데 사용됩니다. 작업은 새 값을 2개의 조각에 푸시하고 값(t 또는 f)은 값 조각에 마지막으로 입력된 값을 수정합니다.
• 팝: 2개 조각에서 마지막 값을 제거하고, 팝된 작업으로 팝된 값을 평가하고, 그 결과를 사용하여 팝 후 새 마지막 값을 수정합니다.
• Eval: 작업 슬라이스의 마지막 남은 작업과 함께 값 슬라이스의 마지막 남은 값을 평가하기 위해 마지막 닫는 괄호일 때 호출됩니다.

거짓을 찾으면 Ands의 평가를 종료하고 Ors가 true를 찾으면 원하는 경우 수행하도록 남겨 두어 솔루션을 더욱 최적화할 수 있습니다 :)

복잡성

• 시간 복잡도:
  에)

• 공간 복잡성:
  에)

암호

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