Golang의 LeetCode: 부울 표현식 구문 분석

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

직관

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

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

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

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

접근하다

우리는 2개의 슬라이스(작업용 슬라이스와 평가할 값용 슬라이스)가 있는 사용자 정의 구조체인 CallStack을 구현합니다.
호출 스택에는 다음과 같은 메서드가 있습니다.

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

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

복잡성

• 시간 복잡도:
  O(n)

• 공간 복잡성:
  O(n)

암호

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
}

위 내용은 Golang의 LeetCode: 부울 표현식 구문 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!