วิธีคิดแบบนักวิทยาการคอมพิวเตอร์/Stacks

0
 
 35705
 2019-09-24T03:57:07Z
 
 Geonuch
 
 wikitext
 text/x-wiki
บทที่ 18 Stacks
18.1 Abstract data types
บทที่ 18 Stacks.
18.1 Abstract data types.
ชนิดข้อมูลที่คุณเคยเห็นมาทั้งหมดเป็นแบบรูปธรรม ซึ่งเราสามารถเข้าใจถึงมันได้โดยง่าย เป็นต้นว่าคลาส Card แทนตัว card ด้วย integers 2 ตัว ดังที่เคยได้กล่าวไว้แล้วมันไม่ใช่ทางเดียวที่จะแทนตัว card มันยังมีทางเลือกอื่นอีกหลายทางที่จะทำการ implementations
 abstract data type หรือ ADT คือการระบุชุดของ operations หรือ method และความหมายของ operations ( สามารถทำอะไรได้ ) แต่ไม่ได้ระบุถึง implementation ของ operations นั่นจึงเป็นสิ่งที่ทำให้มันเป็นนามธรรม
 ทำไมจึงมีประโยชน์
• มันเป็นการง่ายที่คุณเพียงแค่เจาะจงเฉพาะ algorithm ถ้าคุณสามารถใช้ operations ที่ต้องการโดยไม่ต้องคิดว่าจะต้องสร้างการทำงานของ operations นั้นเอง
• มีทางเลือกมากมายที่จะ implement ตัว ADT มันอาจเป็นประโยชน์อย่างมากที่จะเขียน algorithm ที่สามารถใช้กับ implementations ใดๆที่เป็นไปได้
• ADTs ที่รู้จักกันดีอย่าง Stack ADT ที่จะกล่าวถึงในบทนี้ซึ่งเป็น implement ที่ถูกเพิ่มเข้าไปใน standard libraries ดังนั้นเมื่อพวกมันถูกเขียนขึ้นครั้งหนึ่งแล้วก็สามารถนำไปใช้ในหลายๆโปรแกรมได้
• Operations บน ADTs เขียนขึ้นด้วย high-level language เพื่อเจาะจง และกล่าวถึงเฉพาะ algorithm
 เมื่อเราพูดเกี่ยวกับเรื่อง ADTs เราจะแยกความแตกต่างของ code ที่ใช้ ADT เรียกว่า client code และจาก code ที่ implement ADT จะเรียกว่า provider code
18.2 The Stack ADT
18.2 The Stack ADT.
ในบทนี้เราจะมาดูตัว ADT ทั่วไปอย่าง stack ซึ่ง stack ก็คือ collection ซึ่งหมายถึงโครงสร้างข้อมูลที่เก็บ element ได้หลายตัว collections อื่นๆที่เราได้เห็นมาแล้วก็คือ dictionaries และ lists
 ADT ถูกจำกัดความโดย operation ที่แสดงอยู่บนตัวมัน ซึ่งจะเรียกว่า interface ซึ่ง interface ของ stack ประกอบด้วย operations ดังนี้
 __init__ : Initialize a new empty stack.
 push: Add item ใหม่ลง stack.
 pop: Remove และ return item จาก stack ซึ่ง item ที่ return ออกมานั้นจะเป็น item ตัวสุดท้ายที่ได้ add เข้าไป
 isEmpty: ตรวจสอบว่า stack ว่างเปล่าหรือไม่
 บางครั้ง stack จะถูกเรียกว่าโครงสร้างข้อมูลแบบ LIFO คือ เข้าหลังออกก่อนเพราะ item ที่ add เข้าไปหลังสุดจะถูก remove ก่อน
18.3 Implementing stacks with Python lists
18.3 Implementing stacks with Python lists.
Operations ของ list ในภาษา Python จะมีลักษณะคล้ายกับ operations ของ stack แต่ส่วน interface ไม่เหมือนกันซะทีเดียวแต่เราสามารถเขียน code เพื่อแปลง Stack ADT มาเป็น built-in operations ได้
 ตัว code นี้เราเรียกว่า implementation ของ Stack ADT โดยทั่วๆไป implementation คือกลุ่มของ method ตอบสนอง syntactic และ semantic ความต้องการของ interface
 นี่คือ implementation ของ Stack ADT ที่ใช้ Python list
 class Stack :
 def __init__(self) :
 self.items = []
 def push(self, item) :
 self.items.append(item)
 def pop(self) :
 return self.items.pop
 def isEmpty(self) :
 return (self.items == [])
 Stack object มี attribute ที่ชื่อว่า items ก็คือ list ของ items ใน stack โดย initialization method จะกำหนดให้ items เป็น list ที่ว่างเปล่า
 เพื่อใส่ item ใหม่ลงใน stack จะใช้ append method ของ list เพื่อเพิ่มมันลงไปใน items และเพื่อเรียกข้อมูลออกมาจาก stack จะใช้ pop method ของ list เพื่องดึง item ตัวสุดท้ายออกมา
 สุดท้ายคือการตรวจสอบว่า stack นี้ว่างเปล่าหรือไม่ isEmpty จึงเปรียบเทียบว่า items ใช่ list ที่ว่างเปล่าหรือไม่
 การ implementation ที่นำเอา method มาประกอบกันอย่างง่ายด้วย method ที่มีอยู่จะเรียกว่า veneer ลองนึกภาพเหมือนในชีวิตจริง veneer คือไม้คุณภาพดีบางๆที่คลุมอยู่บนเฟอร์นิเจอร์เพื่อปกปิดไม้คุณภาพต่ำที่อยู่ภายใน Computer scientists ใช้สิ่งนี้เปรียบเทียบกับในการบรรยายถึง code เล็กๆที่ซ่อนรายละเอียดของ implementation และทำได้ง่ายกว่ามี standard และ interface มากกว่า
