Entry

A C program for conversion of infix to postfix

May 10th, 2004 08:25
Sudipto Kumar Mukherjee,

Dear learner,
I am a MCA 1st year student. I was searching for the algorithm for
conversion of an Infix expression to a postfix one. This algoritm
is clearly & wonderfully mentioned by Knud van Eeden. You can refer
url: http://www.faqts.com/knowledge_base/view.phtml/aid/26070/fid/585
All I did is I implemented it immidiately through a C program.
And here is the complete program: (This ran in Turbo C++)
Please go down to where it begins with "HERE IS THE ACTUAL CODE:"
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <process.h>
#include <string.h>
#define INPUT 0
#define STACK 1
struct Node
{
 float value;
 struct Node* up;
};
typedef struct Node Stack;
float topValue(Stack **ptrBase)
{
 Stack *temp;
 temp = *ptrBase;
 if(temp == NULL)
 {
  printf("\nError: Stack empty. Haulting execution.");
  getch();
  exit(0);
 }
 while(temp->up!=NULL)
 temp = temp->up;
 return temp->value;
}
void push(Stack **ptrBase, float value)
{
 Stack *newNode,*temp;
 newNode = malloc(sizeof(Stack));
 if(newNode == NULL)
 {
  printf("\nFatal: Memory Allocation Error in function push(). Haulting 
Execution.");
  getch();
  exit(-1);
 }
 newNode->value = value;
 newNode->up = NULL;
 if(*ptrBase==NULL)
 {
  *ptrBase = newNode;
 }
 else
 {
  temp = *ptrBase;
  while(temp->up!=NULL)
  temp=temp->up;
  temp->up = newNode;
 }
}
float pop(Stack **ptrBase)
{
 Stack *temp;
 float value;
 /* case 1: head not formed. pop called illegaly */
 if(*ptrBase == NULL)
 {
  printf("\nError: Stack Empty!");
  return -1;
 }
 /* case 2: head is the only node */
 if((*ptrBase)->up == NULL)
 {
  value = (*ptrBase)->value;
  free(*ptrBase);
  *ptrBase = NULL; // Reassign head to null */
  return value;
 }
 /* case3: when two or more nodes are present */
 temp = *ptrBase;
 while(temp->up->up!=NULL)
 temp = temp->up;
 value = temp->up->value;
 free(temp->up);
 temp->up = NULL;
 return value;
}
float evalPostfix(char *postfix)
{
 Stack *base=NULL;
 //float value=0;
 float   a,b;
 float c;
 printf("\nThe infix notation is %s",postfix);
 printf("\nIts postfix notation: ");
 while(*postfix)
 {
  if(*postfix == '+' || *postfix == '-' || *postfix == '*' ||      
*postfix   == '/')
  {
   b = pop(&base);
   a = pop(&base);
   switch(*postfix)
   {
    case '+':
	       c = a + b;
	       break;
    case '-':
	       c = a - b;
	       break;
    case '*':
	       c = a * b;
	       break;
    case '/':
	       c = a / b;
	       break;
   }
   push(&base,c);
  }
  else if(*postfix > '0' && *postfix < '9')
  {
   push(&base,*postfix - '0');
  }
  else
  {
   printf("Could not be determined due to the illegal symbol '%
c'",*postfix);
   getch();
   exit(-1);
   break;
  }
  postfix++;
 }
 return pop(&base);
}
int getPriority(char ch,int tableType) // tableType 0 for Input, 1 for 
stack
{
 //printf("pri %c ",ch);
 switch(ch)
 {
  case '#':
	   return 0;
  case '+':
  case '-':
	   return 3;
  case '*':
  case '/':
	   return 4;
  case '^':
	   return 5;
  case '(':
	   return tableType==0?9:2;
  case ')':
	   return tableType==0?2:9;
  default:
	  if(isalnum(ch))
	  return 9;
	  printf("\nIlligal symbol %c. Haulting Execution.",ch);
	  getch();
	  exit(-1);
	  return -1; // used just to avoid an warning message
 }
}
/*char *infixToPostfix(char *infix)
{
 char postfix[80];
 int  token;
 int  i;
 Stack *myStack=NULL,*resultStack=NULL;
 push(&myStack,'#');
 while(*infix)
 {
  printf("%c ",*infix);
  getch();
  if(getPriority(*infix,0) > getPriority(topValue(&myStack),1))
  {
   push(&myStack,*infix);
  }
  else
  {
   // keep popping tokens from the stack & put it into the result stack
   // untill either of '(' or ')' is encountered.
   while(myStack!=NULL)
   {
    if(getPriority(topValue(&myStack),1) >= getPriority(*infix,0))
    {
     token = pop(&myStack);
     if(token != '(' && token !=')')
     push(&resultStack,token);
     else
     break;
    }
   }
   push(&myStack,*infix);
  }
  infix++;
 }
 while(myStack)
 {
  token = pop(&myStack);
  if(token!= '#')
  push(&resultStack,token);
  else
  break;
 }
 i = 0;
 while(resultStack)
 postfix[i]=pop(&resultStack);
 postfix[i]='\0';
 return postfix;
} */
 /*
 Algoritmm:
 1. -Create a stack
     1. Put the special token '#' on the
	stack. This will serve to mark
	the empty stack.
 2. -While not at the end of the expression
     1. read the next token from the expression
     2. if this token has a GREATER PRIORITY
	(according to the input priority table)
	than the last token on the stack
	(according to the stack priority table)
	push its value on this stack
	else
     3. if this token has a SMALLER OR EQUAL PRIORITY
	(according to the input priority table)
	than the last token on the stack
	(according to the stack priority table)
	1. remove all stack tokens
	   with a priority higher or equal
	   than that token, and put
	   this removed tokens (except
	   open or closed brackets) at
	   the end of the result.
	2. after that push that token on the
	   stack
 3. -Endwhile: Go back to step 3.
 4. -If the expression becomes empty, and you
     are finished, remove and output all
     the remaining tokens (except the special
     '#' token) from the stack.
     Put these tokens at the end of the result
 */
 // Algorithm location: 
http://www.faqts.com/knowledge_base/view.phtml/aid/26071
// HERE IS THE ACTUAL CODE:
char *infixToPostfix(char *infix)
{
 char postfix[80]; // to be returned
 int  i=0; // postfix incremental character writer counter
 Stack *stack=NULL;
 int stackToken,stackTokenPriority,inputTokenPriority;
 push(&stack,'#');
 while(*infix != '\0')
 {
  // *infix is the next token
  inputTokenPriority = getPriority(*infix,INPUT);
  do{
   stackToken = topValue(&stack);
   stackTokenPriority = getPriority(stackToken,STACK);
   if(inputTokenPriority > stackTokenPriority)
   {
    push(&stack,*infix);
    break;
   }
   else
   {
    pop(&stack);
    if(stackToken != '(' && stackToken != ')')
    postfix[i++]=stackToken;
   }
  }while(1);
  infix++;
 }
 while(stack!=NULL)
 {
  stackToken = pop(&stack);
  if(stackToken != '#')
  postfix[i++] = stackToken;
 }
 postfix[i] = '\0';
 return postfix;
}
void main()
{
 clrscr();
 printf("\ninfixToPostfix: %s",infixToPostfix("(3+4)*5+6-7"));
 puts("\nPress a key to end:");
 getch();
}