อธิบายการประเมินนิพจน์สแต็คในภาษาซี

กองซ้อนเป็นโครงสร้างข้อมูลเชิงเส้น โดยที่ข้อมูลจะถูกแทรกและนำออกที่ปลายด้านเดียวเท่านั้น

อัลกอริทึม

ด้านล่างเป็นอัลกอริธึมสำหรับการกด ( ) −

• ตรวจสอบสแต็กโอเวอร์โฟลว์

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

• มิฉะนั้น ให้แทรกองค์ประกอบลงในสแต็ก

top ++
a[top] = item

รับด้านล่างเป็นอัลกอริทึมสำหรับ ป๊อป ( ) −

• ตรวจสอบสแต็กอันเดอร์โฟลว์

if ( top = = -1)
printf( "stack under flow");

มิฉะนั้น ให้ลบองค์ประกอบออกจากสแต็ก

item = a[top]
top --

ด้านล่างนี้คืออัลกอริทึมสำหรับ ดิสเพลย์ ( ) −

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

มิฉะนั้น ให้ปฏิบัติตามอัลกอริธึมที่กล่าวถึงด้านล่าง

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

การประยุกต์ใช้สแต็ค

ให้เราเข้าใจการแปลงนิพจน์ของสแต็คในภาษาซี

นิพจน์ - เป็นการผสมผสานทางกฎหมายของตัวถูกดำเนินการและการดำเนินการ

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

มีสามประเภทของนิพจน์ในภาษา C ซึ่งสามารถดำเนินการแปลงและประเมินค่าได้ อธิบายไว้ด้านล่าง −

• นิพจน์ Infix - ตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ ตัวอย่างเช่น A+B

• นิพจน์คำนำหน้า - ตัวดำเนินการอยู่ก่อนตัวถูกดำเนินการ ตัวอย่างเช่น +AB

• นิพจน์ Postfix - ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ ตัวอย่างเช่น AB+

การประเมินนิพจน์ postfix

อัลกอริทึม

สแกนสตริงอินพุตจากซ้ายไปขวา

สำหรับแต่ละสัญลักษณ์อินพุต

• หากเป็นตัวเลข ให้ดันไปที่สแต็ก

• หากเป็นโอเปอเรเตอร์ ให้เปิดเนื้อหาส่วนใหญ่สองรายการบนสุดจากสแต็กและใช้โอเปอเรเตอร์กับเนื้อหาเหล่านั้น ต่อมาก็ดันผลไปกอง

• หากสัญลักษณ์อินพุตคือ '\0' ให้ล้างสแต็ก

โปรแกรม

ต่อไปนี้เป็นโปรแกรม C สำหรับการประเมินนิพจน์ postfix -

#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);
   }
}

ผลลัพธ์

เมื่อโปรแกรมข้างต้นทำงาน มันจะให้ผลลัพธ์ดังต่อไปนี้ −

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