Giải thích chuyển đổi 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, dữ liệu chèn và xóa chỉ tại một đầu.

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

Push (Đẩy vào)

• Kiểm tra tràn: if (top == n-1) printf("stack overflow");
• Chèn: top++; a[top] = item;

Pop (Lấy ra)

• Kiểm tra rỗng: if (top == -1) printf("stack underflow");
• Xóa: item = a[top]; top--;

Display (Hiển thị)

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

Ứng dụng: Chuyển đổi biểu thức

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

Ba dạng biểu thức

• Infix (Trung tố): Toán tử giữa hai toán hạng. Ví dụ: A+B
• Prefix (Tiền tố): Toán tử trước toán hạng. Ví dụ: +AB
• Postfix (Hậu tố): Toán tử sau toán hạng. Ví dụ: AB+

Ví dụ chuyển đổi

Infix sang Postfix:    A + B * C
Bước 1: A + B C *
Bước 2: A B C * +
Kết quả: ABC*+

Infix sang Prefix:     A + B * C
Bước 1: A + * B C
Bước 2: + A * B C
Kết quả: +A*BC

Ví dụ phức tạp: Chuyển đổi A+B*C/D-E+F

Infix sang Postfix:  ABC*D/+E-F+
Infix sang Prefix:   +-+A/*BCDEF

Thuật toán chuyển Infix sang Postfix (Shunting Yard)

Quét chuỗi từ trái sang phải:

• Bước 1: Nếu là toán hạng, in ra màn hình.
• Bước 2: Nếu là '(', đẩy vào stack.
• Bước 3: Nếu là ')', lấy tất cả khỏi stack cho đến khi gặp '('.
• Bước 4: Nếu là toán tử, so sánh độ ưu tiên với đỉnh stack.
  • Nếu ưu tiên đỉnh stack ≥ ưu tiên hiện tại: pop đỉnh stack ra, push toán tử hiện tại.
  • Ngược lại: push toán tử hiện tại vào stack.
• Bước 5: Nếu gặp '\0', pop tất cả phần tử còn lại trong stack.

Minh họa chuyển đổi Infix sang Postfix với Stack: