स्टैक एक रैखिक डेटा संरचना है, जहां डेटा केवल एक छोर पर डाला और निकाला जाता है।
एल्गोरिदम
नीचे पुश ( ) -
. के लिए एक एल्गोरिथम दिया गया है- स्टैक ओवरफ्लो की जांच करें।
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]); स्टैक का अनुप्रयोग
आइए हम सी भाषा में स्टैक के भावों के रूपांतरण को समझते हैं।
अभिव्यक्ति - यह ऑपरेंड और संचालन का कानूनी संयोजन है।
अभिव्यक्ति के प्रकार
सी भाषा में तीन प्रकार के भाव होते हैं जिन पर रूपांतरण और मूल्यांकन किया जा सकता है। उन्हें नीचे समझाया गया है -
-
इंफिक्स एक्सप्रेशन - ऑपरेटर ऑपरेंड के बीच में होता है। उदाहरण के लिए, ए+बी
-
उपसर्ग अभिव्यक्ति - ऑपरेटर ऑपरेंड से पहले है। उदाहरण के लिए, +AB
-
पोस्टफिक्स एक्सप्रेशन - ऑपरेटर ऑपरेंड के बाद होता है। उदाहरण के लिए, AB+
पोस्टफिक्स एक्सप्रेशन का मूल्यांकन
एल्गोरिदम
इनपुट स्ट्रिंग को बाएं से दाएं स्कैन करें।
प्रत्येक इनपुट प्रतीक के लिए,
-
यदि यह एक अंक है, तो इसे स्टैक पर पुश करें।
-
यदि यह एक ऑपरेटर है, तो स्टैक से शीर्ष दो सामग्री को पॉप आउट करें और उन पर ऑपरेटर लागू करें। बाद में, परिणाम को स्टैक करने के लिए पुश करें।
-
अगर इनपुट सिंबल '\0' है, तो स्टैक को खाली करें।
कार्यक्रम
पोस्टफिक्स एक्सप्रेशन के मूल्यांकन के लिए सी प्रोग्राम निम्नलिखित है -
#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