18.4 Pushing and popping
18.4 Pushing and popping.
Stack คือ generic data structure ซึ่งหมายถึงว่าเราสามารถเพิ่ม item ชนิดใดก็ได้เข้าไปตัวอย่างข้างล่างนี้เป็นการ pushes integers 2 ตัวและ string ใส่ลงไปใน stack
 »> s = Stack
 »> s.push(54)
 »> s.push(45)
 »> s.push("+")
 เราสามารถใช้ isEmpty และ pop เพื่อ remove และพิมพ์ค่า items ทั้งหมดใน stack
 while not s.isEmpty :
 print s.pop,
 ผลลัพธ์ก็คือ + 45 54 การพิมพ์ค่าของ stack เป็นการพิมพ์ค่าจากหลังไปหน้ามันไม่ใช่การพิมพ์ที่เป็นรูปแบบมาตราฐานของ list
 คุณลองเปรียบเทียบ code ที่ implementation ไปของ printBackward ใน Section 17.4 ทั้ง recursive version ของ printBackward และ algorithm ของ stack ทั้งคู่สามารถเข้ากันได้ ข้อแตกต่างคือ printBackward ใช้ runtime stack ในการติดตาม node ขณะที่มันเข้าไปตรวจสอบใน list และพิมพ์ค่ามาจากด้านหลัง algorithm ของ stack ก็ทำอย่างเดียวกัน เว้นแต่มันใช้ Stack object แทนที่ของ runtime stack
18.5 Using a stack to evaluate postfix
18.5 Using a stack to evaluate postfix.
ในภาษาการ programming ส่วนใหญ่ expressions ทางคณิตศาสตร์เขียนโดยใช้ operator อยู่ระหว่าง operands 2 ตัวเช่น 1+2 รูปแบบนี้เรียกว่า infix ยังมีรูปแบบหนึ่งที่ใช้ในการคำนวณเรียกว่า postfix ซึ่งมีรูปแบบเป็น operator ตามหลัง operands เช่น 1 2 +
 บางครั้งเหตุผลที่เราใช้ประโยชน์จาก postfix นั้นก็คือการใช้ natural way เพื่อประเมิน postfix expression โดยใช้ stack
• เริ่มต้นจากดูจุดเริ่มต้นของ expression และตรวจสอบดูว่าเป็น operator หรือ operand
- ถ้าเป็น operand ให้ push มันลง stack
- ถ้าเป็น operator ให้ pop ตัว operands 2 ตัวจากออกมาแล้วทำการคำนวณตาม operator แล้วจึง push ผลลัพธ์ลง stack
• เมื่อจบ expression แล้วจะได้ operand เหลืออยู่ 1 ตัวใน stack ซึ่งก็คือผลลัพธ์นั่นเอง
 ตัวอย่างที่อธิบายถึงข้อดีของ posfix คือเราไม่ต้องใช้วงเล็บในการควบคุมลำดับการคำนวณเพื่อให้ได้ผลลัพธ์ที่เหมือนกับในรูปแบบ infix เราจะต้องเขียนเป็น (1 + 2) * 3
