Solved

# infix to postfix

Posted on 2002-03-27
1,824 Views
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
Question by:mixelogj
• 8
• 3
• 3
• +5

LVL 1

Author Comment

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

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

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

LVL 1

Author Comment

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

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

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

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

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

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

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

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

So you have the conversion from infix to postfix covered now? (That was the original request...)
0

LVL 33

Accepted Solution

hongjun earned 130 total points
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

#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

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

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

Try them and decide which to use :)

hongjun
0

LVL 1

Author Comment

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

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

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

I suggest you post a new question and show what you already have.

hongjun
0

## Featured Post

### Suggested Solutions

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to useâ€¦
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.