[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1853
  • Last Modified:

infix to postfix

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
mixelogj
Asked:
mixelogj
  • 8
  • 3
  • 3
  • +5
1 Solution
 
mixelogjAuthor Commented:
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
 
mixelogjAuthor Commented:
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
 
zebadaCommented:
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
The IT Degree for Career Advancement

Earn your B.S. in Network Operations and Security and become a network and IT security expert. This WGU degree program curriculum was designed with tech-savvy, self-motivated students in mind – allowing you to use your technical expertise, to address real-world business problems.

 
mixelogjAuthor Commented:
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
 
RobalitoruCommented:
   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
 
zebadaCommented:
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
 
mixelogjAuthor Commented:
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
 
mixelogjAuthor Commented:
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
 
imladrisCommented:
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
 
RobalitoruCommented:
  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
 
mixelogjAuthor Commented:
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
 
imladrisCommented:
So you have the conversion from infix to postfix covered now? (That was the original request...)
0
 
hongjunCommented:
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
 
ozoCommented:
#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
 
RobalitoruCommented:
  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
 
mixelogjAuthor Commented:
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
 
hongjunCommented:
Try them and decide which to use :)

hongjun
0
 
mixelogjAuthor Commented:
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
 
premshreeCommented:
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
 
AtourayCommented:
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
 
hongjunCommented:
I suggest you post a new question and show what you already have.

hongjun
0

Featured Post

Will You Be GDPR Compliant by 5/28/2018?

GDPR? That's a regulation for the European Union. But, if you collect data from customers or employees within the EU, then you need to know about GDPR and make sure your organization is compliant by May 2018. Check out our preparation checklist to make sure you're on track today!

  • 8
  • 3
  • 3
  • +5
Tackle projects and never again get stuck behind a technical roadblock.
Join Now