Solved

infix to postfix

Posted on 2002-03-27
21
1,835 Views
Last Modified: 2007-12-19
can anyone give me or tell me where i can get a function which transforms an infix input such as (5*4)+(3/2)%4 to postfix (5 4 3 2 4 * + / %)? i tried searching in programmer's heaver but the function i found there seems not to be working well...

thanks!
0
Comment
Question by:mixelogj
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 3
  • 3
  • +5
21 Comments
 
LVL 1

Author Comment

by:mixelogj
ID: 6900238
and also if possible a function which calculates the value of a postfix string, for example it would return 6 on 2 2 1 + *

thank you
0
 
LVL 1

Author Comment

by:mixelogj
ID: 6900282
i have a prog which transforms to a something like postfix form:

Enter infix: ((3*4)+2)*4*((4+2)*3)
Postfix:  3 4 * 2 + 4 * 4 2 + 3 * *

also a prog which makes a form like this postfix to the original postfix would do :-)

mixelogj
0
 
LVL 6

Expert Comment

by:zebada
ID: 6900628
This is delphi source, not C, but is fairly easy to convert
http://www.blacky.co.nz/free/expr.zip

Or if you prefer, the same writen in java
http://www.blacky.co.nz/free/expression.zip

Regards
Paul
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 1

Author Comment

by:mixelogj
ID: 6900753
i'm afraid i'm not a C or C++ expert... just a beginner trying to learn so since i have no expirience, i can't do conversions...
thank you anyway
  Mixelogj
0
 
LVL 1

Expert Comment

