# infix to postfix

Printable View

• 11-17-2005
caramel
infix to postfix
[edited]
• 11-17-2005
sunnypalsingh
• 11-17-2005
caramel
well thank u.. i'm a beginner, so i'll try to understand the code then use it as a template for my program... if i have any questions, i'll post them here.

thanks once more :)
• 11-18-2005
treenef
I believe these two sources explain the concept of postfix
or Reverse Polish Notation adequately...

http://www.spsu.edu/cs/faculty/bbrow...tures/postfix/
http://www.qiksearch.com/articles/cs...ix-evaluation/
• 11-18-2005
caramel
Quote:

Originally Posted by treenef
I believe these two sources explain the concept of postfix
or Reverse Polish Notation adequately...

http://www.spsu.edu/cs/faculty/bbrow...tures/postfix/
http://www.qiksearch.com/articles/cs...ix-evaluation/

thanks so much, those were helpful
• 11-18-2005
caramel
here's my latest coding for the program:

Code:

``` #include <stdio.h> #include <conio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> /* constants */ #define TRUE 1 #define FALSE 0 /* Allocate space for stack, then define stack functions. */ typedef struct {  char OpStack[40];  int top; } STACK; /* function prototypes */ void initStack(STACK *stack); void get_infix(char infix[]); void convertToPostfix(char infix[], char postfix[]); int isOperator(char c); int precedence(char operator1, char operator2); int pred_level(char ch); void push(STACK *stack, char value); char pop(STACK *stack); char stackTop(STACK *stack); int isEmpty(STACK *stack); int isFull(STACK *stack); void printResult(char infix[], char postfix[]); void print_msg(void); struct table {   char s[2];   int isp;   int icp; }pr[7]; int isp(char c) { int i;  for(i=0;i<=9;i++)  if(pr[i].s[0]==c)   return(pr[i].isp);   return 0; } int icp(char c) { int i;  for(i=0;i<=9;i++)  if(pr[i].s[0]==c)   return(pr[i].icp);   return 0; } int main() {     char infix[40], postfix[40]="";     /* convert from infix to postfix main function */     convertToPostfix(infix, postfix);     /* display the postfix equivalent */     infix[strlen(infix)-2] = '\0';     printResult(infix, postfix);     return EXIT_SUCCESS; } /* initalise the stack */ void initStack(STACK *stack) {     stack->top = -1;  /* stack is initially empty */ } /* get infix expression from user */ void get_infix(char infix[]) {     int i;     printf("Enter infix expression: ");     fflush(stdin);         for ( i=0; i<40; )     {           if ( (infix[i] = getchar()) == '\n' )           {               i++;               break;           }           else if ( !(isspace(infix[i])) )               i++;     }     infix[i] = '\0'; } /* convert the infix expression to postfix notation */ void convertToPostfix(char infix[], char postfix[]) {     int i, length;     int j=0;     char top_ch;     STACK stack;     initStack(&stack); /* initialise stack */     get_infix(infix);  /* get infix expression from user */     length = strlen(infix);     if ( length )     {              push(&stack, '(');           strcat(infix, ")");           length++;                     for ( i=0; i<length; i++ )           {               /* if current operator in infix is digit */               if ( isdigit(infix[i]) )               {                     postfix[j++] = infix[i];               }               /* if current operator in infix is left parenthesis */               else if ( infix[i] == '(' )               {                     push(&stack, '(');                   if ( infix[i] == '(' )               {                     while ( TRUE )                     {                         /* get top */                         top_ch = stackTop(&stack);                         /* no stack left */                         if ( top_ch == '\0' )                         {                               printf("\n %s ERROR: Unbalanced parentheses\n", postfix);                               print_msg();                               exit(1);                         }                         else                         {                               if ( top_ch != ')' )                               {                                   postfix[j++] = top_ch;                                   pop(&stack);                               }                               else                               {                                   pop(&stack);                                   break;                               }                               }                         }                         }               }               /* if current operator in infix is operator */               else if ( isOperator(infix[i]) )               {                     while ( TRUE )                     {                         /* get top */                         top_ch = stackTop(&stack);                         /* no stack left */                         if ( top_ch == '\0' )                         {                               printf("\nERROR: Full Stack!\n");                               print_msg();                               exit(1);                         }                         else                         {                               if ( isOperator(top_ch) )                               {                                   if ( pred_level(top_ch) >= pred_level(infix[i]) )                                         postfix[j++] = pop(&stack);                                   else                                         break;                               }                               else                                   break;                         }                     }                     push(&stack, infix[i]);               }               /* if current operator in infix is right parenthesis */               else if ( infix[i] == ')' )               {                     while ( TRUE )                     {                         /* get top */                         top_ch = stackTop(&stack);                         /* no stack left */                         if ( top_ch == '\0' )                         {                               printf("\n %s ERROR: Unbalanced parentheses\n", postfix);                               print_msg();                               exit(1);                         }                         else                         {                               if ( top_ch != '(' )                               {                                   postfix[j++] = top_ch;                                   pop(&stack);                               }                               else                               {                                   pop(&stack);                                   break;                               }                         }                     }                     continue;               }           }     }     postfix[j] = '\0'; } int isOperator(char c) { /* determine if c is an operator */ switch (c) {         case '+':                 return TRUE;                 break;         case '-':                 return TRUE;                 break;         case '*':                 return TRUE;                 break;         case '/':                 return TRUE;                 break;         default:                 return FALSE;                 break; } } /* determine precedence level */ int pred_level(char ch) {     if ( ch == '+' || ch == '-' )           return 1;     else           return 2; } /* determine if the precedence of operator1 is less than,   equal to, greater than the precedence of operator2 */ int precedence(char operator1, char operator2) {     if ( pred_level(operator1) > pred_level(operator2) )           return 1;     else if ( pred_level(operator1) < pred_level(operator2) )           return -1;     else           return 0; } /* push a value on the stack */ void push(STACK *stack, char value) {     if ( !(isFull(stack)) )     {           (stack->top)++;           stack->OpStack[stack->top] = value;     } } /* pop a value off the stack */ char pop(STACK *stack) {     char ch;     if ( !(isEmpty(stack)) )     {           ch = stack->OpStack[stack->top];           (stack->top)--;           return ch;     }     else           return '\0'; } /* return the top value of the stack without popping the stack */ char stackTop(STACK *stack) {     if ( !(isEmpty(stack)) )           return stack->OpStack[stack->top];     else           return '\0'; } /* determine if stack is empty */ int isEmpty(STACK *stack) {     /* empty */     if ( stack->top == -1 )           return TRUE;     /* not empty */     else           return FALSE; } /* determine if stack is full */ int isFull(STACK *stack) {     /* full */     if ( stack->top == 19 )           return TRUE;     /* not full */     else           return FALSE; } /* display the result postfix expression */ void printResult(char infix[], char postfix[]) {     /*system("cls");*/     printf("\n\n");     printf("Infix notation: %s \n", infix);     printf("Postfix notation: %s \n\n", postfix);     print_msg(); } /* print exit message */ void print_msg(void) {     printf("Hit <RETURN> to exit...");     fflush(stdin);     getchar(); }```

