infix to postfix

This is a discussion on infix to postfix within the C Programming forums, part of the General Programming Boards category; [edited]...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    6

    infix to postfix

    [edited]
    Last edited by caramel; 11-18-2005 at 10:50 AM.

  2. #2

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    6
    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

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    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/

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    6
    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

  6. #6
    Registered User
    Join Date
    Nov 2005
    Posts
    6
    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?

  7. #7
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396
    If I get a spare moment this weekend I'll take a look.
    Oh and check this out, Link
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



  8. #8
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    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.

  9. #9
    Registered User
    Join Date
    Nov 2005
    Posts
    6
    Bajanine and treenef, thanks a lot for the input! It was all very helpful

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM
  2. Infix, Postfix, Pseudo-Calculator using Stack ADT
    By sangken in forum C Programming
    Replies: 9
    Last Post: 09-08-2006, 08:17 AM
  3. Replies: 4
    Last Post: 03-12-2006, 01:17 PM
  4. Converting from infix to postfix
    By jcramer in forum C Programming
    Replies: 4
    Last Post: 03-27-2004, 08:23 PM
  5. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 08:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21