इस लेख में, हम उपसर्ग अभिव्यक्ति के मूल्यांकन पर चर्चा करेंगे।
उपसर्ग अभिव्यक्ति
इस नोटेशन में, ऑपरेटर उपसर्ग . है ऑपरेंड के लिए, यानी ऑपरेटर को ऑपरेंड के आगे लिखा जाता है। उदाहरण के लिए, +ab . यह इसके इंफिक्स नोटेशन a + b . के बराबर है . उपसर्ग संकेतन को पोलिश संकेत . के रूप में भी जाना जाता है ।
अधिक पढ़ने के लिए।
उदाहरण:
* + 6 9 - 3 1
उपसर्ग अभिव्यक्तियों का मूल्यांकन इंफिक्स अभिव्यक्तियों की तुलना में तेजी से किया जाता है। साथ ही, प्रीफ़िक्स एक्सप्रेशन में ऐसे कोई कोष्ठक नहीं हैं जो इसे जल्दी मूल्यांकन करते हैं।
उपसर्ग अभिव्यक्ति का मूल्यांकन करने के लिए एल्गोरिदम:
उपसर्ग अभिव्यक्ति के मूल्यांकन के लिए एक स्टैक डेटा संरचना की आवश्यकता होती है। हम ऑपरेटरों को स्टैक में धकेलेंगे और फिर व्यंजक को हल करेंगे।
हम व्यंजक के प्रत्येक अवयव को एक-एक करके देखेंगे। यदि वर्तमान तत्व एक ऑपरेंड है, तो हम इसे स्टैक पर धकेल देंगे। और अगर यह एक ऑपरेटर है, तो हम दो ऑपरेंड पॉप करेंगे, ऑपरेशन करेंगे, ऑपरेंड ऑपरेटर ऑपरेंड करेंगे और फिर परिणाम को स्टैक पर वापस धकेलेंगे।
एल्गोरिदम -
चरण 1: व्यंजक के अंतिम तत्व से प्रारंभ करें।
चरण 2: वर्तमान तत्व की जाँच करें।
चरण 2.1: यदि यह एक ऑपरेंड है, तो इसे स्टैक पर पुश करें।
चरण 2.2: यदि यह एक ऑपरेटर है, तो स्टैक से दो ऑपरेंड पॉप करें। ऑपरेशन करें और तत्वों को वापस स्टैक पर धकेलें।
चरण 3: ऐसा तब तक करें जब तक कि व्यंजक के सभी तत्वों को पार न कर लिया जाए और स्टैक के शीर्ष को वापस कर दें जो ऑपरेशन का परिणाम होगा।
आइए एक उपसर्ग व्यंजक को हल करने के लिए हमारे एल्गोरिथम की कार्यप्रणाली को देखते हैं,
उपसर्ग व्यंजक :
* + 6 9 - 3 1
पुनरावृत्ति :1
एलिमेंट स्कैन किया गया => 1
ऑपरेशन => स्टैक करने के लिए धक्का
स्टैक => 1
पुनरावृत्ति :2
स्कैन किया गया तत्व => 3
ऑपरेशन => स्टैक करने के लिए धक्का
स्टैक => 3, 1
पुनरावृत्ति :3
एलिमेंट स्कैन किया गया => -
ऑपरेशन => स्टैक से दो पॉप करें, ऑपरेशन करें और परिणाम को पीछे धकेलें।
3 - 1 =2
स्टैक => 2
पुनरावृत्ति :4
एलिमेंट स्कैन किया गया => 9
ऑपरेशन => स्टैक करने के लिए धक्का
ढेर => 9, 2
पुनरावृत्ति:5
एलिमेंट स्कैन किया गया => 6
ऑपरेशन => स्टैक करने के लिए धक्का
स्टैक => 6, 9, 2
पुनरावृत्ति :6
एलिमेंट स्कैन किया गया => +
ऑपरेशन => स्टैक से दो पॉप करें, ऑपरेशन करें और परिणाम को पीछे धकेलें।
6 + 9 =15
स्टैक => 15 , 2
पुनरावृत्ति :7
एलिमेंट स्कैन किया गया => **
ऑपरेशन => स्टैक से दो पॉप करें, ऑपरेशन करें और परिणाम को पीछे धकेलें।
15 * 2 =30
स्टैक => 30
अंत => स्टैक के शीर्ष पर लौटें, परिणाम =30.
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string prefixExp) {
stack<double> operendStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operendStack.push(prefixExp[i] - '0');
else {
double o1 = operendStack.top();
operendStack.pop();
double o2 = operendStack.top();
operendStack.pop();
if( prefixExp[i] == '+')
operendStack.push(o1 + o2);
else if( prefixExp[i] == '-')
operendStack.push(o1 - o2);
else if( prefixExp[i] == '*')
operendStack.push(o1 * o2);
else if( prefixExp[i] == '/')
operendStack.push(o1 / o2);
else{
cout<<"Invalid Expression";
return -1;
}
}
}
return operendStack.top();
}
int main()
{
string prefixExp = "*+69-31";
cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
return 0;
} आउटपुट -
The result of evaluation of expression *+69-31 is 30