Postfix to infix notation

On the reverse Polish notation (writing) on ​​Habré already told . As is well known, the whole power of a surge arrester in a postfix math expression. About how to convert the usual infix to postfix notation is described in detail in the article above, on Wikipedia, and even the implementation is given in Assembler . But I didn’t find any articles on how to reverse the action.



Probably the first question that you ask: "Why is it necessary?". Imagine that we are optimizing the user-entered expression and the result we need to show in the infix notation, and we will, of course, optimize using the arrester.
')
Well, now closer to the point:

Verbal description of the algorithm:

1. If we read a number, we put it on the stack.
2. If we read the sign of the operation, then:
   
   • Take the top 2 stack items
   • If in the first element the priority of the operation is lower (and not equal to 0) than that of the considered operations, then we take the first element in brackets
   • Similarly for the 2nd element
   • Write to the stack a line of the form: 2nd element + operation sign + 1st element
   
   
3. If the line is completely passed, the result is the value of the top of the stack.

C ++ implementation

#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); //         } 

Work example

For example, take the transformed expression from the example in the article with the habr:

 : (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)