การแปลงนิพจน์ใน Stack ด้วยภาษา C (Infix to Postfix/Prefix)

Stack เป็นโครงสร้างข้อมูลแบบเส้นตรงที่ข้อมูลเพิ่มและลบได้เฉพาะปลายเดียว (Top)

อัลกอริทึมพื้นฐาน Stack

Push

if (top == n-1) printf("stack overflow");
else { top++; a[top] = item; }

Pop

if (top == -1) printf("stack underflow");
else { item = a[top]; top--; }

Display

if (top == -1) printf("stack is empty");
else { for(i=0; i<=top; i++) printf("%d ", a[i]); }

การแปลงนิพจน์ (Expression Conversion)

นิพจน์ คือการรวมระหว่andum และตัวดำเนินการอย่างถูกต้อง

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

• Infix - ตัวดำเนินการอยู่กลาง เช่น A+B
• Prefix - ตัวดำเนินการอยู่หน้า เช่น +AB
• Postfix - ตัวดำเนินการอยู่หลัง เช่น AB+

ตัวอย่างการแปลง

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 Postfix:     Infix to Prefix:
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 /*BCD - E + F
ABC*D/+E-+F           -+A/*BCDE+F
ABC*D/+E-F+           +-+A/*BCDEF

อัลกอริทึมการแปลง Infix เป็น Postfix (ใช้ Stack)

1. อ่านสัญลักษณ์จากซ้ายไปขวา
2. ถ้าเป็น Operand -> พิมพ์ออกมาทันที
3. ถ้าเป็น '(' -> Push เข้า Stack
4. ถ้าเป็น ')' -> Pop และพิมพ์จนกว่าจะเจอ '('
5. ถ้าเป็น Operator -> เปรียบเทียบ Precedence (ลำดับความสำคัญ) กับ Operator ที่อยู่ Top ของ Stack
   • ถ้า Precedence ของ Top Stack >= Precedence ของ Operator ปัจจุบัน -> Pop ออกมาแล้ว Push Operator ปัจจุบัน
   • มิฉะนั้น -> Push Operator ปัจจุบันเข้า Stack
6. ถ้าจบสตริง ('\0') -> Pop ทุกตัวที่เหลือใน Stack ออกมา