text: /* This is the code for converting postfix expression to corresponding infix expression. The input is postfix expression(Eg: ab+).
   * This code gives output as the corresponding infix expression with parenthesis(a+b). This approach uses stack data structure.
   */
  
  #include<stdio.h>
  #include<stdlib.h>
  #include<stdio_ext.h>
  #include<string.h>
  
  //SIZE is the size of character array 'data' that holds intermediate expressions.
  #define SIZE 50
  
  /* Here, stack is implemented using linked list. Each node in linked list represents one element in stack. This is the definition of
   * each node of that linked list.
  */
  struct stackNode
  {
  	/* In process of converting postfix expression to infix expression, we need to push intermediate expressions in stack. To store
  	 * those expressions, character array 'data' is used. 'next' is the pointer pointing towards the next element in the stack.
  	 */
  	char data[SIZE];
  	struct stackNode *next;
  };
  
  //The function to check whether stack is empty or not.
  int isEmpty(struct stackNode *ftop)
  {
  	int rval = 0;
  	if (ftop == NULL)
  	{
  		rval = 0;
  	}
  	else
  	{
  		rval = 1;
  	}
  	return rval;
  }
  
  //The function to check whether stack is full or not.
  int isFull(struct stackNode *fnewnode)
  {
  	int rval = 0;
  	if (fnewnode == NULL)
  	{
  		rval = 0;
  	}
  	else
  	{
  		rval = 1;
  	}
  	return rval;
  }
  
  //Function to push element in the stack.
  int push(struct stackNode **ftop, char fidata[])
  {
  	struct stackNode *top = NULL, *newnode = NULL;
  	int rval = 0;
  	top = *ftop;
  
  	//Memory is assigned to element to be pushed.
  	newnode = (struct stackNode*) calloc(1, sizeof(struct stackNode));
  
  	//Check if stack is full or not. If not then push the character/expression.
  	rval = isFull(newnode);
  	if (rval == 1)
  	{
  		strcpy(newnode->data , fidata);
  		if (top == NULL)
  		{
  			top = newnode;
  		}
  		else
  		{
  			newnode->next = top;
  			top = newnode;
  		}
  	}
  	*ftop = top;
  
  	//rval=1 indicates successful push, else stack is full.
  	return rval;
  }
  
  //Function to pop an element from stack.
  int pop(struct stackNode **fhead, char fddata[])
  {
  	struct stackNode *head = NULL, *dnode = NULL;
  	int rval = 0;
  	head = *fhead;
  
  	//Check if stack is empty or not. If not, then pop the character/expression.
  	rval = isEmpty(head);
  	if (rval == 1)
  	{
  		dnode = head;
  		strcpy(fddata , dnode ->data);
  		head = head->next;
  		dnode->next = NULL;
  		free(dnode);
  		dnode = NULL;
  	}
  	*fhead = head;
  
  	//rval=1 indicates successful pop, else stack is empty.
  	return rval;
  }
  
  //Function to determine the priority of the character.
  int checkSymbol(char fsymbol)
  {
  	int pr = 0;
  
  	/* If fsymbol is operator(i.e +,-,*,/ or %) 1 is returned. Else if fsymbol is a operand(i.e either character or intermediate sub
  	 * expression) then 0 is returned.
  	 */
  	switch (fsymbol)
  	{
  		case '+':
  		case '-':
  		case '*':
  		case '/':
  		case '%':
  			pr = 1;
  			break;
  
  		default:
  			pr = 0;
  			break;
  		}
  		return pr;
  }
  
  //Function that evaluates the infix expression from postfix expression.
  void postfixToInfix(char fpostfix[SIZE], char finfix[SIZE])
  {
  	int i = 0, symbolCheck = 0 ;
  	char symbol = '\0';
  	char operator[2] = {'\0'}, operandExpression[10] = {'\0'}, operand1[SIZE] = {'\0'}, operand2[SIZE] = {'\0'} ;
  
  	//This approach requires a stack to store operands. opndtop is the top of the operand stack.
  	struct stackNode *opndtop = NULL ;
  
  	//iterate through input postfix string. i is the iterating variable.
  	while(fpostfix[i] != '\0')
  	{
  		//symbol contains character of postfix string.
  		symbol = fpostfix[i];
  
  		//Check whether current symbol is operand or operator by calling the function checkSymbol().
  		symbolCheck = checkSymbol(symbol);
  
  		/* If checkSymbol() returns 0, that means the symbol is operand. If it is operand, push it in the stack. Go to next character
  		 * in expression.
  		 *
  		 * If checkSymbol() does not returns 0, that means the symbol is operator(either +,-,* or /). If we encounter the operator, pop
  		 * 2 operands from the stack & concatinate the strings as (+operand1+operator+operand2+). This will give sub expression in
  		 * infix expression. Push this intermediate sub expression in the stack. Move on to next character in postfix string. Keep
  		 * doing this till last symbol is encountered.
  		 */
  		if(symbolCheck == 0)
  		{
  			operandExpression[0] = symbol ;
  			operandExpression[1] = '\0';
  			push(&opndtop , operandExpression);
  			i = i + 1 ;
  		}
  		else
  		{
  			operator[0] = symbol ;
  			operator[1] = '\0' ;
  		    pop(&opndtop , operand2);
  			pop(&opndtop , operand1);
  			strcpy(finfix, "(") ;
  			strcat(finfix, operand1) ;
  			strcat(finfix, operator) ;
  			strcat(finfix, operand2) ;
  			strcat(finfix, ")") ;
  		    push(&opndtop , finfix);
  			i = i + 1 ;
  		}
  	}
  
  	/* After the above while loop is completed, the stack contains only 1 element, i.e the final infix expression. Pop it. It is stored
  	 * in finfix.
  	 */
  	pop(&opndtop , finfix);
  }
  
  int main(void)
  {
  	char postfix[SIZE] = {'\0'}, infix[SIZE] = {'\0'};
  
  	//Taking input as the postfix expression.
  	printf("Enter the postfix expression = ");
  	__fpurge(stdin);
  	scanf("%9s", postfix);
  
  	//Call to the function postfix_to_infix
  	postfixToInfix(postfix, infix);
  
  	//Output the converted infix string.
  	printf("\nInfix expression = %s", infix);
  
  	return 0;
  }
  
  /*
   * Sample Input/Output:
   *
   * Input:
   * Enter a postfix expression = ABC*EF-/+
   *
   * Output:
   * Infix string = (A+((B*C)/(E-F)))
   *
   * Time Complexity: O(n) , where n is length of postfix expression.
   * Space Complexity: O(n) , where n is length of postfix expression.
   */
  
  