การประเมินค่าของนิพจน์ใน Stack ด้วยภาษา C

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

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

Push (การเพิ่มข้อมูล)

• ตรวจสอบ Stack Overflow (เต็ม)

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

• หากไม่เต็ม ให้เพิ่มข้อมูล

top++;
a[top] = item;

Pop (การนำข้อมูลออก)

• ตรวจสอบ Stack Underflow (ว่าง)

if (top == -1) printf("stack underflow");

• หากไม่ว่าง ให้นำข้อมูลออก

item = a[top];
top--;

Display (การแสดงผล)

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

การประยุกต์ใช้ Stack: การประเมินค่านิพจน์ Postfix

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

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

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

การประเมินค่านิพจน์ Postfix

อัลกอริทึม

1. อ่านสตริงนิพจน์จากซ้ายไปขวา
2. สำหรับแต่ละสัญลักษณ์:
   • ถ้าเป็นตัวเลข (Digit) ให้ Push เข้า Stack
   • ถ้าเป็นตัวดำเนินการ (Operator) ให้ Pop ข้อมูล 2 ตัวบนสุด มาคำนวณ แล้ว Push ผลลัพธ์กลับเข้า Stack
   • ถ้าพบ '\0' (จบสตริง) ให้ Pop ค่าที่เหลือออกมาเป็นคำตอบ

โปรแกรมตัวอย่าง: ประเมินค่า Postfix Expression

#include <stdio.h>
#include <ctype.h>

int top = -1;
int stack[100];

void push(int n) {
    stack[++top] = n;
}

int pop() {
    return stack[top--];
}

int eval(char op, int op1, int op2) {
    switch(op) {
        case '+': return op1 + op2;
        case '-': return op1 - op2;
        case '*': return op1 * op2;
        case '/': return op1 / op2;
    }
    return 0;
}

int main() {
    char expr[50];
    int i, op1, op2, result;
    
    printf("Enter a postfix expression: ");
    scanf("%s", expr);
    
    for(i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if (isdigit(ch)) {
            push(ch - '0');  // แปลง char เป็น int
        } else {
            op2 = pop();
            op1 = pop();
            result = eval(ch, op1, op2);
            push(result);
        }
    }
    
    printf("Evaluated value = %d\n", pop());
    return 0;
}

ผลลัพธ์

Run 1: enter a postfix expression: 45+  evaluated value = 9
Run 2: enter a postfix expression: 352*+  evaluated value = 13