18.6 Parsing
18.6 Parsing.
เพื่อ implement algorithm ก่อนหน้านี้ เราต้องสามารถเข้าไปดูใน string และหยุดเมื่อเจอ operands และ operators และประมวลผล example of parsing และผลลัพธ์ -- the individual chunks of the string -- เรียกว่า tokens คุณอาจจะจำคำนี้ได้ในบทที่ 1
 Python ได้เตรียม split method ไว้ใน string และ re (regular expression) modules ฟังก์ชัน string.split จะแบ่ง string เป็น list โดยใช้ single character เป็น delimiter เป็นต้นว่า
 »> import string
 »> string.split("Now is the time"," ")
 ['Now', 'is', 'the', 'time']
 ในกรณีนี้ delimiter คือ space character ดังนั้น string จึงถูกแบ่งตาม space แต่ละอัน
 ฟังก์ชัน re.split มีความสามรถมากกว่าโดยเราสามารถใช้ regular expression แทนที่ delimiter การระบุชุดของ string เราจะเรียกว่า regular expression เป็นต้นว่า [A-z] ก็คือชุดของตัวอักษรทั้งหมด [0-9] คือชุดของตัวเลขทั้งหมด ตัว ^ operator แสดงถึงการปฏิเสธ ดังนั้น [^0-9] ก็คือชุดของทุกๆ character แต่ไม่รวมตัวเลข ซึ่งเป็นรูปแบบการใช้งานที่เราต้องการในการใช้แบ่งตัว postfix expressions
 »> import re
 »> re.split("([^0-9])", "123+456*/")
 ['123', '+', '456', '*', , '/', ]
 สังเกตดูลำดับของ arguments ต่างจาก string.split ตัว delimiter จะมาก่อน string
 ผลลัพธ์ของ list ที่ได้จะมี operands 123 และ 456 และ operator คือ * และ / รวมไปถึง string ที่ว่างเปล่า 2 ตัว ซึ่งก็คือ “phantom operands” (operands ที่ไม่มีตัวตน) ซึ่งจะเกิดขึ้นเมื่อ operator ปรากฎขึ้นโดยไม่มีตัวเลขอยู่หน้าหรือหลังมัน
18.7 Evaluating postfix
18.7 Evaluating postfix.
เพื่อประเมินตัว postfix expression เราจะใช้ parser จาก section ที่แล้วและใช้ algorithm จาก section ก่อนหน้านั้น เพื่อให้ง่ายเราจะเริ่มต้นจากการ implement operator + และ * ก่อน
 def evalPostfix(expr):
 import re
 tokenList = re.split("([^0-9])", expr)
 stack = Stack
 for token in tokenList:
 if token == " or token == ' ':
 continue
 if token == '+':
 sum = stack.pop + stack.pop
 stack.push(sum)
 elif token == '*':
 product = stack.pop * stack.pop
 stack.push(product)
 else:
 stack.push(int(token))
 return stack.pop
 เงื่อนไขแรกคือการดู space และ string ที่ว่างเปล่าและ 2 เงื่อนไขถัดมาคือการรองรับ operator ตอนนี้เราสมมติให้สิ่งอื่นๆจะต้องเป็น operand แน่นอนว่ามันจะดีกว่าที่จะตรวจสอบ erroneous input และแสดง error message แต่เราจะทำมันหลังจากนี้
 ตอนนี้ลองทดสอบการประเมิน postfix จาก (56+47)*2
 »> print evalPostfix ("56 47 + 2 *")
 206
 ตอนนี้เราเข้าใกล้เพียงพอแล้ว
18.8 Clients and providers
18.8 Clients and providers.
หนึ่งในเป้าหมายหลักพื้นฐานของ ADT คือการแบ่งออกเป็น provider ผู้ซึ่งเขียน code ที่ implements ตัว ADT และ client คือผู้ที่ใช้ ADT ผู้ที่จะคอยห่วงเกี่ยวกับเรื่องของการ implementation ให้ถูกต้องก็คือ provider ในการระบุความสอดคล้องกันของ ADT และไม่เกี่ยวกับการที่จะใช้งานมันอย่างไร
 ตรงข้ามกับ client ที่คิดอยู่ตลอดว่า implementation ของ ADT ถูกต้องและไม่สนใจในเรื่องรายละเอียด เมื่อคุณใช้ Python ‘s built-in types ทำให้คุณรู้สึกได้ว่าคุณคือ client
 แน่นอนว่าเมื่อคุณ implement ตัว ADT คุณจะต้องเขียน client code เพื่อทดสอบมัน ในกรณีนี้คุณจะมี 2 บทบาทที่สามารถทำให้คุณสับสนได้ คุณจะต้องพยายามดูว่าคุณเล่นอยู่ในบทบาทใดในเวลาใดๆ
18.9 Glossary
18.9 Glossary.
abstract data type (ADT): A data type (usually a collection of objects) that is defined by a set of operations but that can be implemented in a variety of ways.
 interface: The set of operations that define an ADT.
 implementation: Code that satisfies the syntactic and semantic requirements of an interface.
 client: A program (or the person who wrote it) that uses an ADT.
 provider: The code (or the person who wrote it) that implements an ADT.
 veneer: A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client.
 generic data structure: A kind of data structure that can contain data of any type.
 infix: A way of writing mathematical expressions with the operators between the operands.
 postfix: A way of writing mathematical expressions with the operators after the operands.
 parse: To read a string of characters or tokens and analyze its grammatical structure.
 token: A set of characters that are treated as a unit for purposes of parsing, such as the words in a natural language.