การแยกวิเคราะห์นิพจน์ในโครงสร้างข้อมูล: ประเภทของสัญกรณ์ การเชื่อมโยง และลำดับความสำคัญ

การแยกวิเคราะห์ เป็นกระบวนการของการวิเคราะห์สตริงของสัญลักษณ์ ซึ่งแสดงเป็นภาษาธรรมชาติหรือภาษาคอมพิวเตอร์ที่สอดคล้องกับไวยากรณ์ที่เป็น ทางการ การแยกวิเคราะห์นิพจน์ในโครงสร้างข้อมูล หมายถึงการประเมินนิพจน์ทางคณิตศาสตร์และตรรกะ ขั้นแรก มาดูวิธีการเขียนนิพจน์เลขคณิต:

• 9+9
• Cb

นิพจน์สามารถเขียนด้วยค่าคงที่ ตัวแปร และสัญลักษณ์ที่สามารถทำหน้าที่เป็นตัวดำเนินการหรือวงเล็บได้ นิพจน์ทั้งหมดนี้ต้องเป็นไปตามชุดของกฎเฉพาะ ตามกฎนี้ การแยกวิเคราะห์นิพจน์จะทำโดยใช้ไวยากรณ์

นิพจน์ทางคณิตศาสตร์จะแสดงในรูปแบบของสัญกร ณ์ ตอนนี้ มีสามวิธีในการเขียนนิพจน์ในเลขคณิต:

• สัญกรณ์ Infix
• คำนำหน้า (ภาษาโปแลนด์) สัญกรณ์
• Postfix (ย้อนกลับ-โปแลนด์) สัญกรณ์

อย่างไรก็ตาม เมื่อเขียนนิพจน์แล้ว ผลลัพธ์ของนิพจน์ที่ต้องการจะยังคงเหมือนเดิม ก่อนเริ่มต้นใช้งานประเภท Notation มาดูกันว่า Associativity และ Precedence อยู่ใน นิพจน์ Parsing ใน Data Structure อย่างไร

หากคุณเป็นมือใหม่และสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับวิทยาศาสตร์ข้อมูล ลองดูหลักสูตรวิทยาศาสตร์ข้อมูลของเราจากมหาวิทยาลัยชั้นนำ

อ่าน: กราฟในโครงสร้างข้อมูล

สมาคม

ก่อนที่คุณจะเริ่มต้น คุณต้องรู้ว่าคุณสมบัติการเชื่อมโยงคืออะไร มันให้กฎแก่คุณในการจัดเรียงวงเล็บใหม่ในนิพจน์เพื่อให้หลักฐานที่ถูกต้อง ซึ่งหมายความว่าการจัดเรียงใหม่ของวงเล็บเหลี่ยมจำเป็นต้องให้ค่าเดียวกับสมการหลัก มันมีกฎที่ถูกต้องเพื่อแทนที่ตัวดำเนินการ

ในนิพจน์ที่มีตัวดำเนินการตั้งแต่สองตัวขึ้นไป การดำเนินการที่ดำเนินการนั้นไม่สำคัญ เว้นแต่ว่าลำดับของตัวถูกดำเนินการจะไม่ถูกสับเปลี่ยน ถ้านิพจน์เขียนโดยใช้วงเล็บและ infix การเปลี่ยนตำแหน่งจะไม่เปลี่ยนค่า

เนื่องจากในภาษาอินโด-ยูโรเปียน นิพจน์จะถูกอ่านจากซ้ายไปขวา ตัวดำเนินการ infix ส่วนใหญ่จะสัมพันธ์กันทางซ้าย ตัวดำเนินการจะถูกประเมินในลำดับความสำคัญเดียวกัน การเพิ่มขึ้นของอำนาจเป็นกฎที่ใช้ในการพิจารณาตัวดำเนินการ infix ตัวดำเนินการคำนำหน้ามักจะสัมพันธ์กัน

