LeetCode dalam Golang: Menghuraikan Ungkapan Boolean

Ini adalah salah satu masalah LeetCode yang saya suka selesaikan. Saya menyelesaikannya di Golang, dan saya sudah pun seorang pemula Go, yang mula belajar di dalamnya sejak seminggu sahaja.

Intuisi

Masalah ini ialah versi lain untuk melaksanakan program kalkulator yang mengambil rentetan dan menilainya. Anda perlu menyelesaikannya dengan menilai kurungan dalam kepada yang luar sehingga anda mendapat keputusan akhir. Masalah ini paling baik diterangkan oleh timbunan, anda hanya melaksanakan CallStack yang apabila membuka kurungan baharu, anda Tekan ke timbunan, dan apabila menutupnya anda hanya Pop daripada timbunan. Pada penutupan terakhir kami memanggil Eval untuk mendapatkan keputusan akhir.

Kami mempunyai 3 operasi yang boleh dilakukan dalam kalkulator kami, dan terdapat beberapa fakta yang diketahui tentangnya:

• DAN: ia adalah benar sehingga anda mendapati yang palsu (satu palsu sudah memadai)
• ATAU: ia adalah palsu sehingga anda mendapati yang benar (yang benar sudah memadai)
• Bukan: ia adalah bertentangan dengan hujahnya.

Jadi, kita tidak perlu mengekalkan semua nilai untuk setiap operasi untuk mengetahui ia adalah hasil akhir. Jika kami menyelesaikan DAN, hanya kekalkan jika anda menemui palsu atau tidak, jika ATAU, kekalkan jika anda menemui yang benar atau tidak, dan jika TIDAK, maka nilai itu sudah menjadi satu nilai yang anda akan nilaikan sebagai nilai yang bertentangan.

Pendekatan

Kami melaksanakan struct tersuai: CallStack, yang mempunyai 2 keping, satu untuk operasi dan satu untuk nilai yang akan kami nilai.
Timbunan panggilan mempunyai kaedah:

• Tekan: digunakan untuk menolak nilai & operasi kepada 2 keping yang kita ada. Operasi menolak nilai baharu kepada 2 keping, dan nilai (t atau f) hanya mengubah suai nilai yang dimasukkan terakhir dalam kepingan nilai.
• Pop: alih keluar nilai terakhir daripada 2 keping, nilai nilai yang muncul dengan operasi yang muncul dan gunakan hasilnya untuk mengubah suai nilai terakhir baharu selepas muncul.
• Eval: dipanggil apabila kurungan penutup terakhir untuk menilai baki nilai terakhir dalam kepingan nilai dengan baki operasi terakhir dalam kepingan operasi.

Penyelesaian boleh lebih dioptimumkan dengan menamatkan penilaian Ands sebaik sahaja anda menemui yang palsu, dan Ors sebaik sahaja anda menemui yang benar, saya akan menyerahkannya kepada anda jika anda mahu :)

Kerumitan

• Kerumitan masa:
  O(n)

• Kerumitan ruang:
  O(n)

Kod

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
}

Atas ialah kandungan terperinci LeetCode dalam Golang: Menghuraikan Ungkapan Boolean. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!