Stack
สแตก(Stack) หมายถึง โครงสร้างข้อมูลที่ออกแบบมาให้มีลักษณะทั้งแบบเป็นเชิงเส้น (Linear Structure) และแบบไม่เป็นเชิงเส้น (Non Linear Structure) เพราะเขียนโปรแกรมได้ทั้งการใช้อาร์เรย์ (Array) และ ลิงค์ลิสต์ (Linklist) การนำข้อมูลเข้าและออกจากสแตกจะมีลำดับการทำงานแบบเข้าหลังออกก่อน (LIFO:Last In First Out)
ลักษณะของโครงสร้างข้อมูลแบบ Stack
ข้อมูลที่เก็บใน Stack จะเก็บในลักษณะวางทับกัน เช่นเดียวกับการวางจานเรียงซ้อนกัน ข้อมูลตัวแรกจะเป็นข้อมูลที่อยู่ล่างสุดของStack และข้อมูลสุดท้ายจะเป็นข้อมูลที่อยู่บนสุด ของ Stack เมื่อมีการนำข้อมูลออกจาก
โครงสร้างข้อมูลแบบ Stack จะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ
สแตกเต็ม (Full Stack)
การแปลงนิพจน์ infix ให้เป็น postfix
1. ⤇ ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
2. ⇰ สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน
Operation ของ Stack
1. Push Stack เป็น operation สำหรับนำข้อมูลลงใน Stack
2. Pop Stack เป็น operation สำหรับนำข้อมูลออกจาก Stack 
ปัญหาที่เกิดขึ้นกับสแตก
สแตกเต็ม (Full Stack)
สแตกว่าง (Empty Stack)
การแปลงนิพจน์ infix ให้เป็น postfix
นิพจน์ infix คือนิพจน์ที่มี ตัวดำเนินการ (Operator) อยู่ระหว่างตัวถูกกระทำ (Operand) เช่น A + B เครื่องหมาย + เป็นโอเปอเรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย
นิพจน์ Postfix คือ นิพจน์คณิตศาสตร์ที่มีตัวดำเนินการอยู่หลังตัวถูกดำถูกกระทำ
ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่างๆ เรียงตามลำดับการดำเนินการก่อน-หลัง (precedence) ได้แก่
ยกกำลัง ^
คูณ หาร * , /
บวก ลบ + , -
ถ้าเครื่องหมายมีลำดับการดำเนินการเดียวกัน จะเลือกดำเนินงานของเครื่องหมายจากซ้ายไปขวา (ยกเว้น ยกกำลัง) และถ้ามีวงเล็บจะดำเนินงานสิ่งที่อยู่ในวงเล็บก่อน
ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยากคือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^) มีความสำคัญมากกว่าเครื่องหมายคูณ (*) และหาร (/) และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-) เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ)
เช่น A + B * C เครื่องจะคำนวณ B * C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า A ซึ่งจะทำงานเหมือนกับ A + (B * C) ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับความสำคัญเท่ากัน การคำนวณจะกระทำจากซ้ายไปขวา เช่น A – B + C จะทำ A – B ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับค่า C
เมื่อการประมวลผลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix เสียก่อน ซึ่งนิพจน์ postfix คือนิพจน์ที่มีโอเปอร์เรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น
AB+ หมายถึง A + B
AB- หมายถึง A - B
AB* หมายถึง A * B
AB/ หมายถึง A / B
AB^ หมายถึง A ^ B
➤ค้นหาเครื่องหมายดำเนินการทางซ้ายสุด ของนิพจน์
เมื่อการประมวลผลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix เสียก่อน ซึ่งนิพจน์ postfix คือนิพจน์ที่มีโอเปอร์เรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น
AB+ หมายถึง A + B
AB- หมายถึง A - B
AB* หมายถึง A * B
AB/ หมายถึง A / B
AB^ หมายถึง A ^ B
ตัวอย่างของการแปลงนิพจน์ Infix เป็น Postfix
นิพจน์ Infix : A – B * C
INPUT
|
STACK
|
OUTPUT
|
A
|
A
| |
-
|
-
|
A
|
B
|
-
|
AB
|
*
|
-*
|
AB
|
C
|
-*
|
ABC
|
ABC*-
|
สรุปขั้นตอนในการหาผลลัพธ์ของนิพจน์ Postfix
➤ค้นหาเครื่องหมายดำเนินการทางซ้ายสุด ของนิพจน์
➤เลือกตัวถูกดำเนินการ2ตัวอยู่ติดกับเครื่องหมายดำเนินการทางซ้าย
➤ประมวลผลตามเครื่องหมายดำเนินการนั้น
➤แทนที่เครื่องหมายดำเนินการและตัวถูกดำเนินการ ด้วยผลลัพธ์ที่ได้
ไม่มีความคิดเห็น:
แสดงความคิดเห็น