Ngăn xếp là một cấu trúc dữ liệu tuyến tính, nơi dữ liệu chỉ được chèn và xóa ở một đầu.
Thuật toán
Dưới đây là thuật toán cho Push () -
- Kiểm tra sự cố tràn ngăn xếp.
if (top = = n-1)
printf("stack over flow"); - Nếu không, hãy chèn một phần tử vào ngăn xếp.
top ++ a[top] = item
Dưới đây là thuật toán cho Pop () -
- Kiểm tra quy trình bên dưới ngăn xếp.
if (top = = -1)
printf("stack under flow"); Nếu không, hãy xóa một phần tử khỏi ngăn xếp.
item = a[top] top --
Dưới đây là một thuật toán cho Display () -
if (top == -1)
printf ("stack is empty"); Nếu không, hãy làm theo thuật toán được đề cập bên dưới.
for (i=0; i<top; i++)
printf ("%d", a[i]); Ứng dụng của ngăn xếp
Hãy để chúng tôi hiểu các chuyển đổi của biểu thức ngăn xếp trong ngôn ngữ C.
Biểu thức - Nó là sự kết hợp hợp pháp giữa toán hạng và phép toán.
Các loại biểu thức
Có ba loại biểu thức trong ngôn ngữ C để chuyển đổi và đánh giá có thể được thực hiện. Chúng được giải thích bên dưới -
-
Biểu thức infix - Toán tử nằm giữa các toán hạng. Ví dụ:A + B
-
Biểu thức tiền tố - Toán tử đứng trước các toán hạng. Ví dụ:+ AB
-
Biểu thức hậu tố - Toán tử đứng sau các toán hạng. Ví dụ:AB +
Việc chuyển đổi infix thành postfix và infix thành prefix được giải thích bên dưới -
Infix to postfix Infix to prefix A+ B*C A+ B*C A+ BC * A+ *BC ABC* + +A*BC
Ví dụ:
Chuyển đổi tiền tố A + B * C / D-E + F thành tiền tố hậu tố và tiền tố.
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+
Thuật toán
Quét chuỗi đầu vào từ trái sang phải và làm theo các bước dưới đây -
-
Bước 1 - Nếu ký hiệu đầu vào là một toán hạng, hãy in nó ra màn hình.
-
Bước 2 - Nếu ký hiệu đầu vào là ‘(‘ thì hãy đẩy nó vào ngăn xếp.
-
Bước 3 - Nếu đầu vào ký hiệu là ‘)’ thì hãy bật ra tất cả nội dung của ngăn xếp cho đến khi bạn nhận được ‘(‘.
-
Bước 4 - Nếu ký hiệu đầu vào là một toán tử, hãy kiểm tra mức độ ưu tiên của toán tử trên đầu ngăn xếp với ký hiệu đầu vào hiện tại.
Nếu mức độ ưu tiên hàng đầu của phần trên cùng của ngăn xếp lớn hơn hoặc bằng mức độ ưu tiên của biểu tượng hiện tại, thì hãy bật ra nội dung của ngăn xếp và đặt biểu tượng hiện tại vào ngăn xếp.
Nếu không, hãy đẩy toán tử vào ngăn xếp.
-
Bước 5 - Nếu ký hiệu đầu vào là ‘\ 0’ thì hãy bật ra nội dung của ngăn xếp cho đến khi nó trở nên trống.
Chuyển đổi infix để đăng sửa chữa với sự trợ giúp của ngăn xếp được đưa ra bên dưới -
