Golang の LeetCode: ブール式の解析

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

直感

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

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

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

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

アプローチ

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

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

偽が見つかったら Ands の評価を終了し、真が見つかったら Ors の評価を終了することで、ソリューションをより最適化できます。それは必要に応じて任せておきます :)

複雑

• 時間計算量:
  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 中国語 Web サイトの他の関連記事を参照してください。