สรุป สแตก(Stack)
การเพิ่มข้อมูลในสแตก (pushing stack)
การเพิ่มข้อมูลเข้าสแตก หมายถึงการเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูลสุดท้ายในสแตกจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก ความหมายของคำว่า สแตกเต็ม คือท๊อปของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่าท๊อปเป็นศูนย์ เมื่อสแตกเต็มค่าท๊อปเป็น N ดังนั้นเมื่อท๊อปชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีก
นิยาม push(S,x)
ถ้าให้ S เป็นสแตก และ X เป็นข้อมูล ขบวนการ push (S,X) หมายถึง การ push ข้อมูล X ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า TOP เป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า Top จะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push
การดึงข้อมูลจากสแตก (Popping Stack)
การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือที่ชี้ด้วยท๊อปออกจากสแตก จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง
นิยาม pop(S)
ถ้าให้ S เป็นสแตก ขบวนการ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้นถ้านำคำสั่ง X= pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกมา และใส่ค่าไว้ที่ X หรือการเซตค่า X ให้เท่ากับข้อมูลที่ดึงจากสแตก
การว่างของสแตก
นิยาม empty(s)
ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่าง
การแปลงนิพจน์ Infix ให้เป็น Postfix
ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
Operator คือเครื่องหมายกระทำ + - * / ^
Operand คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C
ลำดับความสำคัญ Operator
เครื่องหมายยกกำลัง ^
เครื่องหมายคูณกับหาร *,/
เครื่องหมายบวกกับลบ +,-
เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C
การเพิ่มข้อมูลในสแตก (pushing stack)
การเพิ่มข้อมูลเข้าสแตก หมายถึงการเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูลสุดท้ายในสแตกจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก ความหมายของคำว่า สแตกเต็ม คือท๊อปของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่าท๊อปเป็นศูนย์ เมื่อสแตกเต็มค่าท๊อปเป็น N ดังนั้นเมื่อท๊อปชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีก
นิยาม push(S,x)
ถ้าให้ S เป็นสแตก และ X เป็นข้อมูล ขบวนการ push (S,X) หมายถึง การ push ข้อมูล X ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า TOP เป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า Top จะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push
การดึงข้อมูลจากสแตก (Popping Stack)
การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือที่ชี้ด้วยท๊อปออกจากสแตก จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง
นิยาม pop(S)
ถ้าให้ S เป็นสแตก ขบวนการ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้นถ้านำคำสั่ง X= pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกมา และใส่ค่าไว้ที่ X หรือการเซตค่า X ให้เท่ากับข้อมูลที่ดึงจากสแตก
การว่างของสแตก
นิยาม empty(s)
ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่าง
การแปลงนิพจน์ Infix ให้เป็น Postfix
ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
Operator คือเครื่องหมายกระทำ + - * / ^
Operand คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C
ลำดับความสำคัญ Operator
เครื่องหมายยกกำลัง ^
เครื่องหมายคูณกับหาร *,/
เครื่องหมายบวกกับลบ +,-
เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C
ไม่มีความคิดเห็น:
แสดงความคิดเห็น