স্ট্যাক একটি লিনিয়ার ডেটা স্ট্রাকচার, যেখানে ডেটা শুধু একটি এন্ডে ইনসার্ট এবং রিমুভ করা হয়।
অ্যালগরিদম
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 ভাষায় তিনটি ধরণের এক্সপ্রেশন আছে—
- ইনফিক্স এক্সপ্রেশন (Infix expression) — অপারেটর অপারেন্ডের মাঝপথে থাকে। উদাহরণ: A+B
- প্রিফিক্স এক্সপ্রেশন (Prefix expression) — অপারেটর অপারেন্ডের আগে থাকে। উদাহরণ: +AB
- পোস্টফিক্স এক্সপ্রেশন (Postfix expression) — অপারেটর অপারেন্ডের পরে থাকে। উদাহরণ: AB+
ইনফিক্স থেকে পোস্টফিক্স এবং ইনফিক্স থেকে প্রিফিক্স কনভারশন নিচে দেখানো হলো—
Infix to postfix Infix to prefix A+ B*C A+ B*C A+ BC * A+ *BC ABC* + +A*BC
উদাহরণস্বরূপ,
Convert A+B*C / D-E+F infix to postfix and prefix.
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 + - +A/*BCDEF ABC *D / +E–F+
অ্যালগরিদম
ইনপুট স্ট্রিংকে বাম থেকে ডানে স্ক্যান করুন এবং নিচের ধাপগুলো অনুসরণ করুন—
- Step 1 — ইনপুট সিম্বল অপারেন্ড হলে, তা মনিটরে প্রিন্ট করুন।
- Step 2 — ইনপুট সিম্বল '(' হলে, তা স্ট্যাকে পুশ করুন।
- Step 3 — ইনপুট সিম্বল ')' হলে, '(' পাওয়া পর্যন্ত স্ট্যাকের সব কন্টেন্ট পপ করুন।
- Step 4 — ইনপুট সিম্বল অপারেটর হলে, স্ট্যাকে থাকা অপারেটরের প্রায়োরিটি বর্তমান সিম্বলের সাথে তুলনা করুন।
যদি স্ট্যাকে থাকা অপারেটরের প্রায়োরিটি বর্তমান সিম্বলের প্রায়োরিটির চেয়ে বড় বা সমান হয়, তবে স্ট্যাক থেকে কন্টেন্ট পপ করুন এবং বর্তমান সিম্বলটি স্ট্যাকে পুশ করুন।
অন্যথায়, অপারেটরটি স্ট্যাকে পুশ করুন।
- Step 5 — ইনপুট সিম্বল '\0' হলে, স্ট্যাক খালি না হওয়া পর্যন্ত কন্টেন্ট পপ করুন।
স্ট্যাকের সাহায্যে ইনফিক্স থেকে পোস্টফিক্স কনভারশন নিচে দেওয়া হলো—
