पोस्टफिक्स से लेकर इंफ़िक्स नोटेशन तक

Habré पर रिवर्स पोलिश नोटेशन (रिकॉर्ड) के बारे में पहले ही बताया जा चुका है। जैसा कि आप जानते हैं, गणितीय अभिव्यक्ति के उपसर्ग संकेतन में बन्दी की सारी शक्ति। उपनिषद से हमें अवगत कराए जाने वाले इन्फिक्स नोटेशन को ऊपर के लेख में विकिपीडिया पर विस्तार से वर्णित किया गया है, और यहां तक ​​कि असेंबलर में कार्यान्वयन भी दिया गया है । लेकिन मुझे यह नहीं मिला कि रिवर्स एक्शन को कैसे क्रैंक किया जाए।



शायद पहला सवाल जो आप पूछते हैं: "इसकी आवश्यकता क्यों है?" कल्पना करें कि हम उपयोगकर्ता द्वारा दर्ज की गई अभिव्यक्ति को अनुकूलित करते हैं और हमें एक इनफ़िक्स रिकॉर्ड में परिणाम दिखाने की आवश्यकता है, और हम निश्चित रूप से, बन्दी का उपयोग करके अनुकूलन करेंगे।

खैर, अब बिंदु के करीब:

एल्गोरिथ्म का मौखिक विवरण:

1. यदि हम एक संख्या पढ़ते हैं, तो हम इसे स्टैक पर धकेल देते हैं
2. यदि हम ऑपरेशन संकेत पढ़ते हैं, तो:
   
   • हम 2 शीर्ष स्टैक तत्व लेते हैं
   • यदि पहले तत्व में ऑपरेशन की प्राथमिकता कम है (और 0 के बराबर नहीं है) तो सवाल में ऑपरेशन की तुलना में, तो हम पहले तत्व को कोष्ठक में लेते हैं
   • इसी तरह से दूसरे तत्व के लिए
   • हम स्टैक पर फ़ॉर्म की एक पंक्ति लिखते हैं: 2 तत्व + ऑपरेशन साइन + 1 तत्व
   
   
3. यदि रेखा पूरी तरह से फंस गई है, तो परिणाम स्टैक के शीर्ष का मूल्य है

C ++ कार्यान्वयन

#include <string.h> #include <stdio.h> #include <stdlib.h> // <-- --> enum optype {power = 3, devide = 2, multiply = 2, minus = 1, plus = 1, null=0}; //   struct stack { char val[100]; //    optype type; //  ,      stack * next; } *head; // <--   --> void push(char[], optype); void push(stack *); stack * pop(); // <--   --> void fromRPN(char *, char *); // (RPN) Reverse polish notation int main() { char infix[100], postfix[100]; //     gets(infix); fromRPN(infix, postfix); printf("%s\n", postfix); system("PAUSE"); return 0; } void push(stack *t) { t->next = head; head = t; } void push(char str[], optype type) { stack *t; t = new stack; strcpy(t->val, str); t->type = type; t->next = head; head = t; } stack * pop() { stack *t; if(head == NULL) return NULL; t = head; head = t->next; return t; } void fromRPN(char * input, char * output) { char c, temp[100]; int p_temp=0; stack *h1, *h2; //        optype type; head = NULL; while(*input) { //     c = (*input); if(c>='0' && c<='9' || c=='.') { //     temp[p_temp++] = c; //      temp[p_temp] = '\0'; } else if(c==' ') { if(p_temp!=0) { push(temp, null); //     p_temp=0; } temp[0] = '\0'; //    } else if(c=='+' || c=='-'|| c=='*' || c=='/' || c=='^') { //    h1 = pop(); //    h2 = pop(); //    //    if(c=='+') type = plus; else if(c=='-') type = minus; else if(c=='*') type = multiply; else if(c=='/') type = devide; else if(c=='^') type = power; if(h2->type!=null && h2->type<type) { //    1-   temp[0]='('; temp[1] = '\0'; //     h2->val[strlen(h2->val)+2] = '\0'; h2->val[strlen(h2->val)+1] = c; //    h2->val[strlen(h2->val)] = ')'; } else { h2->val[strlen(h2->val)+1] = '\0'; h2->val[strlen(h2->val)] = c; } strcat(temp, h2->val); if(h1->type!=null && h1->type<type) { //    2-   strcat(temp, "("); h1->val[strlen(h1->val)+1] = '\0'; h1->val[strlen(h1->val)] = ')'; //     } strcat(temp, h1->val); strcpy(h2->val, temp); //        ,       delete h1; //    h2->type = type; //     push(h2); //      } input++; } strcpy(output, (pop())->val); //         } 

काम का उदाहरण

एक उदाहरण के लिए हम हब्र के एक लेख में एक उदाहरण से रूपांतरित अभिव्यक्ति को लेंगे:

 : (8+2*5)/(1+3*2-4) : 8 2 5 * + 1 3 2 * + 4 - /  "8" : {"8", null=0}  "8" --: {"8", null=0}  "2" --: {"2", null=0}, {"8", null=0}  "5" --: {5, null=0}, {"2", null=0}, {"8", null=0}  "*" --: {"2*5", multiply=2}, {"8", null=0}  "+" --: {"8+2*5", plus=1}  "1" --: {"1", null=0}, {"8+2*5", plus=1}  "3" --: {"3", null=0}, {"1", null=0}, {"8+2*5", plus=1}  "2" --: {"2", null=0}, {"3", null=0}, {"1", null=0}, {"8+2*5", plus=1}  "*" --: {"3*2", multiply=2}, {"1", null=0}, {"8+2*5", plus=1}  "+" --: {"1+3*2", plus=1}, {"8+2*5", plus=1}  "4" --: {"4", null=0}, {"1+3*2", plus=1}, {"8+2*5", plus=1}  "-" --: {"1+3*2-4", minus=1}, {"8+2*5", plus=1}  "/" //    ,      --: {"(8+2*5)/(1+3*2-4)", devide=2} : (8+2*5)/(1+3*2-4)