ในบางภาษา ตัวดำเนินการและตัวถูกดำเนินการจะได้รับค่าเท่ากัน โดยที่การเชื่อมโยงไม่ถือว่าทำให้ลำดับภาษานี้มีความชัดเจน ในขณะที่ในบางภาษา โอเปอเรเตอร์จะไม่สัมพันธ์กัน ทำให้การใช้นิพจน์ที่ซับซ้อนจำเป็นสำหรับการใช้วงเล็บ ซึ่งจะเพิ่มความซับซ้อนให้กับโปรแกรมเมอร์

ลำดับความสำคัญในโครงสร้างข้อมูล

ลำดับความสำคัญหมายถึงสิ่งที่ตัวดำเนินการต้องปฏิบัติตามในคำสั่งของนิพจน์ โดยทั่วไปจะใช้ในขณะที่ทำงานกับ Infix Notation

ในสถานการณ์ของ ตัวถูกดำเนิน การ <operator> <operand> <operator> ระหว่างตัวดำเนินการทั้งสอง การกำหนดค่าตัวดำเนินการค่อนข้างยุ่งยาก ดังนั้น จึงมีการปฏิบัติตามกฎลำดับความสำคัญของโอเปอเรเตอร์สำหรับการคำนวณ เช่น ที่นี่ การคูณมีความสำคัญสูงกว่า และดำเนินการบวกในภายหลัง

• กฎที่พบบ่อยที่สุดแต่ไม่ชัดเจนนักคือต้องดำเนินการคูณและหารก่อนการบวกและการลบ โดยทั่วไปแล้ว สิ่งเหล่านี้จะถูกรวบรวมในลักษณะเดียวกัน ดังนั้นจึงมีความสำคัญเท่าเทียมกันสำหรับผู้ดำเนินการทั้งหมด
• เมื่อพิจารณาการดำเนินการนี้ในรูปแบบลอจิคัล ความผันแปรจะเห็นได้ใน “และ” และ “หรือ” หลายภาษาให้ความสำคัญเท่าเทียมกัน โดยที่การดำเนินการ "หรือ" จะได้รับลำดับความสำคัญที่สูงกว่า บางภาษาพิจารณาการคูณหรือ "&" "&" บวกด้วย "หรือ" ลำดับความสำคัญเท่ากัน โดยที่ภาษาส่วนใหญ่จัดให้มีการดำเนินการทางคณิตศาสตร์ที่มีลำดับความสำคัญสูงสุด
• การโอเวอร์โหลดเกิดขึ้นเนื่องจากไม่มีการจัดสรรลำดับความสำคัญอย่างเหมาะสม หลายภาษาให้การปฏิเสธ (จริง/เท็จ) ลำดับความสำคัญสูงกว่านิพจน์พีชคณิตเวกเตอร์ ในขณะที่บางภาษามีลำดับความสำคัญเท่ากัน

อ่านเพิ่มเติม: แนวคิดโครงการโครงสร้างข้อมูล

ประเภทของสัญกรณ์

ตอนนี้ให้เราเรียนรู้ว่าตำแหน่งของโอเปอเรเตอร์ตัดสินใจประเภทของสัญกรณ์ได้อย่างไร

1. สัญกรณ์ Infix

ใน Infix Notation ตัวดำเนินการจะถูกใช้ระหว่างตัวถูกดำเนินการ ในขณะที่อ่านนิพจน์ Infix Notation นั้นค่อนข้างง่ายสำหรับมนุษย์ แต่จะใช้เวลาและพื้นที่มากในการประมวลผลอาร์กิวเมนต์ infix เมื่อพูดถึงอัลกอริธึมของคอมพิวเตอร์ เช่น p + q

<ตัวถูกดำเนินการ> <ตัวดำเนินการ> <ตัวถูกดำเนินการ>

Infix Notation ต้องการข้อมูลเพิ่มเติมเพื่อดำเนินการประเมิน กฎถูกสร้างขึ้นในภาษานิพจน์โดยใช้ตัวดำเนินการ Associativity , ตัวอย่างเช่น: p * ( q + r ) / s

• กฎการเชื่อมโยงแนะนำว่านิพจน์จำเป็นต้องดำเนินการจากซ้ายไปขวา เช่น การคูณด้วย p ก่อนการหารของ q
• ในทำนองเดียวกัน กฎสำหรับลำดับความสำคัญแนะนำว่าจะดำเนินการคูณและหารก่อนดำเนินการบวกและลบ

