Menghuraikan Ungkapan Boolean

1106. Menghuraikan Ungkapan Boolean

Kesukaran: Sukar

Topik: Rentetan, Tindanan, Rekursi

ungkapan boolean ialah ungkapan yang menilai sama ada benar atau palsu. Ia boleh dalam salah satu bentuk berikut:

• 't' yang dinilai benar.
• 'f' yang bernilai palsu.
• '!(subExpr)' yang menilai kepada BUKAN logik ungkapan dalam subExpr.
• '&(subExpr₁, subExpr₂, ..., subExpr_n)' yang menilai kepada logik DAN dalam ungkapan subExpr₁, subExpr₂, ..., subExpr_n di mana n >= 1.
• '|(subExpr₁, subExpr₂, ..., subExpr_n)' yang menilai kepada logik ATAU dalam ungkapan subExpr₁, subExpr₂, ..., subExpr_n di mana n >= 1.

Memandangkan ungkapan rentetan yang mewakili ungkapan boolean, kembalikan penilaian ungkapan itu.

Ia adalah dijamin bahawa ungkapan yang diberikan adalah sah dan mengikut peraturan yang diberikan.

Contoh 1:

• Input: ungkapan = "&(|(f))"
• Output: palsu
• Penjelasan:
  • Pertama, nilaikan |(f) --> f. Ungkapan itu kini "&(f)".
  • Kemudian, nilaikan &(f) --> f. Ungkapan itu kini "f".
  • Akhir sekali, kembalikan palsu.

Contoh 2:

• Input: ungkapan = "|(f,f,f,t)"
• Output: benar
• Penjelasan: Penilaian (salah ATAU palsu ATAU palsu ATAU benar) adalah benar.

Contoh 3:

• Input: ungkapan = "!(&(f,t))"
• Output: benar
• Penjelasan:
  • Pertama, nilai &(f,t) --> (salah DAN benar) --> palsu --> f. Ungkapan itu kini "!(f)".
  • Kemudian, nilaikan !(f) --> BUKAN palsu --> benar. Kami kembali benar.

Kekangan:

• 1 <= ekspresi.panjang <= 2 * 10⁴
• ungkapan[i] ialah satu aksara berikut: '(', ')', '&', '|', '!', 't', 'f' dan ','.

Petunjuk:

1. Tulis fungsi "parse" yang memanggil fungsi pembantu "parse_or", "parse_and", "parse_not".

Penyelesaian:

Kami akan memecahkan penyelesaian kepada fungsi yang lebih kecil yang mengendalikan penghuraian dan menilai pelbagai jenis ungkapan: parse_or, parse_and, parse_not, dan fungsi parse utama yang mengendalikan penghuraian ungkapan secara rekursif. Kami akan menggunakan timbunan untuk menjejaki ungkapan bersarang dan menilainya langkah demi langkah.

Pendekatan:

1. Penghuraian dan Pengulangan:

   • Gunakan tindanan untuk menjejaki ungkapan apabila menemui kurungan bersarang.
   • Proses aksara secara berurutan dan uruskan timbunan untuk penilaian bersarang.
   • Apabila menghadapi kurungan penutup ), ekstrak set ungkapan terakhir dan gunakan operasi logik (&, |, atau !).

2. Fungsi Pembantu:

   • parse_or: Menilai |(expr1, expr2, ..., exprN) dengan mengembalikan benar jika sekurang-kurangnya satu sub-ungkapan adalah benar.
   • parse_and: Menilai &(expr1, expr2, ..., exprN) dengan mengembalikan benar hanya jika semua subungkapan adalah benar.
   • parse_not: Menilai !(expr) dengan mengembalikan yang bertentangan dengan sub-ungkapan.

3. Pengendalian Ekspresi:

   • Aksara tunggal seperti t dan f diterjemahkan terus kepada benar dan palsu.
   • Apabila operasi ditemui (&, |, !), ungkapan dalaman dinilai berdasarkan peraturan masing-masing.

Mari laksanakan penyelesaian ini dalam PHP: 1106. Menghuraikan Ungkapan Boolean

  
  
  Penjelasan:




Fungsi Utama (parseBooleanExpression):


Lelaran melalui ungkapan dan menolak aksara ke timbunan.
Apabila menemui a ), ia mengumpul semua elemen di dalam kurungan dan menilainya berdasarkan operasi (&, |, !).
Menukar hasil kepada 't' (benar) atau 'f' (salah) dan menolaknya kembali ke tindanan.







Fungsi Pembantu:



parse_and: Mengembalikan benar jika semua subungkapan adalah 't' (benar).

parse_or: Mengembalikan benar jika mana-mana sub-ungkapan ialah 't'.

parse_not: Membalikkan nilai boolean sub-ungkapan tunggal.








  
  
  Contoh Panduan:




Input: "&(|(f))"


Pemprosesan tindanan:



&, (, |, (, f, ), ) → Ungkapan dalam |(f) dinilai kepada f.
Menghasilkan &(f), yang menilai kepada f.


Output: palsu.



Input: "|(f,f,f,t)"


Menilai | operasi:


Mencari satu 't', dengan itu dinilai benar.


Output: benar.



Input: "!(&(f,t))"

Pemprosesan tindanan:



!, (, &, (, f, ,, t, ), ) → &(f,t) menilai kepada f.

!(f) kemudiannya dinilai sebagai benar.


Output: benar.





  
  
  Kerumitan:




Kerumitan Masa: O(N), dengan N ialah panjang ungkapan. Setiap aksara diproses beberapa kali terhad.

Kerumitan Ruang: O(N), disebabkan timbunan yang digunakan untuk menjejaki ungkapan bersarang.


Penyelesaian ini sangat sesuai untuk kekangan dan harus mengendalikan saiz input dengan berkesan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

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