Thread: infix to postfix

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

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/

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

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?

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.

Bajanine and treenef, thanks a lot for the input! It was all very helpful