मान लीजिए कि हमारे पास रिवर्स पॉलिश नोटेशन है और हमें वैल्यू का मूल्यांकन करना है। रिवर्स पॉलिश नोटेशन को पोस्टफिक्स एक्सप्रेशन के रूप में भी जाना जाता है। यहां हमें पोस्टफिक्स एक्सप्रेशन को हल करने के लिए स्टैक डेटा संरचना का उपयोग करना होगा।
पोस्टफ़िक्स एक्सप्रेशन से, जब कुछ ऑपरेंड मिलते हैं, तो उन्हें स्टैक में धकेल दिया जाता है। जब कुछ ऑपरेटर मिलते हैं, तो दो आइटम स्टैक से पॉप किए जाते हैं और फिर ऑपरेशन सही क्रम में किया जाता है। उसके बाद, परिणाम को भविष्य में उपयोग के लिए स्टैक में भी धकेल दिया जाता है। पूरे एक्सप्रेशन को पूरा करने के बाद फाइनल रिजल्ट भी स्टैक टॉप में स्टोर हो जाता है। तो यदि व्यंजक “53+62/*35*+” है, तो उत्तर 39
. होगाआइए चरणों को देखें -
- पोस्टफ़िक्स एक्सप्रेशन में प्रत्येक वर्ण ch के लिए, करें
- यदि ch एक संकारक है ☉ , तो
- a :=स्टैक से पहला तत्व पॉप करें,
- b :=स्टैक से दूसरा तत्व पॉप करें
- res :=b ☉ a
- रेस को स्टैक में पुश करें
- अन्यथा यदि ch एक संकार्य है, तो
- ch को स्टैक में जोड़ें
- यदि ch एक संकारक है ☉ , तो
- स्टैक टॉप का रिटर्न एलिमेंट
उदाहरण(C++)
एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -
#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
using namespace std;
float scanNum(char ch){
int value;
value = ch;
return float(value-'0');//return float from character
}
int isOperator(char ch){
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1;//character is an operator
return -1;//not an operator
}
int isOperand(char ch){
if(ch >= '0' && ch <= '9')
return 1;//character is an operand
return -1;//not an operand
}
float operation(int a, int b, char op){
//Perform operation
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //find b^a
else
return INT_MIN; //return negative infinity
}
float postfixEval(string postfix){
int a, b;
stack<float> stk;
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++){
//read elements and perform postfix evaluation
if(isOperator(*it) != -1){
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}
else if(isOperand(*it) > 0){
stk.push(scanNum(*it));
}
}
return stk.top();
}
main(){
string post = "53+62/*35*+";
cout << "The result is: "<<postfixEval(post);
} इनपुट
"53+62/*35*+"
आउटपुट
The result is: 39