これは、私が解決して楽しかった LeetCode の問題の 1 つです。私はそれを Golang で解決しました。私はすでに Go の初心者で、わずか 1 週間で Golang で学習を始めました。

直感

この問題は、文字列を取得して評価する計算機プログラムの実装の別のバージョンです。最終結果が得られるまで、内側の括弧を外側の括弧に評価して解決する必要があります。これらの問題はスタックによって最もよく説明されます。新しい括弧を開くときにスタックにプッシュし、括弧を閉じるときにスタックからポップするという CallStack を実装しているだけです。最後の終了時に Eval を呼び出して最終結果を取得します。

電卓で実行できる操作は 3 つあり、それらについてはいくつかの既知の事実があります:

• AND: false が見つかるまで true (false が 1 つあれば十分)
• OR: true が見つかるまで false です (true が 1 つあれば十分です)
• Not: 議論の反対です。

したがって、最終結果を知るために各操作のすべての値を維持する必要はありません。 AND を解決している場合、見つかった場合は維持するだけです。 false かどうか、OR の場合、true が見つかったかどうかを維持します。NOT の場合、それはすでに 1 つの値になり、その反対の値に評価されます。

アプローチ

カスタム構造体 CallStack を実装します。これには 2 つのスライスがあり、1 つは操作用、もう 1 つは評価する値用です。
呼び出しスタックにはメソッドがあります:

• Push: 値と操作を 2 つのスライスにプッシュするために使用されます。操作は新しい値を 2 つのスライスにプッシュし、値 (t または f) は値スライスに最後に入力された値を変更するだけです。
• Pop: 2 つのスライスから最後の値を削除し、ポップされた値をポップ操作で評価し、その結果を使用してポップ後の new の最後の値を変更します。
• Eval: 操作スライス内の最後に残った操作を使用して値スライス内の最後に残った値を評価するために、最後の閉じ括弧のときに呼び出されます。

false が見つかったら Ands の評価を終了し、true が見つかったら 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