2. สัญกรณ์คำนำหน้า

โอเปอเรเตอร์ในที่นี้เขียนขึ้นก่อน ตามด้วยตัวถูกดำเนินการ มันยังถูกตั้งชื่อเป็นสัญกรณ์โปแลนด์ เช่น +pq

<โอเปอเรเตอร์> <ตัวถูกดำเนินการ> <ตัวถูกดำเนินการ>

เช่น p * ( q + r ) / s

การประเมินจะต้องดำเนินการจากซ้ายไปขวา และวงเล็บจะไม่เปลี่ยนแปลงหรือเปลี่ยนรูปแบบสมการ ในที่นี้จำเป็นต้องเติมให้สมบูรณ์ก่อนการคูณเพราะตำแหน่ง “+” อยู่ทางซ้ายของ “*”

ที่นี่ ตัวดำเนินการทุกคนดำเนินการกับค่าที่อยู่ทางซ้ายของค่าเหล่านั้นทันที ตัวอย่างเช่น "+" ด้านบนใช้ "q" และ "r" เราสามารถสรุปวงเล็บเพื่อให้สิ่งนี้ชัดเจน:

((p (qr +) *) s /)

ดังนั้น “( )” จะพิจารณาและใช้ค่าทั้งสองหลังจากนำหน้า “p” ทันที และผลลัพธ์ของ + ในทำนองเดียวกัน “/” จะใช้ผลลัพธ์ของนิพจน์การคูณและตัว “s”

3. สัญกรณ์ Postfix

Postfix Notation ซึ่งส่วนใหญ่เป็นตัวถูกดำเนินการ ตามด้วยตัวดำเนินการ มันยังถูกตั้งชื่อเป็น Reverse Polish Notation เช่น pq+

<ตัวถูกดำเนินการ> <ตัวถูกดำเนินการ> <ตัว ดำเนินการ>

สำหรับ Postfix เช่นเดียวกับการดำเนินการ Prefix ของนิพจน์คือซ้ายไปขวาและ "( )" ไม่จำเป็น ที่นี่ ตัวดำเนินการดำเนินการกับค่าที่ใกล้ที่สุดสองค่าจากด้านขวา ในตัวอย่างด้านล่าง มีการเพิ่มวงเล็บโดยไม่จำเป็น เพื่อให้ชัดเจนว่าไม่มีผลกระทบต่อการประเมิน

(/ (* p (+ qr) ) s)

ในที่นี้ ค่าการดำเนินการ "การประเมินผู้ปฏิบัติงานมาจากซ้ายไปขวา" ค่าดำเนินการจะอยู่ทางด้านขวา และหากค่านั้นเกี่ยวข้องกับการคำนวณ ลำดับของการประเมินก็จะเปลี่ยนไป จากตัวอย่างข้างต้น ให้ดูที่ “/” เป็นตัวดำเนินการหลักทางด้านซ้าย

รอจนกว่าการดำเนินการคูณจะเสร็จสิ้น และในเบื้องต้น จำเป็นต้องดำเนินการคูณก่อนที่จะเริ่มการคำนวณหาร (และจากตัวอย่างข้างต้น จะเห็นได้ชัดเจนว่าการดำเนินการบวกนั้นจำเป็นต้องทำให้เสร็จก่อนดำเนินการคูณ)

เนื่องจากตัวดำเนินการ Postfix Notation ใช้ค่าทางด้านขวา ค่าใดๆ ที่เกี่ยวข้องกับการคำนวณจะทำให้การคำนวณเสร็จสมบูรณ์เมื่อเราเลื่อนไปทางซ้าย ดังนั้น เราสามารถสรุปได้ว่าการคำนวณนิพจน์ไม่เหมือนกับการดำเนินการตัวดำเนินการคำนำหน้า