it works as intended with numbers and operators, but drops out variables.. they're not displayed in the postfix output... can someone suggest a fragment of code i can include in my program to make it display the variables as well?
• 11-18-2005
Bajanine
If I get a spare moment this weekend I'll take a look.
Oh and check this out, Link :)
• 11-19-2005
treenef
I was thinking on the lines of creating one more function to check if it was an operand.

Such as:-

Code:

```bool IsOperand(char ch)   {   if (((ch >= 'a') && (ch <= 'z')) ||       ((ch >= 'A') && (ch <= 'Z')) ||       ((ch >= '0') && (ch <= '9')))       return true;   else       return false;   }```
And my corresponding Convert function:-

Code:

```void Convert(const string & Infix, string & Postfix) {   stack<char> OperatorStack;   char TopSymbol, Symbol;   int k;   for (k = 0; k < Infix.size(); k++)       {       Symbol = Infix[k];       if (IsOperand(Symbol))         Postfix = Postfix + Symbol;       else         {         while ((! OperatorStack.empty()) &&             (TakesPrecedence(OperatorStack.top(), Symbol)))             {             TopSymbol = OperatorStack.top();             OperatorStack.pop();             Postfix = Postfix + TopSymbol;             }         if ((! OperatorStack.empty()) && (Symbol == ')'))             OperatorStack.pop();  // discard matching (         else             OperatorStack.push(Symbol);         }       }   while (! OperatorStack.empty())       {       TopSymbol = OperatorStack.top();       OperatorStack.pop();       Postfix = Postfix + TopSymbol;       } }```
I implemented this using c++ and the STL but you should be able to apply this to C.
• 11-19-2005
caramel
Bajanine and treenef, thanks a lot for the input! It was all very helpful :)