Giải thích đánh giá biểu thức stack trong ngôn ngữ C

Stack (ngăn xếp) là cấu trúc dữ liệu tuyến tính, nơi dữ liệu được chèn và xóa chỉ tại một đầu (đỉnh stack).

Các thuật toán cơ bản

Thuật toán Push (Đẩy vào stack)

• Kiểm tra tràn stack (stack overflow).

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

• Nếu không tràn, chèn phần tử vào stack.

top++;
a[top] = item;

Thuật toán Pop (Lấy ra khỏi stack)

• Kiểm tra rỗng stack (stack underflow).

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

• Nếu không rỗng, lấy phần tử ra khỏi stack.

item = a[top];
top--;

Thuật toán Display (Hiển thị stack)

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

Nếu không rỗng:

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

Ứng dụng của Stack: Chuyển đổi và đánh giá biểu thức

Biểu thức là tổ hợp hợp lệ của toán hạng (operand) và toán tử (operator).

Ba loại biểu thức

• Biểu thức trung tố (Infix): Toán tử nằm giữa hai toán hạng. Ví dụ: A+B
• Biểu thức tiền tố (Prefix): Toán tử nằm trước toán hạng. Ví dụ: +AB
• Biểu thức hậu tố (Postfix): Toán tử nằm sau toán hạng. Ví dụ: AB+

Đánh giá biểu thức hậu tố (Postfix Evaluation)

Thuật toán

Quét chuỗi nhập từ trái sang phải. Với mỗi ký tự:

• Nếu là chữ số: đẩy (push) vào stack.
• Nếu là toán tử: lấy (pop) 2 phần tử đầu stack, áp dụng toán tử, đẩy kết quả vào stack.
• Nếu gặp ký tự kết thúc '\0': làm rỗng stack.

Chương trình mẫu

Chương trình C đánh giá biểu thức hậu tố:

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

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

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

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

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

int main() {
    char a[50], ch;
    int i, op1, op2, res, x;
    
    printf("Nhập biểu thức hậu tố: ");
    gets(a);
    
    for(i = 0; a[i] != '\0'; i++) {
        ch = a[i];
        if (ch >= '0' && ch <= '9') {
            push(ch - '0');  // Chuyển char thành int
        } else {
            op2 = pop();
            op1 = pop();
            res = eval(ch, op1, op2);
            push(res);
        }
    }
    
    x = pop();
    printf("Giá trị tính được = %d\n", x);
    return 0;
}

Kết quả chạy

Chạy 1: Nhập biểu thức hậu tố: 45+ 
Giá trị tính được = 9

Chạy 2: Nhập biểu thức hậu tố: 352*+ 
Giá trị tính được = 13