เพื่อเน้นทั้งสามสัญลักษณ์ ตัวถูกดำเนินการมาในลำดับเดียวกัน และตัวดำเนินการต้องถูกย้ายเพื่อให้ความหมายที่ถูกต้องระหว่างการคำนวณ สิ่งนี้จำเป็นต้องได้รับการพิจารณาโดยเฉพาะอย่างยิ่งเมื่อพิจารณาตัวดำเนินการอสมมาตร “-” และ “/” เพื่อให้ชัดเจน pq เคยเป็น qr เว้นแต่จะมีค่าเท่ากัน ค่าเทียบเท่ากับ “pq -” หรือ “- pq”

P+q ≡ +pq ≡ pq+

เช่น:

Infix- p * q + r / s

คำนำหน้า – pq * rs / +

แก้ไขโพสต์ – + * pq / rs

ขั้นแรก ในการดำเนินการ ให้คูณ p และ q และต่อมาหาร r ด้วย s และสุดท้าย บวกผลลัพธ์

ด้านล่างตารางสรุประหว่างสามสัญลักษณ์

สัญกรณ์ Infix	สัญกรณ์โปแลนด์	สัญกรณ์ขัดเงา
p+q	+pq	pq+
(p+q)*r	++pq	pqr+*
พี*(q+r)	*p+qr	pqr*+ +
p÷q+r÷s	+÷pq÷rs	pq÷rs÷+
(pq)*(rs)	*-pq-rs	pq-rs-*

การแปลงระหว่างสัญลักษณ์

*เพื่อให้ข้อมูลเชิงลึกที่ชัดเจน วงเล็บจะถูกเพิ่มในนิพจน์

Infix	Postfix	คำนำหน้า
( (p * q) + (r / s) )	( (pq *) (rs /) +)	(+ (* pq) (/ rs) )
((p * (q + r) ) / วินาที)	( (p (qr +) *) s /)	(/ (* p (+ qr) ) s)
(p * (q + (r / s) ) )	(p (q (rs /) +) *)	(* p (+ q (/ rs) ) )

• คุณสามารถเริ่มการแปลงโดยตรงในวงเล็บโดยใช้ตัวดำเนินการในวงเล็บ เช่น (m + n) หรือ (mn +) หรือ (+ mn) ทำซ้ำในโอเปอเรเตอร์ทั้งหมดโดยลบวงเล็บที่ไม่ต้องการ
• ตอนนี้ใช้เคล็ดลับนี้ที่แสดงด้านบนเพื่อแปลงและแยกวิเคราะห์ต้นไม้ – ต้นไม้แยกวิเคราะห์ที่เทียบเท่ากันสำหรับแต่ละโหนดคือ:

ชำระเงิน: โครงสร้างข้อมูล & อัลกอริธึมใน Python

บทสรุป

การแยกวิเคราะห์นิพจน์ในโครงสร้างข้อมูล Infix, Postfix และ Prefix Notation ในนิพจน์ทางคณิตศาสตร์นั้นค่อนข้างแตกต่างกัน แต่มีวิธีการเขียนนิพจน์เหมือนกัน ความรู้เหล่านี้มีความสำคัญในการเขียนโปรแกรม

ในภาษาการเขียนโปรแกรมคอมพิวเตอร์ นิพจน์จะถูกพิจารณาและแยกวิเคราะห์จากสตริง กฎการเชื่อมโยงและลำดับความสำคัญค่อนข้างเปลี่ยนแปลงในภาษาต่างๆ

ทำไมถึงเลือกเรียนหลักสูตร Data Science กับ upGrad?

วิทยาศาสตร์ข้อมูลเป็นหนึ่งในสาขาที่เฟื่องฟูในด้านวิทยาการคอมพิวเตอร์ บริษัทต่างๆ ต้องการโปรแกรมเมอร์ที่มีความรู้พื้นฐานที่ดี ซึ่งเป็นพื้นฐานสำหรับการเขียนโปรแกรมโดยไม่คำนึงถึงภาษาการเขียนโปรแกรม

