Bagaimanakah algoritma Shunting-yard boleh digunakan untuk menukar rentetan ungkapan matematik kepada struktur pokok dalam C ?

Menghuraikan Ungkapan Matematik dalam C Menggunakan Algoritma Shunting-yard

Dalam bidang pengaturcaraan, menyatakan pengiraan matematik yang kompleks dalam kod selalunya memerlukan penghuraian rentetan teks ke dalam perwakilan pokok dalaman. Ini memudahkan penilaian dan manipulasi seterusnya bagi ungkapan ini.

Pertimbangkan tugas menghuraikan rentetan ungkapan matematik berikut: "(a b)c-(d-e)f/g". Matlamatnya adalah untuk membina struktur pokok menggunakan kelas C untuk mewakili ungkapan ini.

Menggunakan Algoritma Shunting-yard

Algoritma Shunting-yard menyediakan strategi yang berkesan untuk menghuraikan ungkapan matematik ke dalam pokok. Algoritma ini beroperasi dalam dua fasa:

1. Tokenize Ungkapan: Pecah rentetan kepada token individunya, termasuk operan (cth., "a", "b"), operator ( cth., " ", "-") dan kurungan.

2. Bina Pokok: Gunakan dua tindanan: tindanan operator dan tindanan output. Proseskan token satu demi satu:

   • Jika token ialah operan, tolaknya ke tindanan output.
   • Jika token ialah operator, pop operator daripada tindanan operator sehingga anda menemui pengendali keutamaan yang lebih rendah atau kurungan terbuka. Tolak pengendali semasa ke tindanan operator.
   • Jika token ialah kurungan terbuka, tolaknya pada tindanan operator.
   • Jika token ialah kurungan tertutup, operator pop daripada tindanan operator sehingga anda menemui kurungan terbuka yang sepadan. Tolak subungkapan yang terhasil ke tindanan output.

Mentakrifkan Struktur Pokok

Untuk mewakili struktur pokok, takrifkan C berikut kelas:

• Exp (kelas asas)
• Terma (mewarisi daripada Exp) untuk operan
• Nod (mewarisi daripada Exp) untuk operator

Contoh Proses Penghuraian

Untuk ungkapan "(a b)c-(d-e)f/g", proses penghuraian akan diteruskan seperti berikut:

Operator Stack | Output Stack
--------------|--------------
               | a b
+             | a b +
               | a b + c
*             | a b + c *
               | a b + c * d
-             | a b + c * d -
               | a b + c * d - e
               | a b + c * (d - e)
*             | a b + c * (d - e) f
               | a b + c * (d - e) f /
               | (a + b) * c - (d - e) * f / g

Struktur pokok yang terhasil akan mempunyai bentuk berikut:

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

Atas ialah kandungan terperinci Bagaimanakah algoritma Shunting-yard boleh digunakan untuk menukar rentetan ungkapan matematik kepada struktur pokok dalam C ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!