मान लीजिए हमारे पास रिवर्स पोलिश नोटेशन (Reverse Polish Notation) है और हमें उसका मान निकालना है। रिवर्स पोलिश नोटेशन को पोस्टफिक्स एक्सप्रेशन (postfix expression) के नाम से भी जाना जाता है। यहां हमें पोस्टफिक्स एक्सप्रेशन को हल करने के लिए स्टैक डेटा संरचना का उपयोग करना होगा।
पोस्टफिक्स एक्सप्रेशन से, जब कुछ ऑपरेंड मिलते हैं, तो उन्हें स्टैक में पुश किया जाता है। जब कोई ऑपरेटर मिलता है, तो स्टैक से दो आइटम पॉप किए जाते हैं और फिर सही क्रम में ऑपरेशन किया जाता है। उसके बाद, परिणाम को भविष्य के उपयोग के लिए स्टैक में भी पुश किया जाता है। पूरे एक्सप्रेशन को पूरा करने के बाद, अंतिम परिणाम भी स्टैक के शीर्ष पर स्टोर होता है। यदि एक्सप्रेशन "53+62/*35*+" है, तो उत्तर 39 होगा।
आइए चरण देखें:
- पोस्टफिक्स एक्सप्रेशन के प्रत्येक वर्ण ch के लिए:
- यदि ch एक ऑपरेटर ☉ है, तो:
- a := स्टैक से पहला तत्व पॉप करें
- b := स्टैक से दूसरा तत्व पॉप करें
- res := b ☉ a
- res को स्टैक में पुश करें
- अन्यथा यदि 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');
}
int isOperator(char ch){
if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^')
return 1;
return -1;
}
int isOperand(char ch){
if(ch >= '0' && ch <= '9')
return 1;
return -1;
}
float operation(int a, int b, char op){
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);
else return INT_MIN;
}
float postfixEval(string postfix){
int a, b;
stack<float> stk;
string::iterator it;
for(it = postfix.begin(); it != postfix.end(); it++){
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();
}
int main(){
string post = "53+62/*35*+";
cout << "परिणाम है: " << postfixEval(post);
}
इनपुट
"53+62/*35*+"
आउटपुट
परिणाम है: 39
