Bagaimana Menghuraikan dan Membina Pokok daripada Ungkapan Aritmetik di Jawa?

Menghuraikan Ungkapan Aritmetik dan Membina Pokok daripadanya di Jawa

Artikel ini membincangkan tugas menghuraikan ungkapan aritmetik dan membina struktur data pokok yang sepadan di Jawa. Objektifnya adalah untuk memproses ungkapan seperti "(5 2)*7" menjadi pokok yang menyerupai struktur ungkapan.

Pendekatan: Menggunakan Tindanan

Untuk menghuraikan ungkapan, timbunan boleh digunakan. Pendekatan ini melibatkan pemprosesan berulang token daripada ungkapan:

• Jika kurungan pembukaan "(" ditemui, ia ditolak ke tindanan.
• Jika nombor (operand) ditemui , ia disimpan sebagai nod daun dan ditolak ke tindanan.

• Jika operator ( , -, *, /) ditemui:

  • Keutamaannya dibandingkan kepada pengendali atas pada tindanan.
  • Jika keutamaan lebih rendah atau sama, ungkapan dinilai sehingga "(" atau permulaan ungkapan sebelumnya.
  • Hasil daripada penilaian ditolak ke dalam tindanan.

Contoh: Menghuraikan "(5 2)*7"

Pertimbangkan menghuraikan ungkapan " (5 2)*7":

• "(" ditolak ke tindanan.
• "5" ditolak ke tindanan sebagai nod daun.
• " " ditolak ke tindanan.
• "2" ditolak ke tindanan sebagai nod daun.

• ")" ditemui, jadi ungkapan "5 2" dinilai:

  • Nod daun "5" dan "2" muncul daripada tindanan.
  • Nod tambahan baharu " " dicipta, dengan dua nod daun sebagai kanak-kanak.
  • Nod tambahan ditolak ke tindanan.
• "*" ditolak ke tindanan.
• "7" ditolak ke atas timbunan sebagai nod daun.

• "eof" (akhir ungkapan) ditemui, jadi ungkapan "(nod) 7" dinilai:

  • Nod pendaraban "(*nod)" dan nod daun "7" muncul daripada tindanan.
  • Nod pendaraban baharu "*" dibuat dan ditolak ke tindanan.

Struktur pokok terakhir yang diambil daripada timbunan akan sejajar dengan ungkapan asal:

    *
   / \
  +   7
 / \
5   2

Kesimpulan

Menggunakan timbunan untuk menghuraikan ungkapan aritmetik membolehkan pembinaan struktur data pokok yang cekap mewakili ungkapan tersebut. Pendekatan ini membolehkan operasi dan analisis selanjutnya dilakukan pada pokok yang dihuraikan.

Atas ialah kandungan terperinci Bagaimana Menghuraikan dan Membina Pokok daripada Ungkapan Aritmetik di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!