ইনফিক্স থেকে পোস্টফিক্স এক্সপ্রেশন রূপান্তর

ইনফিক্স এক্সপ্রেশন মানুষ পড়ে এবং সমাধান করতে পারে। আমরা সহজে অপারেটরদের অগ্রাধিকার বুঝতে পারি এবং গাণিতিক এক্সপ্রেশন সমাধানের সময় পারেন্থেসিস ব্যবহার করে কোন অংশটি প্রথমে সমাধান করতে হবে তা নির্দেশ করতে পারি। কম্পিউটার অপারেটর এবং পারেন্থেসিস সহজে পার্থক্য করতে পারে না, তাই পোস্টফিক্স রূপান্তর দরকার।

ইনফিক্স এক্সপ্রেশনকে পোস্টফিক্সে রূপান্তর করতে স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করা হয়। ইনফিক্স এক্সপ্রেশন বাম থেকে ডানে স্ক্যান করার সময় যখন কোনো অপারেন্ড পাওয়া যায়, সেটি সরাসরি পোস্টফিক্স ফর্মে যোগ করা হয়। অপারেটর এবং পারেন্থেসিসের জন্য সেগুলো তাদের প্রসিডেন্স মেনে স্টকে যোগ করা হয়।

নোট: এখানে শুধু {+, -, *, /, ^} অপারেটর বিবেচনা করা হয়েছে, অন্যান্য অপারেটর উপেক্ষা করা হয়েছে।

ইনপুট এবং আউটপুট

ইনপুট: ইনফিক্স এক্সপ্রেশন: x^y/(5*z)+2
আউটপুট: পোস্টফিক্স ফর্ম: xy^5z*/2+

অ্যালগরিদম

infixToPostfix(infix)

ইনপুট: ইনফিক্স এক্সপ্রেশন।
আউটপুট: ইনফিক্স এক্সপ্রেশনকে পোস্টফিক্স ফর্মে রূপান্তর।

শুরু
  স্টকে বিশেষ ক্যারেক্টার # পুশ করুন
  ইনফিক্স এক্সপ্রেশনের প্রতিটি ক্যারেক্টার ch জন্য, করুন
    যদি ch অ্যালফানিউমেরিক ক্যারেক্টার হয়, তবে
      ch পোস্টফিক্স এক্সপ্রেশনে যোগ করুন
    অন্যথায় যদি ch = '(' হয়, তবে
      '(' স্টকে পুশ করুন
    অন্যথায় যদি ch = '^' হয়, তবে
      '^' স্টকে পুশ করুন
    অন্যথায় যদি ch = ')' হয়, তবে
      স্টক খালি না হওয়া পর্যন্ত এবং স্টক টপ ≠ '(' পর্যন্ত
        স্টকে থেকে পপ করে পোস্টফিক্সে যোগ করুন
      '(' স্টকে থেকে পপ করুন
    অন্যথায়
      স্টক খালি না হওয়া পর্যন্ত এবং ch-এর প্রসিডেন্স <= স্টক টপের প্রসিডেন্স পর্যন্ত
        পপ করে পোস্টফিক্সে যোগ করুন
      নতুন ক্যারেক্টারটি পুশ করুন
  끝난
  স্টকে অবশিষ্ট ক্যারেক্টার থাকার পর্যন্ত
    পপ করে পোস্টফিক্সে যোগ করুন
  끝난
  পোস্টফিক্স ফেরত দিন
শেষ

উদাহরণ (C++)

#include <iostream>
#include <stack>
#include <locale>
using namespace std;

int preced(char ch) {
  if(ch == '+' || ch == '-') return 1;
  else if(ch == '*' || ch == '/') return 2;
  else if(ch == '^') return 3;
  else return 0;
}

string inToPost(string infix) {
  stack stk;
  stk.push('#');
  string postfix = "";
  string::iterator it;
  for(it = infix.begin(); it != infix.end(); it++) {
    if(isalnum(char(*it)))
      postfix += *it;
    else if(*it == '(')
      stk.push('(');
    else if(*it == '^')
      stk.push('^');
    else if(*it == ')') {
      while(stk.top() != '#' && stk.top() != '(') {
        postfix += stk.top();
        stk.pop();
      }
      stk.pop();
    } else {
      if(preced(*it) > preced(stk.top()))
        stk.push(*it);
      else {
        while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
          postfix += stk.top();
          stk.pop();
        }
        stk.push(*it);
      }
    }
  }
  while(stk.top() != '#') {
    postfix += stk.top();
    stk.pop();
  }
  return postfix;
}

int main() {
  string infix = "x^y/(5*z)+2";
  cout << "Postfix Form Is: " << inToPost(infix) << endl;
}

আউটপুট

Postfix Form Is: xy^5z*/2+