อธิบายการแปลงนิพจน์สแต็คในภาษาซี

กองซ้อนเป็นโครงสร้างข้อมูลเชิงเส้น โดยที่ข้อมูลจะถูกแทรกและนำออกที่ปลายด้านเดียวเท่านั้น

อัลกอริทึม

ด้านล่างนี้เป็นอัลกอริทึมสำหรับ พุช ( ) −

• ตรวจสอบสแต็กโอเวอร์โฟลว์

if (top = = n-1)
printf("stack over flow");

• มิฉะนั้น ให้แทรกองค์ประกอบลงในสแต็ก

top ++
a[top] = item

รับด้านล่างเป็นอัลกอริทึมสำหรับ ป๊อป ( ) −

• ตรวจสอบสแต็กอันเดอร์โฟลว์

if (top = = -1)
printf("stack under flow");

มิฉะนั้น ให้ลบองค์ประกอบออกจากสแต็ก

item = a[top]
top --

ด้านล่างเป็นอัลกอริธึมสำหรับ Display ( ) −

if (top == -1)
printf ("stack is empty");

มิฉะนั้น ให้ปฏิบัติตามอัลกอริธึมที่กล่าวถึงด้านล่าง

for (i=0; i<top; i++)
printf ("%d", a[i]);

การประยุกต์ใช้สแต็ค

ให้เราเข้าใจการแปลงนิพจน์ของสแต็คในภาษาซี

นิพจน์ − เป็นการรวมตัวถูกดำเนินการและการดำเนินการทางกฎหมายร่วมกัน

ประเภทของนิพจน์

มีสามประเภทของนิพจน์ในภาษา C ซึ่งสามารถดำเนินการแปลงและประเมินผลได้ อธิบายไว้ด้านล่าง −

• นิพจน์ Infix - ตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ ตัวอย่างเช่น A+B

• นิพจน์คำนำหน้า - ตัวดำเนินการอยู่ก่อนตัวถูกดำเนินการ ตัวอย่างเช่น +AB

• นิพจน์ Postfix - ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ ตัวอย่างเช่น AB+

อธิบายการแปลง infix เป็น postfix และ infix เป็น prefix อธิบายไว้ด้านล่าง -

Infix to postfix    Infix to prefix
A+ B*C               A+ B*C
A+ BC *              A+ *BC
ABC* +               +A*BC

ตัวอย่างเช่น

แปลงคำนำหน้า A+B*C / D-E+F เป็นคำนำหน้าและคำนำหน้า

Infix to prefix            Infix to postfix
A +B*C / D-E+F            A +B*C / D-E+F
A +*BC / D-E+F            A +BC* / D-E+F
A + / *BCD -E+F           A +BC*D /-E+F
+A /*BCD -E +F            ABC *D /+ -E+F
-+A/*BCDE +F              ABC *D/ +E- +F
+ - +A/*BCDEF             ABC *D / +E –F+

อัลกอริทึม

สแกนอินพุตสตริงจากซ้ายไปขวาและทำตามขั้นตอนที่ระบุด้านล่าง -

• ขั้นตอนที่ 1 - หากสัญลักษณ์อินพุตเป็นตัวถูกดำเนินการ ให้พิมพ์ไปที่จอภาพ

• ขั้นตอนที่ 2 - หากสัญลักษณ์อินพุตคือ '('จากนั้นให้ดันไปที่สแต็ก

• ขั้นตอนที่ 3 - หากอินพุตของสัญลักษณ์คือ ')' ให้เปิดเนื้อหาทั้งหมดของสแต็กออกจนกว่าคุณจะได้รับ '('.

• ขั้นตอนที่ 4 - หากสัญลักษณ์อินพุตเป็นตัวดำเนินการ ให้ตรวจสอบลำดับความสำคัญของตัวดำเนินการที่ด้านบนของสแต็กด้วยสัญลักษณ์อินพุตปัจจุบัน

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

มิฉะนั้น ให้ดันโอเปอเรเตอร์ไปที่สแต็ก

• ขั้นตอนที่ 5 - หากสัญลักษณ์อินพุตคือ '\0' ให้เปิดเนื้อหาของสแต็กออกมาจนกว่าจะว่างเปล่า

การแปลง infix เป็น post fix โดยใช้ stack ด้านล่าง -