Bagaimanakah Algoritma Shunting-Yard boleh digunakan untuk menghuraikan ungkapan matematik dalam C dengan cekap?

Menghuraikan Ungkapan Matematik dalam C

Untuk menghuraikan ungkapan matematik dengan cekap, perwakilan berstruktur, seperti pokok penghuraian, adalah penting. Mari kita pertimbangkan masalah mewakili ungkapan "(a b)c-(d-e)f/g" sebagai pokok.

Algoritma Shunting-Yard

Algoritma Shunting-yard ialah pendekatan yang terkenal untuk menghuraikan ungkapan matematik. Ia mengikut langkah berikut:

1. Imbasan Input: Imbas aksara ungkapan mengikut aksara dan kenal pasti token (cth., operator, operan, kurungan).
2. Timbunan Pengendali: Cipta tindanan untuk menyimpan pengendali.
3. Baris Gilir Output: Buat baris gilir untuk menyimpan ungkapan yang dihuraikan.

4. Pemprosesan: Untuk setiap token yang ditemui:

   • Operan: Tambahkan operan pada baris gilir output.
   • Kurungan Kiri: Tolak ia pada tindanan operator.
   • Kurung Kanan: Pop operator daripada tindanan sehingga kurungan kiri ditemui dan tambahkannya pada baris gilir output.

   • Operator:

     • Jika tindanan operator kosong atau mengandungi hanya kurungan, tolak operator ke atas tindanan.
     • Jika tidak, keluarkan pengendali keutamaan yang lebih tinggi daripada tindanan dan tambahkannya pada baris gilir output sehingga tindanan operator kosong atau operator seterusnya mempunyai keutamaan yang lebih tinggi.
     • Kemudian, tolak operator semasa ke tindanan.
5. Timbunan Siram: Selepas memproses semua token, keluarkan semua operator daripada tindanan dan tambahkannya pada baris gilir output.

Contoh

Menggunakan algoritma Shunting-yard dengan ungkapan "(a b)c-(d-e)f/g" menghasilkan pokok berikut:

Node(+:
  - Node(a)
  - Node(b))
- Node(*:
  - Node(c)
  - Node(-:
    - Node(d)
    - Node(e))
  - Node(/:
    - Node(f)
    - Node(g)))

Pilihan Lain

Selain algoritma Shunting-yard, anda juga boleh menulis tatabahasa formal dan menggunakan perpustakaan penghuraian. Tatabahasa ungkapan penghuraian (PEG) sesuai untuk tujuan ini dan pustaka C/C wujud untuk penghuraian PEG.

Atas ialah kandungan terperinci Bagaimanakah Algoritma Shunting-Yard boleh digunakan untuk menghuraikan ungkapan matematik dalam C dengan cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!