by:Robalitoru
ID: 6902028
   I would gladly help providing you with the algorithm to write your own piece of code. After all, it's not the code that is hard to write in this case, but doing the math.
   But, as I remember it (it's been a while), the whole idea behind a postfixed form is that evaluating the expresion is fairly easy, we only need to parse the string once, from begining to end, and using a stack for the intermediary results.
   That applies for this form of postfix, the form of postfix I know, and a very natural one.
>> Enter infix: ((3*4)+2)*4*((4+2)*3)
>> Postfix:  3 4 * 2 + 4 * 4 2 + 3 * *
   I can give a very easy algorithm to evaluate the postfix form.

   Now, your first form of postfix... I'm sorry, but it's rather strange. If you will explain the idea behind it, and the order of evaluation, and it makes sense, I'll help you with it.


   

0
 
LVL 6

Expert Comment

by:zebada
ID: 6902308
Here's the Delphi code I mentioned earlier, stripped down and converted to C to do simple expression parsing and evaluating

http://www.blacky.co.nz/free/expr.c

Regards
Paul
0
 
LVL 1

Author Comment

by:mixelogj
ID: 6902459
i know this postfix form i am looking for is strange but it's what i am told to do :-( i'm not sure how the way of thinking should be like or i would of already done it...
i'll test that code from delphi today and give back the results.
thank you again
0
 
LVL 1

Author Comment

by:mixelogj
ID: 6902763
in short here is an example:
3 7 5 2 * + +
means multipoly 5 with 2, then add the result to 7, then add the result to 3.
the prog reads the numbers from right to left and the symbols from left to right.
0
 
LVL 16

Expert Comment

by:imladris
ID: 6902846
Note that by that definition "reads the numbers from right to left and the symbols from left to right" the expression in your original question:

(5 4 3 2 4 * + / %)

would start by multiplying 4 and 2, which is not what the infix expression indicated. This definition (reads the numbers from right to left and the symbols from left to right) is the expected one. The "postfix" expression in the original question appears to be something else. Which is right? I.e. which is the one you are after?
0
 
LVL 1

Expert Comment

by:Robalitoru
ID: 6903190
  Hi, all!

>> in short here is an example:
>> 3 7 5 2 * + +
>> means multipoly 5 with 2, then add the result to 7,
>> then add the result to 3.
>> the prog reads the numbers from right to left and the >> symbols from left to right

yes, that was my first guess too, but, then, as imladris said, your first example is wrong.

  But I think that our guess is wrong, because, taking the first example, I can think of no "strange postfix form" that can evaluate it corect taking "the numbers from right to left and the symbols from left to right", because that means you will always have to use an intermediary result as one of the operands.
  But 5*4 and 3/2 both have to be evaluated before the other operations. Think about it!
  This is not the case with a "good postfix form".

  As I see it, this strange postfix form, puts all the numbers (operands) in the order that they appear in the infixed form, and then all the symbols (operators) in the same order. How can you figure out where the paranthesis were? Very silly, and I'm sure that's not it.

  I didn't check out the code zebada gave you, but how can it help you if you didn't figure out the math?

  Meanwhile... good luck!
0
 
LVL 1

Author Comment

by:mixelogj
ID: 6903672
you are right... the correct postfix prog is this:
Enter infix: (5*3+2)*3+(2*2+1)
Postfix:  5 3 * 2 + 3 * 2 2 * 1 + +
(i found it at programmer's heaven)

now i am just looking for a prog to calculate the result..
the code i was given at http://www.blacky.co.nz/free/expr.c
does indeed do what i want but i don't want all of it, i just want the function which calcs the result and i'm having a hard time taking just that from the whole code as it realies on structs etc...
0
 
LVL 16

Expert Comment

by:imladris
ID: 6903840
So you have the conversion from infix to postfix covered now? (That was the original request...)
0
 
LVL 33

Accepted Solution

by:
hongjun earned 130 total points
ID: 6904545
Try this done by me during my schooldays.


/*****************************/
/* Programmer : Loh Hon Chun */
/* Adm No     : 9852152      */
/* Class      : 3A07         */
/* Description: Practical 3  */
/*****************************/

/*************************************************************/
/*************************************************************/
/*                 ASSUMING INFIX EXPRESSION                 */
/*                             IS VALID                          */
/*                              !!!!!!!!                          */
/*************************************************************/
/*************************************************************/

/* include necessary preprocessor header files */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* constants */
#define TRUE 1
#define FALSE 0

/* structure for stack */
typedef struct
{
      char data[20];  /* array to hold stack contents */
      int tos;        /* top of the stack pointer */
} 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);

/* program entry point */
int main(void)
{
      char infix[20], postfix[20]="";

      /* 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->tos = -1;  /* stack is initially empty */
}

/* get infix expression from user */
void get_infix(char infix[])
{
      int i;

      printf("Enter infix expression below (max 18 characters excluding spaces) : \n");
      fflush(stdin);
      /* to read in only 18 characters excluding spaces */
      for ( i=0; i<18; )
      {
            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 tos_ch;
      STACK stack;

      initStack(&stack); /* initialise stack */
      get_infix(infix);  /* get infix expression from user */
      length = strlen(infix);

      /* if strlen if infix is more than zero */
      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 current operator in infix is operator */
                  else if ( isOperator(infix[i]) )
                  {
                        while ( TRUE )
                        {
                              /* get tos */
                              tos_ch = stackTop(&stack);

                              /* no stack left */
                              if ( tos_ch == '\0' )
                              {
                                    printf("\nInvalid infix expression\n");
                                    print_msg();
                                    exit(1);
                              }
                              else
                              {
                                    if ( isOperator(tos_ch) )
                                    {
                                          if ( pred_level(tos_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 tos */
                              tos_ch = stackTop(&stack);

                              /* no stack left */
                              if ( tos_ch == '\0' )
                              {
                                    printf("\nInvalid infix expression\n");
                                    print_msg();
                                    exit(1);
                              }
                              else
                              {
                                    if ( tos_ch != '(' )
                                    {
                                          postfix[j++] = tos_ch;
                                          pop(&stack);
                                    }
                                    else
                                    {
                                          pop(&stack);
                                          break;
                                    }
                              }
                        }
                        continue;
                  }
            }
      }

      postfix[j] = '\0';
}

/* determine if c is an operator */
int isOperator(char c)
{
      if ( c == '+' || c == '-' || c == '*' ||
             c == '/' || c == '%' || c == '^' )
      {
            return TRUE;
      }
      else
            return FALSE;
}

/* determine precedence level */
int pred_level(char ch)
{
      if ( ch == '+' || ch == '-' )
            return 1;
      else if ( ch == '^' )
            return 3;
      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->tos)++;
            stack->data[stack->tos] = value;
      }
}

/* pop a value off the stack */
char pop(STACK *stack)
{
      char ch;

      if ( !(isEmpty(stack)) )
      {
            ch = stack->data[stack->tos];
            (stack->tos)--;
            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->data[stack->tos];
      else
            return '\0';
}

/* determine if stack is empty */
int isEmpty(STACK *stack)
{
      /* empty */
      if ( stack->tos == -1 )
            return TRUE;
      /* not empty */
      else
            return FALSE;
}

/* determine if stack is full */
int isFull(STACK *stack)
{
      /* full */
      if ( stack->tos == 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();
}


hongjun
0
 
LVL 84

Expert Comment

by:ozo
ID: 6904589
#include <stdio.h>;
char *postfixexpr( char *s);
char *postfixterm(char *s){
        while(*s==' '){s++;}
        if( *s == '(' ){
                s = postfixexpr(++s);
                while( *s && *s != ')' ){ ++s; }
                if( *s == ')' ){
                        s++;
                }else{
                        fprintf(stderr,"Unmatched '('\n");
                }
        }else{
                while( '0' <= *s && *s <= '9' ){ printf("%c",*s++); }
                printf(" ");
        }
        return s;
}
char *postfixproduct(char *s){
        s = postfixterm(s);
        while(*s==' '){s++;}
        if( *s == '*' || *s == '/' || *s == '%' ){
                char op=*s++;
                s = postfixproduct(s);
                printf("%c ",op);
        }
        return s;
}
char *postfixexpr(char *s){
  s = postfixproduct(s);
  while(*s==' '){s++;}
  if( *s == '+' || *s == '-' ){
    char op=*s++;
    s = postfixexpr(s);
    printf("%c ",op);
    return s;
  }
}

main(){
    char *s = postfixexpr("(5*4)+(3/2)%4");
    printf("\n%s\n",s);
    printf("\n%s\n",postfixexpr("(5*3+2)*3+(2*2+1)xxxx");
}
0
 
LVL 1

Expert Comment

by:Robalitoru
ID: 6904674
  I'm so sorry, I went to sleep and others beat me to it.
   I don't have the code, and I'm pretty busy right now, so I'll give you the pseudo-code (assuming the expresion is correct).

**************************************
{ Input: postfixed:String; }
{ Interm:Stack; }

for i:=first(postfixed) to last(postfixed)
   if( postfixed(i) is operand ) Interm.Push(postfixed(i))
   else
     // operator
     operand1=Interm.Pop()
     operand2=Interm.Pop()
     result=Evaluate( operand1, postfixed(i), operand2 )
     Interm.Push(result)
   endif
endfor

finalResult=Interm.Pop()
{ Output:finalResult; }
**************************************

  Well, that's it.
  Good luck!
0
 
LVL 1

Author Comment

by:mixelogj
ID: 6904730
emm wow:-) lot's of codes out there.. anyway i reckon my mistake for asking for the conversion function and then running into it at programmer's heaven. anyway, as i can understand these codes u gave me all do the conversion except for the psedocode which i will try and let ya know soon today. see ya and thanks!
0
 
LVL 33

Expert Comment

by:hongjun
ID: 6904732
Try them and decide which to use :)

hongjun
0
 
LVL 1

Author Comment

by:mixelogj
ID: 6906710
okay. the original request was for infix to postfix conversion so it'd be unfair to ask for something else. as i said, lot's of codes out there and i wish i could give ya all points... thank you:-)
0
 

Expert Comment

by:premshree
ID: 7463691
I have written a JavaScript version of the same.
Check it out here : http://www.qiksearch.com/javascripts/infix-postfix_mul11.htm

A Perl version of the same can be found here : http://qiksearch1.tripod.com/cgi-bin/infix-postfix.pl
0
 

Expert Comment

by:Atouray
ID: 25896613
How can hongjun program be put on a GUI? any idea? also how can it evaluate expression like
infix Xpression ( 35 -  20 ) < 10 #, to give a result like this
Postfix = 35 20 - 10 <
Result = False
can someone modify hongjun's code to do the above so that i can see.
thanks

0
 
LVL 33

Expert Comment

by:hongjun
ID: 25896618
I suggest you post a new question and show what you already have.

hongjun
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

688 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question