ฉันกำลังพยายามสร้างตัวแปลงจาก postfix ไปเป็น infix notation และต้องการความช่วยเหลือ มีคำถามเกี่ยวกับการแปลง infix-to-postfix อยู่แล้ว ซึ่ง ให้ตัวอย่างที่ฉันไม่สามารถแปลงกลับได้ (หมายเหตุ: เครื่องหมายลบหายไปตรงนั้น!)
ต่อไปนี้เป็นเอาต์พุตของตัวแปลงของฉัน โดยที่ "คอลัมน์" ตัวแรกคืออินพุต postfix คอลัมน์ที่ 2 คือเอาต์พุต infix ของฉัน และคอลัมน์ที่ 3 คือสิ่งที่ฉันควรได้รับ(?):
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
คุณคิดว่าเป็นไปได้ที่จะแก้ปัญหานี้หรือสองบรรทัดสุดท้ายถูกแปลงอย่างถูกต้องจริง ๆ หรือไม่? คุณจะเขียนอัลกอริทึมเพื่อแก้ไขปัญหานี้อย่างไร
โปรดสมมติว่าสามารถตั้งค่าตัวดำเนินการได้มากขึ้น (ไม่เพียงแต่ + และ -) ให้เป็นทั้งเอกนารีและไบนารี โดยที่ตัวดำเนินการเอกนารีมีลำดับความสำคัญสูงกว่าไบนารี
อ้างอิง
- Ruby Quiz #148: Postfix to Infix หรือผ่านทาง Google Groups
- อัลกอริทึม Shunting-yard (C, Python, Perl) พร้อมการสนับสนุนตัวดำเนินการแบบเอกนารี บน LiteratePrograms