upGrad มุ่งเน้นไปที่การจัดหาชั้นเรียนที่ชาญฉลาดและให้ข้อมูล ครอบคลุมทุกความต้องการขั้นพื้นฐานสำหรับการเป็นนักวิทยาศาสตร์ข้อมูล โปรแกรม PG สำหรับผู้บริหาร 12 เดือนของ upGrad ในสาขาวิทยาศาสตร์ข้อมูล นำเสนอโดย IIIT Bangalore เป็นหลักสูตรที่ได้รับการรับรองจาก NASSCOM แห่งแรกของอินเดีย ซึ่งมาพร้อมกับการให้คำปรึกษาแบบตัวต่อตัวแบบ 1:1 จากผู้เชี่ยวชาญด้าน Data Science Industry ครอบคลุมภาษาการเขียนโปรแกรม เครื่องมือ และไลบรารีที่จำเป็นทั้งหมด เป็นพื้นฐานที่ดีที่สุดในการเริ่มต้นงานวิทยาศาสตร์ข้อมูลที่ต้องจ่ายเงินสูง

โครงสร้างข้อมูลคืออะไร?

โครงสร้างข้อมูลใช้เพื่อจัดระเบียบข้อมูลในหน่วยความจำ มีหลายวิธีในการจัดเรียงข้อมูลในหน่วยความจำ รวมถึงอาร์เรย์ รายการ สแตก คิว และอื่นๆ อีกมากมาย โครงสร้างข้อมูลไม่ใช่ภาษาการเขียนโปรแกรมเช่น C, C ++ หรือ Java แต่เป็นชุดของเทคนิคที่ใช้ในการจัดเรียงข้อมูลในหน่วยความจำในภาษาการเขียนโปรแกรมใดๆ โครงสร้างข้อมูลเป็นวิธีการจัดระเบียบ จัดการ และจัดเก็บข้อมูลอย่างมีประสิทธิภาพ รายการข้อมูลสามารถสำรวจได้ด้วยความช่วยเหลือของโครงสร้างข้อมูล การปรับปรุงความเร็วของโปรแกรมเป็นสิ่งสำคัญ เนื่องจากงานหลักของโปรแกรมคือการบันทึกและดึงข้อมูลของผู้ใช้โดยเร็วที่สุด

การใช้งานจริงของการแยกวิเคราะห์ข้อมูลคืออะไร?

กระบวนการแปลงข้อมูลจากรูปแบบหนึ่งไปอีกรูปแบบหนึ่งเรียกว่าการแยกวิเคราะห์ข้อมูล มีการใช้กันอย่างแพร่หลายในคอมไพเลอร์เพื่อแยกวิเคราะห์รหัสคอมพิวเตอร์และสร้างรหัสเครื่อง กระบวนการแปลงข้อมูลจากรูปแบบหนึ่งไปอีกรูปแบบหนึ่งเรียกว่าการแยกวิเคราะห์ข้อมูล เนื่องจาก HTML ดิบที่เราได้รับนั้นเข้าใจยาก ตัวแยกวิเคราะห์จึงมักใช้ในการขูดออนไลน์ เราต้องการให้ข้อมูลถูกแปลงเป็นรูปแบบที่มนุษย์อ่านได้ ซึ่งอาจหมายถึงการสร้างรายงานโดยใช้สตริงหรือตาราง HTML เพื่อให้ข้อมูลที่เกี่ยวข้องมากที่สุด

การเชื่อมโยงและลำดับความสำคัญช่วยในการจัดโครงสร้างข้อมูลอย่างไร

ลำดับการประเมินของนิพจน์ถูกกำหนดโดยคุณสมบัติสองประการของตัวดำเนินการ: ลำดับความสำคัญและการเชื่อมโยง ลำดับความสำคัญช่วยในการกำหนดว่าควรจัดกลุ่มคำในนิพจน์อย่างไรและควรประเมินนิพจน์อย่างไร เนื่องจากนิพจน์ส่วนใหญ่ใช้เฟรมเวิร์ก BODMAS ตัวดำเนินการบางตัวจึงมีความสำคัญเหนือกว่าตัวอื่นๆ เมื่อตัวดำเนินการสองตัวมีลำดับความสำคัญเท่ากันในนิพจน์ กฎของการเชื่อมโยงจะถูกนำมาใช้ ตามความชอบของคอมไพเลอร์ การเชื่อมโยงอาจเป็นซ้ายไปขวาหรือขวาไปซ้าย