স্ট্যাক একটি লিনিয়ার ডেটা স্ট্রাকচার, যেখানে ডেটা শুধু একটি এন্ডে ইনসার্ট এবং রিমুভ করা হয়।
অ্যালগরিদম
Push ( ) এর অ্যালগরিদম নিচে দেওয়া হলো—
- স্ট্যাক ওভারফ্লো চেক করুন।
if (top == n-1) printf("stack over flow");
- অন্যথায়, স্ট্যাকে এলিমেন্ট ইনসার্ট করুন।
top++ a[top] = item
Pop ( ) এর অ্যালগরিদম—
- স্ট্যাক আন্ডারফ্লো চেক করুন।
if (top == -1) printf("stack under flow");
অন্যথায়, স্ট্যাক থেকে এলিমেন্ট ডিলিট করুন।
item = a[top] top--
Display ( ) এর অ্যালগরিদম—
if (top == -1) printf("stack is empty");
অন্যথায়, নিচের অ্যালগরিদম অনুসরণ করুন।
for (i=0; i<=top; i++) printf("%d", a[i]);
স্ট্যাকের অ্যাপ্লিকেশন
C ভাষায় স্ট্যাক ব্যবহার করে এক্সপ্রেশন কনভারশন বুঝি।
এক্সপ্রেশন (Expression) — অপারেন্ড এবং অপারেশন-এর একটি বৈধ কম্বিনেশন।
এক্সপ্রেশনের প্রকার
C ভাষায় তিনটি ধরণের এক্সপ্রেশন আছে, जिन waarop কনভারশন এবং ইভ্যালুয়েশন করা যায়—
- ইনফিক্স এক্সপ্রেশন (Infix expression) — অপারেটর অপারেন্ডের মাঝপথে থাকে। উদাহরণ: A+B
- প্রিফিক্স এক্সপ্রেশন (Prefix expression) — অপারেটর অপারেন্ডের আগে থাকে। উদাহরণ: +AB
- পোস্টফিক্স এক্সপ্রেশন (Postfix expression) — অপারেটর অপারেন্ডের পরে থাকে। উদাহরণ: AB+
পোস্টফিক্স এক্সপ্রেশন ইভ্যালুয়েশন
অ্যালগরিদম
ইনপুট স্ট্রিংকে বাম থেকে ডানে স্ক্যান করুন।
প্রতিটি ইনপুট সিম্বলের জন্য—
- যদি সেটি ডিজিট হয়, তবে স্ট্যাকে পুশ করুন।
- যদি সেটি অপারেটর হয়, তবে স্ট্যাক থেকে 탑-most দুটি কন্টেন্ট পপ করুন এবং সেগুলোর ওপর অপারেটর অ্যাপ্লাই করুন। পরে রেজাল্টটি স্ট্যাকে পুশ করুন।
- যদি ইনপুট সিম্বল '\0' হয়, তবে স্ট্যাক খালি করুন।
প্রোগ্রাম
পোস্টফিক্স এক্সপ্রেশন ইভ্যালুয়েশনের জন্য C প্রোগ্রাম—
#include<stdio.h>
int top = -1, stack[100];
int 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(ch - '0'); // character to integer
else {
op2 = pop();
op1 = pop();
res = eval(ch, op1, op2);
push(res);
}
}
x = pop();
printf("evaluated value = %d", x);
getch();
return 0;
}
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);
}
return 0;
}
আউটপুট
প্রোগ্রামটি এক্সিকিউট করলে নিচের ফলাফল পাওয়া যায়—
Run 1: enter a postfix expression: 45+ evaluated value = 9 Run 2: enter a postfix expression: 3 5 2 * + evaluated value = 13
