इस लेख में, हम प्रीफिक्स एक्सप्रेशन के मूल्यांकन पर चर्चा करेंगे।
प्रीफिक्स एक्सप्रेशन क्या है?
इस नोटेशन में, ऑपरेटर ऑपरेंड्स से पहले लिखा जाता है, यानी ऑपरेटर ऑपरेंड्स से पहले आता है। उदाहरण के लिए, +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> operandStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operandStack.push(prefixExp[i] - '0');
else {
double o1 = operandStack.top();
operandStack.pop();
double o2 = operandStack.top();
operandStack.pop();
if (prefixExp[i] == '+')
operandStack.push(o1 + o2);
else if (prefixExp[i] == '-')
operandStack.push(o1 - o2);
else if (prefixExp[i] == '*')
operandStack.push(o1 * o2);
else if (prefixExp[i] == '/')
operandStack.push(o1 / o2);
else {
cout << "Invalid Expression";
return -1;
}
}
}
return operandStack.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
