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

কম্পিউটারের দ্বারা এক্সপ্রেশন সমাধানের জন্য সেটিকে পোস্টফিক্স বা প্রিফিক্স ফর্মে রূপান্তর করা যায়। এখানে আমরা দেখব কীভাবে ইনফিক্স এক্সপ্রেশন প্রিফিক্স ফর্মে রূপান্তর করা হয়।

প্রথমে ইনফিক্স এক্সপ্রেশনটি উল্টা (reverse) করা হয়। লক্ষ্য করুন উল্টা করার সময় ওপেনিং এবং ক্লোজিং পারেন্থেসিসও উল্টা হবে।

উদাহরণ: এক্সপ্রেশন: A + B * (C - D)

উল্টা করার পর: ) D - C ( * B + A

তাই ওপেনিং পারেন্থেসিসকে ক্লোজিং এবং ক্লোজিংকে ওপেনিং-এ রূপান্তর করতে হয়।

উল্টা করার পর, এক্সপ্রেশনকে ইনফিক্স-টু-পোস্টফিক্স অ্যালগরিদম ব্যবহার করে পোস্টফিক্স ফর্মে রূপান্তর করা হয়। তারপর পোস্টফিক্স এক্সপ্রেশনটিকে আবার উল্টা করে প্রিফিক্স এক্সপ্রেশন পাওয়া যায়।

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

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

অ্যালগরিদম

infixToPrefix(infix)

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

শুরু
  ইনফিক্স এক্সপ্রেশন উল্টা করুন
  উল্টা করা ইনফিক্স এক্সপ্রেশনের প্রতিটি ক্যারেক্টার ch জন্য, করুন
    যদি ch = '(' হয়, তবে
      ch কে ')' তে রূপান্তর করুন
    অন্যথায় যদি ch = ')' হয়, তবে
      ch কে '(' তে রূপান্তর করুন
  끝난
  postfix := উল্টা করা ইনফিক্সকে পোস্টফিক্সে রূপান্তর করুন
  prefix := সম্প্রতি গণনা করা পোস্টফিক্স ফর্ম উল্টা করুন
  prefix ফেরত দিন
শেষ

উদাহরণ (C++)

#include <iostream>
#include <stack>
#include <locale>
#include <algorithm>
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;
}

string inToPre(string infix) {
  string prefix;
  reverse(infix.begin(), infix.end());
  string::iterator it;
  for(it = infix.begin(); it != infix.end(); it++) {
    if(*it == '(') *it = ')';
    else if(*it == ')') *it = '(';
  }
  prefix = inToPost(infix);
  reverse(prefix.begin(), prefix.end());
  return prefix;
}

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

আউটপুট

Prefix Form Is: +/^xy*5z2