เรื่อง สแตก(ต่อ)
การใช้ สแตก เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์รูปแบบนิพจน์ทางคณิตศาสตร์• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+การแปลงจาก infix เป็น postfix Stack มีการทำงานแบบ LIFO ถูกนำมาอธิบายการทำงานของการแปลงจาก infix เป็น postfix อยู่เสมอ โดยพิจารณาน้ำหนักของเครื่องหมายในนิพจน์ และเครื่องหมายที่ถูกกระทำก่อนไปหลังคือ1. วงเล็บ Parenthesis ()2. ยกกำลัง Exponentiation ^ (Left to Right)3. คูณและหาร Multiplication *, Division / (Left to Right)4. บวกและลบ Addition +, Subtraction - (Left to Right) กฎเกี่ยวกับการแปลง1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้2.1 ถ้าสแตกว่าง ให้ push operator ลงในสแตก2.2 ถ้าสแตกไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตก- ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตกให้ push ลงสแตก- ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตกให้ pop สแตกออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตก แล้วจึง push operator ที่เข้ามานั้นลงสแตก3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตกไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตกไปเป็นผลลัพธ์จนกว่าสแตกจะว่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น