Postfix untuk diinfikskan dengan operator unary/binary

Saya mencoba membuat konverter dari notasi postfix ke notasi infix dan butuh bantuan. Sudah ada pertanyaan tentang konversi infix-to-postfix, yang mana memberi contoh saya gagal mengkonversi kembali. (Catatan: tanda minus tidak ada di sana!)

Berikut ini adalah output dari konverter saya, di mana "kolom" pertama adalah input postfix, kolom ke-2 adalah output infix saya, dan kolom ke-3 adalah apa yang mungkin harus saya dapatkan (?):

2 -                      =   - 2                           =?    - 2                       true
1 + 2 +                  =   + 1 + 2                       =?    + 1 + 2                   true
1 + 2 + +                =   + (+ 1 + 2)                   =?    + 1 + + 2                 false
1 + 2 + + 3 - - 4 - -    =   - (- (+ (+ 1 + 2) - 3) - 4)   =?    + 1 + + 2 - - 3 - - 4     false

Menurut Anda apakah masalah ini dapat diselesaikan, atau dua baris terakhir benar-benar dikonversi dengan benar? Bagaimana Anda menulis algoritma untuk mengatasi masalah ini?

Harap asumsikan bahwa lebih banyak operator (tidak hanya + dan -) yang dapat ditetapkan sebagai unary dan biner, di mana operator unary memiliki prioritas lebih tinggi daripada operator biner.

Referensi

  1. Ruby Quiz #148: Postfix ke Infix, juga melalui Google Grup
  2. Algoritma shunting-yard (C, Python, Perl) dengan dukungan operator unary di LiteratePrograms

c c# infix-notation postfix-notation shunting-yard
person Andrei    schedule 09.08.2010    source sumber
comment
Saya bukan ahli tetapi notasi infiks tidak seharusnya menggunakan tanda kurung? Kolom ke-3 bagi saya tidak terlihat seperti notasi infiks dan bersifat ambigu.   -  person dierre    schedule 11.08.2010

Jawaban (1)


arrow_upward
1
arrow_downward

Notasi postfix tidak memiliki konsep prioritas, karena operan untuk operator mana pun selalu merupakan nilai N teratas di tumpukan (yang kemudian digantikan oleh hasil dari operator tersebut.

Salah satu masalah dengan notasi postfix adalah notasi ini tidak dapat menangani dengan baik simbol operator yang dapat merujuk ke operator berbeda tergantung pada jumlah operan (seperti -, yang dapat menunjukkan minus unary atau biner). Satu-satunya jalan keluarnya adalah memastikan setiap operator memiliki simbol unik yang mewakilinya.

person Bart van Ingen Schenau    schedule 25.08.2010