แต็ก (Stacks)
สแต็ก (Stacks) เป็นลิสต์แบบเชิงเส้น (Linear Lists) มีโครงสร้างข้อมูลที่จัดเก็บ
ข้อมูลแบบเรียงลำดับต่อเนื่อง การเพิ่มข้อมูลลงในสแต็ก หรือการนำข้อมูลออกจากสแต็กจะกระ
ทำที่จุดปลายด้านหนึ่งซึ่งมีลักษณะเข้าออกได้ทางเดียว โดยเรียกบริเวณนั้นว่าTop ของสแต็กตัว
อย่างเช่น มีการเพิ่มข้อมูลลงในสแต็กตามลำดับดังนี้ {5, 10, 15, 20} เมื่อมีการนำข้อมูลออกก็
จะเป็นลำดับดังนี้คือ {20, 15, 10, 5} และด้วยคุณสมบัติแบบย้อนกลับด้าน (Reversing) ของ
สแต็กนี้เองจึงมักเรียกโครงสร้างข้อมูลแบบสแต็กว่า มาทีหลังแต่ออกก่อน (Last In- First
Out : LIFO)
ในความเป็นจริงการดำเนินชีวิตประจำวันของมนุษย์ได้เกี่ยวข้องกับสแต็กในรูปแบบ
ต่างๆมากมายอยู่แล้ว ยกตัวอย่างเช่น ปิ่นโต เป็นชั้นที่วางซ้อนกัน หลายๆ ชั้น เมื่อต้องการนำชั้น
ปิ่นโตออกมา สามารถนำออกมาได้ที่ละชั้นเท่านั้น นั่นหมายความว่าหากอาหารที่ต้องการทานอยู่
ลำดับล่างสุดของชั้นก็จะต้องนำชั้นของปิ่นโตที่อยู่บนชั้นสูงสุดออกไปทีละชั้น จนกระทั่งพบชั้นของ
อาหารที่ต้องการ พิจารณาจากรูปที่ 4.1 ที่นำเสนอภาพเพื่อให้เห็นโครงสร้างข้อมูลแบบสแต็กที่
กล่าวมาให้มีความชัดเจนยิ่งขึ้น
รูปที่ 4.1 สแต็ก (Stacks)
4.1 การดำเนินงานพื้นฐานของสแต็ก (Basic Stack Operations)
การดำเนินงานเกี่ยวกับโครงสร้างข้อมูลแบบสแต็ก ประกอบด้วยฟังก์ชันพื้นฐาน 3 ฟังก์
ชันดัวยกันดังนี้
1. ฟังก์ชัน Push ทำหน้าที่เพิ่มข้อมูลเข้าไปในชั้นบนสุดของแสต็กปัญหาของการ
Push ก็คือต้องมีความมั่นใจว่าภายในสแต้กนั้นมีพื้นที่ว่างพอที่จะบรรจุข้อมูลใหม่ลงไปได้ถ้าหาก
สแต็กหรือมีพื้นที่ว่างไม่เพียงพอ จะทำให้เกิดสถานะโอเวอร์โฟลว์ (Overflow State) ส่งผลให้
ไม่สามารถใส่ข้อมูลใหม่เข้าไปในสแต็กได้อีก ซึ่งโดยทั่วไปเราจะใช้ฟังก์ชัน fullStack ในการ
ตรวจสอบว่าสแต็กเต็มหรือไม่ โดยพิจารณาจากรูปที่ 4.2 ที่แสดงถึงฟังก์ชัน Push ด้วยการใส่
ข้อมูลลงในสแต็ก
รูปที่ 4.2 การPush ข้อมูลลงในสแต็ก
2. ฟังก์ชัน Pop เป็นฟังก์ชันคืนค่าข้อมูลที่อยู่บนสุดของสแต็กส่งคืนให้กับผู้ใช้ พร้อม
ทั้งลบข้อมูลรายการนั้นออกไปด้วย ส่งผลให้ข้อมูลรายการถัดไปกลีบมาอยู่ในสถานะบนสุดอีกครั้ง
และเมื่อรายการสุดท้ายในสแต็กได้ถูกนำออกไปทั้งหมด สแต็กดังกล่าวก็จะถูกกำหนดให้อยู่ใน
สถานะว่าง (EmptyState) แต่หากในขณะนั้นมีการเรียกใช้ฟังก์ชัน Pop บนสแต็กว่างเปล่าจะ
ทำให้เกิดสถานะอันเดอร์โฟลว์(Underflow State) ดังนั้นเมื่อต้องการ Pop ข้อมูลออกจาก
สแต็ก จึงจำเป็นต้องตรวจสอบก่อนว่าสแต็กนั้นว่างหรือไม่ ซึ่งโดยทั่วไปเราจะใช้ฟังก์ชัน empty
Stack ในการตรวจสอบว่าสแต็กว่างหรือไม่ โดยพิจารณาจากรูปที่ 4.3 ที่แสดงถึงฟังก์ชัน Pop
ด้วยการนำข้อมูลออกจากสแต็ก
รูปที่ 4.3 การ Pop ข้อมูลออกจากสแต็ก
3. ฟังก์ชัน Stack Top ฟังก์ชันนี้จะมีความคล้ายคลึงกับฟังก์ชัน Pop ที่คืนค่าข้อมูล
ด้วยการคัดลอกข้อมูลบนสุดของสแต็กส่งคืนให้กับผู้ใช้ แต่จะแตกต่างตรงที่ฟังก์ชัน Stack Top
นั้น จะคืนค่าข้อมูลไปยังผู้ใช้งานเท่านั้น โดยไม่มีการลบข้อมูลออกจากสแต็กแต่อย่างใด กล่าวคือ
หน้าที่ของฟังก์ชัน StackTop นั้นก็คือการอ่านข้อมูลบนสแต็กที่อยู่ลำดับบนสุดของสแต็กนั่นเอง
โดยพิจารณาจากรูปที่ 4.4 ที่แสดงถึงฟังก์ชันStack Topด้วยการอ่านข้อมูลจากสแต็กที่อยู่ใน
ลำดับสุดส่งคืนกลับไปยังผู้ใช้เพื่อนำไปใช้งานต่อไป
รูปที่ 4.4 การอ่านข้อมูลด้วย Stack Top
4.2 การสร้างสแต็ก (Stack Implementation)
เนื่องจากสแต็กเป็นโครงสร้างข้อมูลที่ภาษาคอมพิวเตอร์ไม่ได้มีมาให้เหมือนกับ
อาร์เรย์ดังนั้นจึงจำเป็นต้องสร้างขึ้นเอง โดยสามารถสร้างด้วยการแทนที่ข้อมูลสแต็กได้ 2 วิธี
ด้วยกันคือการสร้างสแต็กด้วยอาร์เรย์และการสร้างสแต็กด้วยลิงก์ลิสต์
การสร้างสแต็กด้วยอาร์เรย์
การสร้างสแต็กด้วยโครงสร้างข้อมูลแบบอาร์เรย์นั้น เป็นการจัดสรรพื้นที่หน่วยความ
จำแบบสแตติก (Static) ซึ่งต้องมีการกำหนดขนาดของสแต็กเพื่อใช้งานล่วงหน้าว่าต้องการขนาด
เท่าไรจากนั้นก็ทำการจัดสรรเนื้อที่ภายในหน่วยความจำแบบคงที่ตายตัวและด้วยโครงสร้างแบบ
อาร์เรย์ที่นำมาแทนที่ข้อมูลของสแต็ก จึงต้องจัดเก็บข้อมูลที่เป็นชนิดเดียวกัน จากรูปที่ 4.5
แสดงถึงการสร้างสแต็กด้วยอาร์เรย์
รูปที่ 4.5 การสร้างสแต็กด้วยอาร์เรย์
อย่างไรก็ตาม การเลือกโครงสร้างข้อมูลแบบอาร์เรย์มาสร้างสแต็กนั้น จะมีข้อเสียอยู่หลายประการ
ด้วยกัน คือ
- การสร้างสแต็กด้วยอาร์เรย์ต้องมีการจัดสรรพื้นที่หน่วยความจำที่แน่นอนไว้ล่วงหน้า
- กรณีการเพิ่มข้อมูลลงในสแต็กมากเกินกว่าที่กำหนดไว้จะส่งผลให้สแต็กเต็มได้
แต่ก็สามารถแก้ไขปัญหาได้ด้วยการจัดสรรเนื้อที่ภายในหน่วยความจำจำนวนมากๆ เข้าไว้
ซึ่งก็จะทวีความสิ้นเปลืองยิ่งขึ้น
- สำหรับกรณีมีข้อมูลจำนวนน้อยหรือไม่มีข้อมูลในสแต็กเลย นั่นหมายความว่าต้องเสียพื้นที่
หน่วยความจำไปโดยปริยาย
การสร้างสแต็กด้วยลิงก์ลิสต์
การสร้างสแต็กด้วยโครงสร้างข้อมูลแบบลิงก์ลิสต์จัดเป็นอีกวิธีหนึ่งที่มีประสิทธิภาพสูงซึ่ง
ลิงก์ลิสต์จะจัดสรรหน่วยความจำแบบไดนามิก (Dynamic) ดังนั้นจึงไม่ต้องกำหนดขนาดคงที่อย่าง
เช่นอาร์เรย์ กล่าวคือหน่วยความจำจะถูกจัดสรรเมื่อมีการใช้งานจริงเท่านั้น อีกทั้งยังสามารถจัดเก็บ
ข้อมูลต่างชนิดกันได้ นอกจากนี้แล้ว การสร้างสแต็กด้วยลิงก์ลิสต์ สแต็กจะไม่มีวันเต็มต่อเมื่อยังมี
เนื้อที่เพียงพอต่อการจัดสรรได้อยู่
ส่วนประกอบสำคัญของลิงก์ลิสต์ก็คือ โครงสร้างสองส่วนที่มีความแตกต่างกันคือ ส่วนหัว
(Head) และส่วนข้อมูล (Data Node) โดยโครงสร้างส่วนหัวจะประกอบไปด้วย Metadataที่เป็น
ข้อมูลเพื่อใช้อธิบายข้อมูลอีกทีหนึ่ง และพอยน์เตอร์ที่อยู่ส่วนบนสุดของสแต็ก สำหรับส่วนข้อมูลจะ
ประกอบด้วยข้อมูลพอยน์เตอร์ที่ใช้เชื่อมโยงไปยังโหนดถัดไปในสแต็ก พิจารณาจากรูปที่ 4.6 ที่
แสดงถึงการสร้างสแต็กด้วยด้วยลิงก์ลิสต์ โดยรูปที่ 4.6 นั้นคือแนวความคิดของสแต็ก และเป็นรูป
แบบของการสร้างสแต็กด้วยลิงก์ลิสต์ในเชิงกายภาพ
รูปที่ 4.6 การสร้างสแต็กด้วยลิงก์ลิสต์
4.3 การนำสแต็กไปประยุกต์ใช้กับโปรแกรม
เนื้อหาต่อไปนี้ จะกล่าวถึงการนำโครงสร้างข้อมูลแบบสแต็กไปใช้งานกับโปรแกรม
ซึ่งตามปกติการเขียนโปรแกรมมักเขียนในลักษณะโมดูลหรือโปรแกรมย่อยโดยโปรแกรมหลัก
จะทำการเรียกใช้โปรแกรมย่อยต่างๆเพื่อใช้งานดังนั้นโครงสร้างข้อมูลแบบสแต็กจะสามารถ
นำมาประยุกต์ใช้เพื่อทำงานกับกรณีดังกล่าวได้เป็นอย่างดีโดยส่วนโปรแกรมที่มีการเรียกใช้
งานโปรแกรมย่อย จะมีการ Push ลำดับคำสั่งที่ต้องประมวลผลในลำดับถัดไปไว้ในสแต็ก
เพื่อจะได้สามารถรีเทิร์นกลับมาทำงานต่อจากตัวที่เรียกได้และเมื่อมีการประมวลผลชุดคำสั่ง
ในโปรแกรมย่อยที่เรียกใช้งานจนเสร็จ ก็จะทำการ Pop ลำดับคำสั่งออกจากสแต็กเพื่อจะได้
กลับไปทำงานยังลำดับคำสั่งที่ได้เรียกใช้โปรแกรมย่อยนั้นได้ต่อไป
รูปที่ 4.7 ตัวอย่างโปรแกรมแสดงลำดับการเรียกโปรแกรมย่อยเพื่อใช้งาน
จากรูปที่ 4.7 เป็นตัวอย่างโปรแกรมแสดงลำดับการเรียกโปรแกรมย่อยเพื่อใช้งานโดย
ที่ Task A ได้เรียกใช้งาน Task B ได้มีการเรียกใช้งานTask C ในขณะที่ Task C ก็ได้เรียก
ใช้งาน Task D จนกระทั่งจบที่ Task D ก็ได้มีการรีเทิร์นกลับไปทำงานยัง Task ก่อนหน้าที่
เรียกใช้งาน จนกระทั่งจบโปรแกรมจากรูปดังกล่าว สามารถอธิบายให้เข้าใจง่ายยิ่งขึ้นได้ดังราย
ละเอียดต่อไปนี้
- Task A
ถือเป็นโปรเซสหลัก โดย ณ ขณะนี้โปรแกรมทำงานที่ Task A อยู่ (รูปที่ 4.8 (a))จาก
นั้นก็ได้มีการเรียกใช้งาน Task B ดังนั้นจึงต้องนำข้อมูลของ Task A ใส่ลงในสแต็ก (รูปที่
4.8(b))
- Task B
ในขณะที่ประมวลผลอยู่ที่ Task B ยังไม่เสร็จสิ้น ก็ได้เรียกใช้งาน Task C ดังนั้นเรา
จึงต้องใส่ข้อมูลที่จำเป็นของ Task B ลงในสแต็กเช่นกัน (รูปที่ 4.8(c))
- Task C
เมื่อ Task C เริ่มทำงานไปสักพักหนึ่ง ซึ่งยังไม่เสร็จสมบูรณ์ ก็ได้มีการรียกใช้งาน
Task D ดังนั้นจึงต้องดำเนินการใส่ข้อมูลของ Task C ลงในสแต็ก (รูปที่ 4.8 (d) ทำให้ ณ
ขณะนี้มีงานอยู่สามงานด้วยกันที่อยู่ในสแต็ก
- Task D
ในขณะที่ Task D ได้เริ่มทำงานจนกระทั่งเสร็จสมบูรณ์ ก็จะต้องรีเทิร์นกลับไปยัง
โปรเซสที่เรียกก่อนหน้า ซึ่งก็คือ Task C นั่นเอง ดังนั้นการกลับไปทำงานยัง Task C ต่อ ก็
สามารถดำเนินการได้ด้วยการ Pop สแต็กส่วนบนสุดออกมาใช้งาน (รูปที่ 4.8(e))และเมื่อ
TaskC ทำงานจนเสร็จสิ้น ก็จะทำการ Pop สแต็กTask B ที่อยู่ส่วนบนสุดของสแต็กออกมา
(รูปที่ 4.8(f)) โดยขณะนี้ลำดับโปรเซสการทำงานได้กลับมายัง Task B จนกระทั่ง Task B
ได้ทำงานต่อจนเสร็จสิ้น จึงได้ทำการPop สแต็ก Task A ที่อยู่ส่วนบนสุดออกมา (รูปที่ 4.8
(g)) ซึ่งเป็นโปรแกรมหลักออกมาทำงานต่อจนกระทั่งจบโปรแกรม
รูปที่ 4.8 แสดงถึงโปรแกรมย่อยต่างๆ ที่ Push ลงในสแต็กและ Pop
ออกจากสแต็กและสถานการณ์
4.4 การประยุกต์ใช้งานสแต็ก (Stack Applications)
ด้วยคุณสมบัติของสแต็กที่มีหลักการทำงานในรูปแบบของ LIFO นี่เอง จึงสามารถนำสแต็ก
ไปประยุกต์ใช้กับงานต่อไปนี้
การเรียงลำดับข้อมูลแบบย้อนกลับ (Reversing Data)
คือการจัดเรียงลำดับข้อมูลใหม่ ตัวอย่างเช่น ข้อมูลในสแต็กที่มีข้อมูลตัวเลขลำดับจาก Topลง
ไปคือ {4 3 2 1 } เมื่อมีการจัดเรียงใหม่ลงในอีกสแต็กหนึ่งก็จะได้ลำดับใหม่มาเป็น {1 2 3 4} เป็นต้น
รูปที่ 4.9 การเรียงลำดับข้อมูลย้อนกลับด้วยสแต็ก
เป็นการแตกข้อมูลออกเป็นส่วนๆ ให้เป็นอิสระต่อกัน เพื่อส่งไปประมวลผล ตัวอย่างเช่น การ
แปลซอร์สโค้ดให้เป็นภาษาเครื่อง ซึ่งคอมไพเลอร์จะดำเนินการแตกโปรแกรมออกเป็นส่วนๆ ให้เป็นอิส
ระกัน เช่นคำสงวน ตัวแปร และโทเค็น (Tokens) เป็นต้น นอกจากนี้แล้ว การแตกข้อมูลออกเป็นส่วนยัง
สามารถนำไปใช้กับการตรวจสอบการจับคู่ของเครื่องหมายวงเล็บในนิพจน์คณิตศาสตร์ได้อีก ด้วย
รูปที่ 4.10 การแตกข้อมูลออกเป็นส่วนๆ เพื่อตรวจสอบการจับคู่ของเครื่อง
หมายวงเล็บ
การหน่วงเวลา (Postponement)
เป็นการหน่วงเวลาของข้อมูลไว้ชั่วขณะหนึ่ง เพื่อรอการประมวลผลในช่วงจังหวะเวลาทีเหมาะ
สม ซึ่งกรณีดังกล่าว จะนำไปใช้กับการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix โดยรายละเอียดจะกล่าวใน
หัวข้อถัดไป
การย้อนรอย (Backtracking Steps)
เป็นการย้อนรอยเพื่อไปยังสถานะก่อนหน้า รวมถึงการค้นหาเส้นทางการเดินทางเพื่อไปยังเป้า
หมายปลายทาง (Goal Seeking)
รูปที่ 4.11 การค้นหาเส้นทางการเดินทางเพื่อไปยังเป้าหมาย
และด้วยตรรกะดังกล่าวสแต็กจึงมีประโยชน์มากมายต่อการนำไปประยุกต์ใช้งานได้อย่าง
หลาก หลายโดยรายละเอียดต่อไปนี้ เป็นการนำเสนอเรื่องราวเกี่ยวกับการนำสแต็กไปใช้เพื่อแปลงนิ
พจน์ Infix มาเป็นPostfix โดยก่อนที่จะเข้าสู่เนื้อหา ควรเข้าใจถึงความแตกต่างระหว่างโอเปอเรเตอร์
(Operator)ซึ่งคือตัวดำเนินการและโอเปอแรนด์ (Operand) ซึ่งคือตัวถูกดำเนินการเสียก่อนด้วย
การพิจารณานิพจน์คณิตศาสตร์จากรูปที่ 5.19
รูปที่ 4.12 นิพจน์คณิตศาสตร์ที่ประกอบไปด้วยโอเปอเรเตอร์และโอเปอร์แรนด์
โดยโอเปอเรเตอร์ก็คือเครื่องหมายการคำนวณต่างๆ เช่น + - * / ในขณะที่ตัวโอเปอแรนด์
ซึ่งเป็นตัวถูกดำเนินการนั้น อาจเป็นได้ทั้งตัวแปรหรือค่าคงที่ใดๆโดยนิพจน์ทางคณิตศาสตร์สามารถนำ
เสนอให้แตกต่างกันได้ถึง 3 รูปแบบด้วยกันดังนี้
1. นิพจน์ Infix
นิพจน์คณิตศาสตร์ที่อยู่ในรูปแบบของ Infixนั้นก็คือนิพจน์โดยทั่วไปที่เรามักใช้กับการคำนวณ
สูตรตัวเลขต่างๆ โดยโอเปอเรเตอร์จอยู่ระหว่างตัวโอเปอร์แรนด์ A+B
2. นิพจน์ Postfix
นิพจน์คณิตศาสตร์ที่อยู่ในรูปแบบของ Postfix นั้น คือนิพจน์ในรูปแบบที่โอเปอเรเตอร์จะอยู่
ข้างหลังตัวโอเปอแรนด์ AB+
3. นิพจน์ Prefix
นิพจน์คณิตศาสตร์ที่อยู่ในรูปแบบของ Prefix จะตรงกันข้ามกับ Postfixโดยจะนำโอเปอเร
เตอร์ไปไว้อยู่ข้างหน้าตัวโอเปอแรนด์ + AB
ข้อเสียประการหนึ่งของนิพจน์แบบ Infix ก็คือ จำเป็นต้องใช้เครื่องหมายวงเล็บเปิดและปิดเพื่อ
ควบคุมค่าของโอเปอเรเตอร์ ซึ่งการใช้เครื่องหมายวงเล็บ ก็เพื่อต้องการกำหนดลำดับความสำคัญของ
นิพจน์ว่าควรดำเนินการคำนวณภายในวงเล็บก่อนนั่นเอง แต่สำหรับในกรณีนิพจน์ในรูปแบบของPostfix
และ Prefix นั้นจะไม่มีความจำเป็นต้องใช้เครื่องหมายวงเล็บดังกล่าวแต่อย่างใด ซึ่งกฏเกณฑ์ในการแปลง
นิพจน์ Infix มาเป็นนิพจน์ Prefix หรือ Postfix นั้นจะใช้หลักการเดียวกัน เพียงแต่นิพจน์ Prefix จะนำ
โอเปอเรเตอร์ไว้หน้าโอเปอแรนด์ ในขณะที่นิพจน์ Postfix จะนำไปไว้ข้างหลัง
การแปลงนิพจน์ Infix มาเป็น Postfix ด้วยมือ (Manual Transformation)
คอมไพเลอร์หรือตัวแปลภาษายุคใหม่ในปัจจุบัน จะไม่สามารถแปลนิพจน์ Infixไปเป็นภาษา
เครื่องได้โดยตรง อันเนื่องมาจากการจัดลำดับความสำคัญของโอเปอเรเตอร์ที่แตกต่างกันในนิพจน์ Infix
จึงทำให้การคำนวณแต่ละเทอมในนิพจน์ไม่เป็นไปตามลำดับ ทำให้คอมไพเลอร์คำนวณหาผลลัพธ์จาก
นิพจน์ Infix ค่อนข้างยากลำบาก โดยพิจารณาจากลำดับการคำนวณของนิพจน์ Infix ด้านล่างต่อไปนี้
ก็จะรับทราบถึงเหตุผลที่คอมไพเลอร์จะไม่นำนิพจน์ Infix ไปใช้งานและยิ่งเป็นสูตรคำนวณที่ซับซ้อนก็ยิ่ง
ทวีความยุ่งยากให้กับคอมไพเลอร์ในการคำนวณหาผลลัพธ์มากเท่านั้น
อย่างไรก็ตาม คอมไพเลอร์สามารถแก้ไขปัญหาข้างต้นได้ด้วยการแปลงนิพจน์ Infix ให้มา
เป็นนิพจน์แบบ Postfix หรือ Prefix เสียก่อน โดยต่อไปนี้เราจะสาธิตหลักวิธีการแปลงนิพจน์ Infix มาเป็น
นิพจน์แบบPostfix ด้วยมือ และหลังจากนั้นจึงค่อยกล่าวรายละเอียดในส่วนของอัลกอริทึมที่แปลงนิพจน์ Infix
มาเป็น Postfix ที่สามารถนำไปใช้บนคอมพิวเตอร์ได้ต่อไป
กฎเกณฑ์สำหรับการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix ด้วยมือ สามารถดำเนินการดัง
ขั้นตอนต่อไปนี้
1. ให้ทำการใส่เครื่องหมายวงเล็บให้กับทุกๆนิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ เช่น เครื่องหมายคูณ
และหารต้องมาก่อนเครื่องหมายบวกและลบ เป็นต้น
2. ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix โดยเริ่มต้นจากนิพจน์
ที่อยู่วงเล็บในสุดก่อน จากนั้นก็ดำเนินการแปลงให้เป็นนิพจน์ Postfix ด้วยการย้ายโอเปอเรเตอร์ตรงตำ
แหน่งวงเล็บปิดของคู่นั้นๆ
3. ถอดเครื่องหมายวงเล็บทิ้งออกไปให้หมด จากกฎการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix ด้วยมือ
ตามรายละเอียดข้างต้น สามารถแสดงให้เกิดความเข้าใจได้ยิ่งขึ้นดังตัวอย่างที่ 5.1
ตัวอย่างที่ 5.1 จงแปลงนิพจน์ A + B * C มาเป็นนิพจน์ Postfix ด้วยมือ
นิพจน์ Infix ที่ให้มา A + B * C
ขั้นตอนที่ 1 ใส่วงเล็บให้ทั้งหมดตามลำดับความสำคัญ
(A +( B * C ))
ขั้นตอนที่ 2 พิจารณานิพจน์ที่อยู่วงเล็บในสุด โดยให้ย้ายเครื่องหมาย *
ไปข้างหลัง C
(A +( B C *))
จากนั้นให้ย้ายโอเปอร์เรเตอร์+ซึ่งอยู่ที่ตำแหน่งวงเล็บเปิด
ภายนอกไปยังตำแหน่งวงเล็บปิดภายนอกของคู่ตัวเอง
(A +( B C *) + )
ขั้นตอนที่ 3 ถอดเครื่องหมายวงเล็บทิ้งออกให้หมด
A B C * +
|
|---|
ตัวอย่างที่ 5.2 จงแปลงนิพจน์ 5 * 6 – 10 มาเป็นนิพจน์ Postfix ด้วยมือ
5 * 6 – 10 = ((5*6)-10)
= ((5 6 *) -10)
= ((5 6 *) 10-)
= 5 6 * 10-
|
|---|
และจากนิพจน์ Postfix ที่ได้จากตัวอย่างที่ 5.2 นั้น คือผลลัพธ์จากการเรียงลำดับตาม
กฎของ Postfixดังนั้นคอมไพเลอร์ก็สามารถทำการคำนวณหาผลลัพธ์จากนิพจน์ Postfix ได้อย่าง
ง่ายดาย นักศึกษาลองพิจารณาและทำการวิเคราะห์รายละเอียดจากรูปที่ 5.20 ต่อไปนี้ ก็จะทราบว่า
ผลจากการเรียงลำดับของนิพจน์ Postfix จะทำให้คอมไพเลอร์สามารถคำนวณหาผลลัพธ์จากสูตร
ตัวเลขตามลำดับได้ง่ายกว่านิพจน์ Infix อย่างไรโดยรายละเอียดของการหาผลลัพธ์จากนิพจน์
Postfix จะกล่าวในหัวข้อ “การหาผลลัพธ์จากนิพจน์ Postfix” ของบทนี้อีกครั้งหนึ่ง
รูปที่ 4.13 แสดงการคำนวณหาผลลัพธ์นิพจน์ Postfix ในสแต็ก
4.5 อัลกอริทึมสำหรับแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix (Algorithmic
Transformation)
การดำเนินงานด้วยการแปลงนิพจน์ Infix มาเป็น Postfixที่กระทำด้วยมือนั้นยากต่อ
การนำไปใช้บนคอมพิวเตอร์ ดังนั้นด้วยเทคนิคต่อไปนี้จะทำให้เราสามารถนำไปสร้างโปรแกรม
เพื่อใช้งานบนสแต็กได้ง่ายทีเดียวอันเนื่องมาจากคุณสมบัติการหน่วงเวลาของข้อมูลที่นำเข้าสู่
สแต็กเพื่อรอการประมวลผลในช่วงจังหวะเวลาที่เหมาะสมภายในสแต็กนี่เองที่ช่วยให้การแปลง
นิพจน์จาก Infix มาเป็น Postfix ได้โดยไม่ยาก
อัลกอริทึมการแปลงนิพจน์ Infix มาเป็น Postfix มีขั้นตอนดังนี้
1. ถ้าข้อมูลเข้าเป็นโอเปอรแรนด์ ให้เอาพุตไป Postfix
2. ถ้าข้อมูลเป็นโอเปอเรเตอร์
- ถ้าสแต็กว่าง ให้ Push ลงในสแต็ก
- ถ้าภายในสแต็กมีข้อมูลอยู่ ให้ทำการเปรียบเทียบดังนี้
- ถ้าโอเปอเรเตอร์ที่อินพุตเข้ามามีลำดับความสำคัญน้อยกว่า หรือเท่ากับโอเปอเรเตอร์ที่อยู่
ส่วนบนของสแต็ก ให้ดำเนินการ Pop สแต็กออกไปที่ Postfix โดยทำการเปรียบเทียบกับโอเปอ
เรเตอร์ที่มีอยู่ในสแต็กไปเรื่อยๆ จนกระทั่งโอเปอเรเตอร์ทีอินพุตเข้ามามีลำดับความสำคัญมาก
กว่าโอเปอเรเตอร์ในสแต็กจากนั้นให้ดำเนินการ Push โอเปอเรเตอร์ที่อินพุตเข้ามาลงในสแต็ก
- ถ้าโอเปอเรเตอร์ที่อินพุตเข้ามามีลำดับความสำคัญมากกว่าโอเปอเรเตอร์ที่อยู่ส่วนบนของ
สแต็ก ให้ดำเนินการ Push โอเปอเรเตอร์นั้นลงในสแต็ก
3. ถ้าข้อมูลเข้าเป็นเครื่องหมายวงเล็บเปิด ให้ดำเนินการPush ลงในสแต็ก
4. ถ้าข้อมูลเข้าเป็นเครื่องหมายวงเล็บปิด ให้ดำเนินการ Pop สแต็กไปยัง Postfix จนกระทั่งพบ
เครื่องหมายวงเล็บเปิด จากนั้นให้นำเครื่องหมายวงเล็บทั้งสองทิ้งไป
5. หากดำเนินการจนเสร็จสิ้นแล้วยังคงมีข้อมูลอยู่ในสแต็ก ให้ดำเนินการ Pop สแต็กที่เหลืออยู่ทั้ง
หมดไปที่ Postfix
รูปที่ 4.14 การแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix
จากรูปที่ 4.14 เป็นภาพแสดงขั้นตอนการแปลงนิพจน์ A + B * C – D /Eมาเป็น
นิพจน์Postfix ซึ่งสามารถอธิบายกระบวนการทำงานได้ดังต่อไปนี้
- เริ่มต้นด้วยการเตรียมนิพจน์ Infix สแต็กว่าง และนิพจน์ Postfix
- คัดลอกโอเปอแรนด์ตัวแรก ซึ่งก็คือ A ไปยังนิพจน์ Postfix (รูปที่ 4.15(a))
- โอเปอเรเตอร์ + ถูก Push ลงในสแต็ก (รูปที่ 4.15(b))
- โอเปอเรเตอร์ B ถูกคัดลอกไปยัง Postfix (รูปที่ 4.15 ( c))
- โอเปอเรเตอร์ * ถูกนำไปเปรียบเทียบกับโอเปอเรเตอร์ที่อยู่บนสุดของสแต็ก แต่
ด้วยลำดับ ความสำคัญของโอเปอเรเตอร์ * นั้นมีมากกว่า + ดังนั้นโอเปอเรเตอร์
* จึงถูก Push ลงในสแต็ก (รูปที่ 4.15(d))
- โอเปอเรเตอร์ตัวถัดไปคือ C ถูกคัดลอกไปยังนิพจน์ Postfix (รูปที่ 4.15(e))
- โอเปอเรเตอร์- ถูกนำไปเปรียบเทียบกับโอเปอเรชันในสแต็ก โดยลำดับความ
สำคัญของโอเปอเรชัน – น้อยกว่าโอเปอเรชัน * ดังนั้นจึง Pop สแต็กออก
ไปยัง Postfix จากนั้นก็ทำการ เปรียบเทียบลำดับความสำคัญระหว่างโอเปอเร
เตอร์–กับ +ซึ่งต่างก็มีระดับความสำคัญ เท่ากัน จึงทำการ Pop สแต็กออกไปยัง
postfix หลังากนั้นสแต็กก็จะว่าง ก็ดำเนินการ Pushโอเปอเรเตอร์ – ลงในสแต็ก
(รูปที่4.15 (f))
- นิพจน์ Infix ตัวถัดไปคือโอเปอเรแรนด์ D ให้คัดลอกไปยัง Postfix (รูปที่ 4.15 (g))
- ตัวถัดไปคือโอเปอเรเตอร์ / ให้ทำการ Push ลงในสแต็ก (รูปที่ 4.15 (h))
- นิพจน์ Infix ตัวถัดไปคือโอเปอเรแรนด์ E ให้คัดลอกไปยัง Postfix (รูปที่ 4.15 (i))
- ได้กระทำการจนกระทั่งไม่มีนิพจน์ Infix แล้ว ให้ทำการ Pop สแต็กที่เหลืออยู่ไปยัง
Postfix (รูปที่ 4.15(j))
จากขั้นตอนการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix ข้างต้น ณ ขณะนี้เรา
พร้อมที่จะทำการพัฒนาอัลกอริทึมการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix โดยในที่นี้
สมมติว่ามีเพียงโอเอเรเตอร์ 3 ตัว ซึ่งทั้งสามโอปเอเรเตอร์นั้นมีลำดับความสำคัญดังนี้
ลำดับความสำคัญ (Priority) โอเปอเรเตอร์
2 */
1 + -
0 (
|
|---|
ตัวอย่างที่ 4.3 จงแปลงนิพจน์ A*B-(C+D)+E ให้เป็นนิพจน์ Postfix
การหาผลลัพธ์จากนิพจน์ Postfix (Evaluating Postfix Expressions)
เราได้ทราบรายละเอียดแล้วว่า การนำสแต็กไปประยุกต์ใช้กับการหน่วงเวลา (Postponement) เพื่อจัดการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix ได้อย่างไร และต่อ
ไปนี้จะแสดงให้เห็นถึงการนำนิพจน์ Postfix มาหาผลลัพธ์ เพื่อจะได้ให้ทราบว่าคอมไพ
เลอร์สามารถจัดการหาผลลัพธ์จากนิพจน์ Postfix ได้สะดวกกว่านิพจน์ Infix อย่างไร
โดยในที่นี้ขอยกตัวอย่างนิพจน์ Postfix เพื่อนำไปคำนวณหาผลลัพธ์ดังนี้
A B C + *
โดยที่ A=2 B=4 และ C=6
|
|---|
หลักการหาผลลัพธ์จากนิพจน์ Postfix ก็คือ จะทำการสแกนนิพจน์ Postfix จาก
ซ้ายไปขวา โดยโอเปอแรนด์ที่พบจะถูกใส่ไว้ในสแต็กไปเรื่อยๆ จนกระทั่งพบตัวโอเปอเรเตอร์ เมื่อพบแล้วจึงดำเนินการหาผลลัพธ์จากคู่โอเปอแรนด์ที่พบก่อนหน้า ผลการคำนวณจะเป็นไป
ตามขั้นตอนดังรูปที่ 4.15 ส่วนอัลกอริทึมการหาผลลัพธ์จากนิพจน์ Postfix แสดงไว้ในอัลกอริ
ทึมที่ 4.10
รูปที่ 4.15 การคำนวณหาผลลัพธ์ของนิพจน์ Postfix
รีเคอร์ชัน (Recursion)
รีเคอร์ชัน (Recursion) เป็นหลักการที่จะนำมาใช้กับการโปรแกรมแบบ
รีเคอร์ชัน (Recursion) ซึ่งโดยปกติทั่วไป อัลกอริทึมการทำงานซ้ำๆ สามารถเขียนได้ 2
รูปแบบด้วยกันคือ
1. การวนรอบ (Iteration)
เป็นเทคนิคที่ใช้หลักการวนรอบหรือลูป (Looping) เพื่อทำกระบวนการนั้นซ้ำๆ
จนกระทั่งตรงตามเงื่อนไขการควบคุมลูปก็จะหลุดออกจากลูป
2.การเรียกตัวเอง (Recursion)
เป็นเทคนิคการวนซ้ำเพื่อทำกระบวนการหรือชุดคำสั่งนั้นซ้ำๆ ด้วยวิธีการเรียก
ตัวเองเพื่อทำซ้ำ วิธีนี้ผู้เขียนโปรแกรมจำเป็นต้องมีความรู้ในหลักการดังกล่าวเป็นอย่างดี
ซึ่งถือว่าเป็นโปรแกรมที่มีความซับซ้อนมากกว่าวิธีแรก แต่ก็มักได้มาซึ่งโปรแกรมที่มีขนาด
เล็กและกระชับมากกว่า
รีเคอร์ชัน คือกระบวนการทำงานซ้ำๆ ด้วยการใช้เทคนิคเรียกตัวเองเพื่อทำงาน
ซึ่งถือว่าเป็นสิ่งที่ค่อนข้างเข้าใจยากสำหรับผู้เริ่มต้นศึกษา โดยประเด็นของรีเคอร์ชันก็คือใน
ทุกๆครั้งของการเรียกตัวเองเพื่อใช้งาน จะต้องสามารถแก้ไขปัญหาในส่วนนั้นได้ รวมถึงการ
ลดขนาดของปัญหาลง แต่อย่างไรก็ตาม ภาษาคอมพิวเตอร์บางภาษาเท่านั้นที่สนับสนุนหลัก
การทำงานของรีเคอร์ชัน เช่น ภาษา C , JAVA และ PASCAL เป็นต้น ในขณะที่ภาษาเก่า
แก่อย่างภาษา COBOL หรือภาษา FORTRAN จะไม่สนับสนุนหลักการทำงานดังกล่าว
เนื้อหาต่อไปนี้ จะศึกษาถึงโปรแกรมแบบรีเคอร์ซีพอย่างง่าย ด้วยการใช้แฟคทอ
เรียล(Factorial) เป็นตัวอย่างของการศึกษาในครั้งนี้ โดยการคำนวณค่าแฟคทอเรียลจะกระ
ทำกับค่าเลขจำนวนเต็มบวกที่จะนำมาคูณกันตั้งแต่ 1 จนถึงค่าตัวเลขจำนวนเต็มนั้นๆ โดย
เราสามารถนิยามการทำงานของแฟคทอเรียลในรูปแบบของการทำซ้ำเป็นรอบได้ตามอัล
กอริทึมดังนี้
ตัวอย่างเช่น ให้ทำการหาค่า Factorial (4)
Factorial (4) = 4 x 3 x 2 x 1 = 24
จากตัวอย่างข้างต้นจะเห็นไดว่า มีกระบวนการทำงานแบบซ้ำๆ เกิดขึ้น ซึ่งก็คือ
ค่าของแฟคทอเรียล n จะเกิดจากการคูณกันตั้งแต่ n จนถึง 1 ซึ่งกระบวนการดังกล่าวใช้หลัก
การทำงานเป็นรอบ ดังอัลกอริทึมที่ 4.1
อัลกอริทึมที่ 4.1 Iterative Factorial Algorithm
และต่อไปนี้จะทำการนิยามการทำงานของแฟคทอเรียลตามหลักการของรี
เคอร์ชัน ซึ่งสามารถนิยามได้ดังนี้
Factorial (n) = 1 {if n = 0}
Factorial (n) = n x (Factorial (n-1)) {if n > 0}
|
|---|
โดยสมมติว่า ต้องการหาค่า Factorial(3) หรือ 3! จากนิยามข้างต้น ก็จะเป็น
ไปดังรูปที่ 4.16 โดยให้ศึกษาจากรูปที่ 4.16 อย่างระมัดระวัง จะเห็นได้ว่าจะมีการใช้รี
เคอร์ชันในการแก้ไขปัญหา 2 ประการด้วยกันคือ ประการแรกเป็นการแตกปัญหาจากบนลง
ล่าง (topto the bottom) จากนั้นจึงค่อยส่งค่าคืนกลับในลักษณะกลับขั้นตอน คือล่างขึ้นบน (bottom to the top) ซึ่งการทำกลับขั้นตอนนี้ เป็นการทำงานในรูปแบบของรีเคอร์ซีพด้วย
การนำสแต็กมาช่วยใช้งาน โดยสแต็กจะดำเนินการเก็บค่า nและ Factorial(n-1)ไว้ในแต่
ละครั้งที่มีการคำนวณหาค่าของ Factorial(n) กล่าวคือ ในขั้นตอนของการแตกประเด็นปัญ
หา ซึ่งเป็นขั้นตอนที่ยังไม่สามารถคำนวณ.ค่าได้ ดังนั้นจึงต้องทำการ Pushค่า n และ
Factorial(n-1)ไว้ในสแต็กก่อน จนกระทั่งถึงจุดที่สามารถคำนวณได้แล้ว(จุดวกคืนกลับ)
ซึ่งก็คือ Factorial(0)ที่มีค่าเท่ากับ 1 โดยหลังจากนั้นข้อมูลในสแต็กก็จะถูก Pop ออกไป
และนำค่านี้ไปแทนที่ Factorial(n-1) ไปเรื่อยๆจนกระทั่งได้ผลลัพธ์สุดท้ายคือ Factorial(n)
รูปที่ 4.16 การคำนวณหา Factorial(3) ด้วยโปรแกรมรีเคอร์ซีพ
ส่วนอัลกอริทึมการหาค่าแฟคทอเรียลด้วยหลักการรีเคอร์ชัน แสดงได้ดัง
อัลกอริทึมที่ 4.2 ซึ่งจะเห็นได้ว่าจะใช้ประโยคคำสั่ง if…else แทนการใช้ประโยคคำสั่ง
ควบคุมลูป ในขณะที่รูปที่ 4.17 จะเป็นการแสดงรายละเอียดการคำนวณค่า Factorial(3)
ด้วยอัลกอริทึมแบบรีเคอร์ซีพ
อัลกอริทึมที่ 4.2 Recursive Factorial Algorithm
รูปที่ 4.17 แสดงการทำงานของ Factorial(3) ด้วยอัลกอริทึมแบบ
รีเคอร์ชีพที่เรียกตัวเองทำงาน
