Giải thích việc đánh giá các biểu thức của ngăn xếp trong ngôn ngữ C

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à một 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à 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 các 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 +

Đánh giá biểu thức hậu tố

Thuật toán

Quét chuỗi đầu vào từ trái sang phải.

Đối với mỗi ký hiệu đầu vào,

• Nếu đó là một chữ số, hãy đẩy nó vào ngăn xếp.

• Nếu đó là một toán tử thì hãy bật ra hai nội dung trên cùng từ ngăn xếp và áp dụng toán tử cho chúng. Sau đó, đẩy kết quả vào ngăn xếp.

• Nếu ký hiệu đầu vào là ‘\ 0’, hãy làm trống ngăn xếp.

Chương trình

Sau đây là chương trình C để đánh giá biểu thức hậu tố -

#include<stdio.h>
int top = -1, stack [100];
main ( ){
   char a[50], ch;
   int i,op1,op2,res,x;
   void push (int);
   int pop( );
   int eval (char, int, int);
   printf("enter a postfix expression:");
   gets (a);
   for(i=0; a[i]!='\0'; i++){
      ch = a[i];
      if (ch>='0' && ch<='9')
         push('0');
      else{
         op2 = pop ( );
         op1 = pop ( );
         res = eval (ch, op1, op2);
         push (res);
      }
   }
   x = pop ( );
   printf("evaluated value = %d", x);
   getch ( );
}
void push (int n){
   top++;
   stack [top] = n;
}
int pop ( ){
   int res ;
   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);
   }
}

Đầu ra

Khi chương trình trên được thực thi, nó tạo ra kết quả sau -

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