Post updated on 24th January, 2017 at 12:49 am
Problem Definition
আমরা সায়েন্টিফিক ক্যালকুলেটরে (34+(34/4)*344^3) এ ধরণের হিসাব নিকাশ সরাসরি করতে পারি। Operator precedence হিসেবে যেই অপারেশনের কাজ আগে হওয়া উচিত ক্যালকুলেটর সেই অপারেশনের কাজটাই আগে করে। উল্লেখিত expression এ যেমন, 344^3 এর কাজটা সবার আগে হবে। আমরা সাদারণ যোগ-বিয়োগ-গুণ-ভাগ খুব সহজেই প্রোগ্রাম লিখে বের করতে পারি। কিন্তু আমাদের প্রোগ্রামে উপরের মত একটা এক্সপ্রেশন ইনপুট দিলে সেটা কি আমরা বের করতে পারি? বেশ কিছু ব্যাপার এক্ষেত্রে মাথায় রাখতে হয়। যেমন কোন অপারেশনটা আগে হবে, ব্র্যাকেটের শুরু ও শেষ ইত্যাদি। এই জিনিসগুলো কিভাবে হ্যান্ডেল করা যায়?
কিছুক্ষণ এই সমস্যাটা নিয়ে ভাবো। একটা string ইনপুট দেয়া থাকবে [ধরো স্ট্রিংটা হচ্ছে (1+(2^3)*4)/3. সংখ্যাগুলো হবে ১ অংক বিশিষ্ট। ব্র্যাকেট হিসেবে ব্যবহার করা হবে () এবং অপারেটর হিসেবে ব্যবহার হবে +, -, *, / ও ^]. তোমাকে একটা প্রোগ্রাম লিখে (1+(2^3)*4)/3-কে evaluate করে result বের করতে হবে 11.
কী? কোন আইডিয়া পাওয়া গেল? আচ্ছা চিন্তা করতে থাকো, ততক্ষণে নতুন ২-১ টা জিনিস সম্পর্কে জেনে নিই।
Arithmetic expressions; Polish Notation
যে কোন arithmetic operation কে আমরা ৩ ভাবে প্রকাশ করতে পারি। সেগুলো হচ্ছে Infix notation, Polish notation ও Postfix notation.
Infix notation: আমরা সাধারণত যেভাবে কোন একটা equation লিখি অর্থাৎ একটা arithmetic operator এর দুই পাশে দুটি operand থাকে। অপারেটরটা ঐ অপারেন্ড দুটির উপর কাজ করে। এই প্রকাশ পদ্ধতিই হচ্ছে infix expression. যেমনঃ A + B. A ও B হচ্ছে operand এবং + হচ্ছে অপারেটর। অপারেটরটি অপারেন্ড দুটির মাঝে বসেছে।
Polish notation: এই পদ্ধতিতে অপারেটর বসে অপারেন্ড দুটির শুরুতে। যেমনঃ +AB বলতে বুঝাচ্ছে A আর B-কে যোগ করতে হবে।
Postfix notation: এক্ষেত্রে অপারেটর বসে অপারেন্ড দুটির পরে। একে Reverse Polish Notation-ও বলা হয়। যেমনঃ AB+ বলতে Aএবং B এর মাঝের যোগের সম্পর্কই বুঝাচ্ছে।
Infix to Postfix conversion
ধরো, ইনফিক্সে একটা এক্সপ্রেশন দেয়া আছে (A+(B^C)*D)/C. এটাকে পোস্টফিক্স নোটেশনে কনভার্ট করতে হবে। এতে সুবিধা হচ্ছে কোন ব্র্যাকেট থাকবে না এক্সপ্রেশনটিতে। আর অপারেটরগুলো এমন ভাবে সাজানো থাকবে যেন তাদের precedence অনুযায়ীই অপারেশনগুলো হয়। চলো কনভার্ট করিঃ
(A+(B^C)*D)/C
= (A+[BC^]*D)/C {exponent এর precedence সবচেয়ে বেশি তাই এটার কাজ আগে হয়েছে}
= (A+[BC^D*])/C {BC^ এর সাথে D এর গুণের সম্পর্ক। তাই এটার priority বেশি}
= ([ABC^D*+])/C {[BC^D*] এর সাথে A এর যোগের কাজের প্রাধান্য বেশি কারণ এরা () এর ভিতরে}
= ABC^D*+C/ {[ABC^D*+] কে ভাগ করা হয়েছে C দিয়ে}
অবশেষে ইনফিক্স নোটেশন (A+(B^C)*D)/C এর পোস্টফিক্স ফরমেট পাওয়া গেল ABC^D*+C/. একই ভাবে তুমি Infix to Polish notation এ রূপান্তর করতে পারবে। পার্থক্য শুধু “অপারেটরগুলো পরে না লিখে আগে লিখবে”।
Infix expression তো অত্যন্ত সুন্দর, সহজ ও সাবলীল। কী দরকার বাকিগুলো নিয়ে ঘাটার? এগুলো শেখারই বা দরকার কী? দেখো, ইনফিক্সটা মানুষ খুব সহজে বুঝতে পারে। আমরা এই নোটেশনে লিখা যে কোন এক্সপ্রেশন দ্রুত হিসাব করে বের করতে পারি। কিন্তু মেশিনের ক্ষেত্রে এটা থেকে আউটপুট বের করা একটু কষ্টকর। যেমন ধরোঃ (1+(2^3)*4)/3 এই ইনফিক্স নোটেশনটা। এটার থেকে আউটপুট বের করার জন্য কার সাথে কাকে যোগ করবে কোনটার কাজ আগে হবে, কোনটা পরে হবে সেটা ঠিক রাখা কঠিন। কিন্তু এই এক্সপ্রেশনটাকে যদি পোস্টফিক্স নোটেশনে কনভার্ট করি তাহলে পাওয়া যাবেঃ 1 2 3^4 *+ 3 /; যা কম্পিউটার সহজে সমাধান করতে পারবে। যেহেতু Polish notation এবং Postfix notation এর মাঝে কোন ব্র্যাকেট থাকে না তাই অনেকখানি চিন্তা কমিয়ে দেয় এই নোটেশনগুলো। তুমি তো এখন ইনফিক্স থেকে পোস্টফিক্সে কনভার্ট করতে পারই। তাহলে এখন শিখে ফেল কিভাবে কম্পিউটার এই পোস্টফিক্সটাকে evaluate করবে।
Evaluation of Postfix notation
1 2 3 ^ 4 * + 3 / এর বাম দিক থেকে পড়া শুরু করি। 1, 2, 3 এর পরে পাওয়া গেল ^. যেহেতু পোস্টফিক্স তার মানে এই অপারেটর কাজ করবে তার আগে থাকা দুটি অপারেন্ডের উপর। অর্থাৎ 2^3 = 8 এর কাজটা প্রথমে হবে। এই রেজাল্টটা বসিয়ে দিব 2 3 ^ এর স্থলে। তাহলে নতুন এক্সপ্রেশনটা দাঁড়ায় 1 8 4 * + 3 /. এরপর যথারীতি ডান দিকে এগিয়ে যেতে থাকি। পাওয়া গেল 4. আর এক ঘর সামনে গেলে পাওয়া গেল * চিহ্ন। তাহলে এই গুণ চিহ্ন কোন দুইটা সংখ্যার উপর কাজ করবে? ঠিক ধরেছ! 8 * 4 = 32 এর হিসাব হবে এখন। 32 কে আগের নিয়মে বসিয়ে দেই 8 4 * এর স্থলে। নতুন এক্সপ্রেশন দাঁড়ায়ঃ 1 32 + 3 /. আরেক ঘর ডানে গিয়ে পাওয়া গেল + চিহ্ন। 1 + 32 = 33. আপডেটেড এক্সপ্রেশনটা এখনঃ 33 3 /. এবং ফাইনালি কাজ হবে 33 / 3 = 11
অর্থাৎ 1 2 3 ^ 4 * + 3 / = 11
Line by line execution:
Given, 1 2 3 ^ 4 * + 3 / as a postfix notation.
1 2 3 ^ 4 * + 3 /
= 1 8 4 * + 3 /
= 1 32 + 3 /
= 33 3 /
= 11
সহজ না? দেখো, আমাদের কিন্তু ব্র্যাকেট নিয়ে কোনো চিন্তাই করা লাগে নাই। কোন্ অপারেটরের কাজ আগে করবো কোনটার কাজ পরে করব এসব নিয়েও চিন্তা করতে হয় নাই। পোস্টফিক্সের বাম থেকে ডানে গেছি, সামনে যেই অপারেটর পড়েছে তার আগের দুইটা সংখ্যা নিয়ে সেই অপারেটরের কাজ করে রেজাল্টটা ঐ অপারেশনের জায়গায় বসিয়ে দিয়েছি। ব্যস শেষ!
খুব বিরক্ত হচ্ছ তাই না? শুরুতে একটা প্রবলেম মাথায় দিয়ে এখন কী সব নিয়ে ফ্যাঁচফ্যাঁচ করছি!!! ওয়েট!!! তুমি যদি ইনফিক্স থেকে পোস্টফিক্স বের করার সিসটেম আর পোস্টফিক্স থেকে কোন এক্সপ্রেশন evaluation করাটা বুঝে গিয়ে থাকো তাহলে তোমার ঐ সায়েন্টিফিক ক্যালকুলেটরের প্রবলেম সলভড! এই পোস্টের বাকি অংশ না পড়লেও চলবে। নিজে নিজে মাথা খাটিয়ে কোড করে ফেল! কোথাও আটকে গেলে পোস্টের বাকি অংশ দেখে নিও।
Solution
এতসব আলোচনা থেকে তুমি এতক্ষণে বুঝে গিয়ে থাকবে যে ব্র্যাকেট, অনেকগুলো অপারেটর ও অপারেন্ডের সমন্বয়ে কোন একটা এক্সপ্রেশনকে evaluate করে মান বের করার জন্য সেই এক্সপ্রেশনটাকে হতে হবে Polish notation অথবা Reverse Polish বা Postfix Notation. ইউজার যেহেতু আমাদেরকে Infix notation এ ইনপুট দিবে তাই এজন্য আমাদেরকে প্রথমেই সেই এক্সপ্রেশনটাকে পোস্টফিক্সে কনভার্ট করতে হবে। এরপর এই পোস্টফিক্স এক্সপ্রেশনকে আগের প্যারার মত করে evaluate করতে হবে। কাজের সুবিধার জন্য আমরা দুইটা function লিখব। একটার কাজ হবে পোস্টফিক্সে কনভার্ট করা আরেকটার কাজ হচ্ছে পোস্টফিক্স থেকে মান বের করা। পাশাপাশি আরো ২-১ টা সাহায্যকারী ফাংশন লিখার দরকার হবে।
এখন যেহেতু সরাসরি কোডে চলে যাব তার আগে মনে করিয়ে দিতে চাই এটার জন্য আমাদেরকে স্ট্যাকের ব্যাসিক আইডিয়া থাকা লাগবে। যদি স্ট্যাক আগে না করে থাকো বা ভুলে গিয়ে থাকো তাহলে দেখে আসতে পারো এখান থেকে।
এখন দেখবো পোস্টফিক্সে কনভার্ট করার কোড। কোডের সাইজ একটু বড়। কিন্তু আইডিয়াটা জটিল না। শুরুতে অ্যালগরিদমটা একটু মাথায় গেঁথে নিলে নিজে নিজেই কোড বুঝে যাবে।
Infix to Postfix conversion Algorithm
- ইনপুট হওয়া এক্সপ্রেশনের বাম থেকে ডানে লুপের মাধ্যমে read করতে থাকো
- যদি ‘(‘ পাওয়া যায় তাহলে সেটাকে stack এ push করো
- যদি ‘)’ পাওয়া যায় তাহলে তোমার stack থেকে একটা একটা করে element উঠিয়ে (pop) postfix এর স্ট্রিং এ add করতে থাকো, যতক্ষণ পর্যন্ত ‘(‘ না পাওয়া যায়। ‘(‘ পাওয়া গেলে সেটাকে pop করে দাও
- যদি কোন operand পাওয়া যায় তাহলে তাকে postfix string এ এড করে দাও
- যদি operator পাওয়া যায় তাহলে স্ট্যাক খালি থাকলে তাকে স্ট্যাকে push করো। অন্যথায় এই অপারেটরের চেয়ে কম precedence এর অপারেটরগুলো স্ট্যাক থেকে উঠিয়ে (pop) postfix string এ যোগ করতে থাকো। করা হয়ে গেলে এই অপারেটরকে স্ট্যাকে push করো
- পুরো স্ট্রিং traverse করা হয়ে গেলে যদি স্ট্যাকে কিছু থাকে তাহলে সেগুলোকে একটা একটা করে উঠিয়ে (pop) পোস্টফিক্সের স্ট্রিং এ যোগ করে দাও
Infix to Postfix conversion Source Code
string convertInfixToPostfix(string infix)
{
string postfix = "";
stack <char> myStack;
char ch;
for(int i=0; infix[i]; i++)
{
ch = infix[i];
if(ch=='(') //if found opening bracket
myStack.push(ch);
else if(ch==')') //if found closing bracket
{
while(!myStack.empty() && myStack.top()!='(')
{
postfix = postfix + myStack.top();
myStack.pop();
}
if(!myStack.empty() && myStack.top()=='(')
myStack.pop();
}
else //found operator or operand
{
//^ is highest, then * and /. then + and -
int priority = operatorPrecedence(ch);
if(priority==0) //found operand
postfix = postfix + ch;
else //found operator
{
if(myStack.empty())
myStack.push(ch);
else
{
while(!myStack.empty()
&& myStack.top()!='('
&& priority<=operatorPrecedence(myStack.top()))
{
postfix = postfix + myStack.top();
myStack.pop();
}
myStack.push(ch);
}
}
}
}
while(!myStack.empty())
{
postfix += myStack.top();
myStack.pop();
}
return postfix;
}
Postfix evaluation Algorithm
- Postfix notation এর শুরু থেকে শেষ পর্যন্ত লুপের মাধ্যমে traverse করো
- কোনো operand পাওয়া গেলে তাকে stack এ পুশ করো
- কোন অপারেটর পাওয়া গেলে স্ট্যাকের top এ থাকা দুটি operand কে তুলে (pop) তাদের মধ্যে এই অপারেটরের অপারেশন সম্পন্ন করে রেজাল্টটা স্ট্যাকে পুশ করো
- পুরো স্ট্রিং traverse করা হয়ে গেলে স্ট্যাকে একটাই element থাকবে। আর এটাই কাংক্ষিত ফলাফল
Postfix evaluation Source Code
int evaluatePostfixExpression(string postfix)
{
stack <int> myStack;
char ch;
//1 2 3 ^ 4 * + 3 /
for(int i=0; postfix[i]; i++)
{
ch = postfix[i];
if(ch>='0' && ch<='9') //found operand
myStack.push(ch-'0'); //char to int conversion
else //found operator
{
int a,b;
b = myStack.top();
myStack.pop();
a = myStack.top();
myStack.pop();
myStack.push(calculate(a, b, ch));
}
}
return myStack.top();
}
এই প্রোগ্রামে একটা সমস্যা হয়ত মাথায় আসতে পারে। তা হচ্ছে যেই ইনফিক্স নোটেশন ইনপুট দেয়া হবে সেটা ভ্যালিড কিনা। মানে সেটার অপারেটর বা ব্র্যাকেট ঠিকঠাক মত আছে কিনা। এক্সপ্রেশনের ভ্যালিডিটি চেক করার ব্যাপারটা এখানে স্কিপ করা হয়েছে। তুমি চাইলে নিজেই একটা এক্সপ্রেশনের ভ্যালিডিটি চেক করতে পারবে স্ট্যাক ব্যবহার করে ব্র্যাকেটের ব্যালেন্স চেকিং এই পোস্টটি পড়লে।
আশা করি পুরো ব্যাপারটা বুঝা গিয়েছে। কোথাও কোন সমস্যা হলে বা ভুল চোখে পড়লে কমেন্ট করার অনুরোধ রইলো।
পুরো প্রোগ্রামটা একসাথে পাওয়া যাবে আমার গিটহাব রিপোজিটরিতে।
৫ নাম্বার পয়েন্ট টা একটু দয়া করে চেক করবেন কি? যেই অপারেটর আসবে, স্ট্যাক এ যদি তার চেয়ে বড় বা সমান প্রিসিডেন্সের অপারেটর থাকে এবং স্ট্যাক টপে “(” যদি না থাকে , তাহলেই না স্ট্যাক থেকে পপ করা হয়? ভুল হলে ক্ষমা সুন্দর দৃষ্টিতে দেখবেন