postfix

let me post my code first

Code:

---

#include <stdio.h>
#include <stdlib.h>

struct stackNode{
      char data;
      struct stackNode *nextPtr;
      };
typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;

#define SIZE 20;

void convertTpPostfix( char infix[], char postfix[] );
int isOperator( char c );    /* Checks to c if its an oprator */
int precedence ( char operator1, char operator2 ); /*Acoording to the prcedence -1, 0, 1 */
void push ( StackNodePtr *topPtr, char value );
char pop ( StackNodePtr *topPtr );
char stackTop ( StackNodePtr topPtr );
int isEmpty( StackNodePtr topPtr );
void printStack( StackNodePtr topPtr );

int main(void)
{
 StackNodePtr startPtr = NULL;
 char infix[SIZE], postfix[SIZE];

 printf( "Enter a posfix expresion: " );
 fgets( infix, SIZE-1, stdin );



      system("PAUSE");
      return 0;
}
void covertToPostfix( char infix[], char postfix[] )
{

}

int isOperator( char c )
{
 if ( c == '+' || c == '-' || c == '*' ||c == '/' ||c == '^' ||c == '%' )
    return 1;
 else
    return 0;
}

int precedence ( char operator1, char operator2 )
{
 if ( operator1 == operator2 )
    return 0;
 else if ( operator1 < operator2 )
      return -1;
 else
    return 1;
}

void push ( StackNodeptr *topPtr, char value )
{
 StackNodePtr newptr;

 newPtr = malloc( sizeof( stackNode) );

 if ( newPtr ){
    newPtr -> data = value;
    newPtr -> nextptr = *topPtr;

    *topPtr = newPtr;
 }
 else
    fprintf(stderr, "Out of memory to store %c", value );
}
char pop ( StackNodePtr *topPtr )
{
 StackNodePtr = tempPtr;
 char storeValue;

 tempPtr = *topPtr;

 storevalue = (*topPtr) -> data;
 *topPtr = (*topPtr) -> nextPtr;
 free( tempPtr );
 return storeValue;
}

char stacktop( StackNodePtr topPtr )
{
 return (topPtr -> data);
}

int isEmpty( StackNodePtr topPtr )
{
 return topPtr == NULL;
}

void printStack( StackNodePtr topPtr )
{
 if ( topPtr == NULL )
    fprintf(stderr,"No memory available\n" );
 else{
      while ( topPtr != NULL ){
            printf("%c --> ", topPtr -> data );
            topPtr = topPtr -> nextPtr;
    }
    printf("NULL\n");
}

---

Okay my book sayd i should creat a programm that takes in ainfix and changes it to a postfix ...thats what i have done so far i am just stuck on this part ......

This the algorithm givin in the book ...

1)Push a left parenthesis '(' onto the stack ..
2) Append a right parenthesis ')' to the end of infix..
3) while stack is not empty , read infix from left ot right and do the following
if the current charater in infix is a digit, copy it to next element of postfix..
if the curretn character in infix is a left parenthesis , push it onto a stack.
if the current character in infix is an operator
pop operator (if these are any) at the top of the stack while they have equal or higher precedence than the current operator, and insert the popped operators in postfix.
push the current character in infix onto stack
if the current character in infix is a right parenthesis.
pop operators from the top of the stack and inser them in postfix until left parenthesis is at the top of the stack..
pop (and discard) the left parenthesis from the stack...

Okay i just want to know if what i have done till know is okay the first and secound ..about the parenthesis confuses me ...Extra help i wont mind ...

Cheers

well, i didn't know what point from the code that willn't execute the prog. anyway, here's my comment.

>> use if-else statement to run data validation. check whether the position is digit or operator. if the question isn't correct, discarded data validation check and return as error. for bracket, should include another variable such as "bracket" in integer format. if the expression of the open bracket and the close bracket is in balance. return the input as correct, else return as error input.

>> after checking, if the pointer point at digit, push this digit to the DIGIT stack. else (if it's an Operator or open bracket), push at OP stack. if the pointer point at close bracket, shouldn't push into the OP stack, coz you want to pop up the OP stack again, discard the close bracket, poping the related operation and push into the DIGIT stack. .......

>> at the end of the pop & push process. the answer should be found into DIGIT stack. try to pop any value from DIGIT stack, and create a POSTFIX stack and push the current poped value into POSTFIX. why ? see this eg:
[code]
3+6-5

|- | = head
|5 |
|+ |
|6 |
|3 |
----
if you print the value from head til down of the level. so it's incorrect. coz it's not postfix expression. if you want to print from down of the level til the head. it's impossible for one way linked list stack (if you are using two way linked list stack [*left] & [*right]-- it can be work). so you pop up any of the value , and then pushing all to the postfix stack. just like this :

|3 | = head
|6 |
|+ |
|5 |
|- |
----

so it's easy for you to print from head til down of the level.

so end of tips, hope this could help you find out the clue.

thanks alot for the explanation...well the part about the paretheses thats 1) and 2) in my question how would i do that ..

Thanks alot

Code:

---

int precedence ( char operator1, char operator2 )
{
 if ( operator1 == operator2 )
    return 0;
 else if ( operator1 < operator2 )
      return -1;
 else
    return 1;
}

---

If the operators you are passing to precedence() are '+', '-', '*', and '/', for example, then I think this function needs to be modified. The only part which will work is the first if. For the rest the return value depends on which operator comes first alphabetically.

Hey, my teacher mentioned this in one of my classes today, but anyway one way to do this is to put the expression in a binary tree and then read it in Postfix form in a recursive function
post(Tree){
output root
post(leftTree);
post(rightTree);
}

well not exactly but you get the point

thanks alot ..yeah i had a feeling that there way some thing wrong with precedence function ... beege> well i first have to understand how stack works ....so thats why i am not implementing binary tree

hey there,

if using tree linked list to convert the expression is quite easily than using the stack.

you should consider the stack is LIFO and the queue is FIFO.

you see, even i have alot of problem to face it during apply the code. try this example if you want to test your prog :

2+3*+3-(3+6^7*3+(4+7*5/7)-5+4(4*7+2)-2)+3*7-3^2-3+2

if this can work on your program, yours is successful done your program. sigh ... i still thinking of the solution how to pop/push to convert to postfix expression. conclusion is stack concept is hard to convert it, but tree will make it easier.

hey i got an ideal,
try use this variable

status_op_before and
status_op_after

To understand prefix notation- write the binary tree out. I could never figure out the difference between pre, in, and post order traversals until I learned to draw the tree out on paper and trace through it by hand.

well, it's easy.

infix : 2+3*(5-2)
prefix : *+23-52
postfix : 23+52-*

>> prefix's operation should be allocated at the left side of the expression. and then, postfix should be allocation at the right hand side.

as i mentioned just now, if using tree concept, it's esay to write the program, rather than using "stack" concept. but my assignment need to use stack concept to convert to infix to postfix expression.

Quote:

---

as i mentioned just now, if using tree concept, it's esay to write the program, rather than using "stack" concept. but my assignment need to use stack concept to convert to infix to postfix expression.

---

So do i friend so do i ;)

ermm, depend on the question, but i prefer tree concept to fix the problem. so how about your answer? so what's the requirement for the program? using stack, queue or tree. sigh, i still trying using stack concept to solve the "puzzle" :cool: