postfix

This is a discussion on postfix within the C Programming forums, part of the General Programming Boards category; let me post my code first Code: #include <stdio.h> #include <stdlib.h> struct stackNode{ char data; struct stackNode *nextPtr; }; typedef ...

  1. #1
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356

    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
    "I wish i could wish my wishs away"

    "By indirections find directions out" -- William Shakespears

    "Do what thou wilt shall be the whole of the law" -- Crowley "THE BEAST 666"

    Mizra -> love = Death...
    RDB(Rocks yooo)..

    http://www.cbeginnersunited.com

    Are you ready for the Trix ???

  2. #2
    ~- Y u n a -~ beely's Avatar
    Join Date
    Dec 2001
    Posts
    291
    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.

  3. #3
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356
    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
    "I wish i could wish my wishs away"

    "By indirections find directions out" -- William Shakespears

    "Do what thou wilt shall be the whole of the law" -- Crowley "THE BEAST 666"

    Mizra -> love = Death...
    RDB(Rocks yooo)..

    http://www.cbeginnersunited.com

    Are you ready for the Trix ???

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    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.

  5. #5
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    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

  6. #6
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356
    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
    "I wish i could wish my wishs away"

    "By indirections find directions out" -- William Shakespears

    "Do what thou wilt shall be the whole of the law" -- Crowley "THE BEAST 666"

    Mizra -> love = Death...
    RDB(Rocks yooo)..

    http://www.cbeginnersunited.com

    Are you ready for the Trix ???

  7. #7
    ~- Y u n a -~ beely's Avatar
    Join Date
    Dec 2001
    Posts
    291

    re

    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.

  8. #8
    ~- Y u n a -~ beely's Avatar
    Join Date
    Dec 2001
    Posts
    291
    hey i got an ideal,
    try use this variable

    status_op_before and
    status_op_after

  9. #9
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    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.
    Mr. C: Author and Instructor

  10. #10
    ~- Y u n a -~ beely's Avatar
    Join Date
    Dec 2001
    Posts
    291
    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.

  11. #11
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356
    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
    "I wish i could wish my wishs away"

    "By indirections find directions out" -- William Shakespears

    "Do what thou wilt shall be the whole of the law" -- Crowley "THE BEAST 666"

    Mizra -> love = Death...
    RDB(Rocks yooo)..

    http://www.cbeginnersunited.com

    Are you ready for the Trix ???

  12. #12
    ~- Y u n a -~ beely's Avatar
    Join Date
    Dec 2001
    Posts
    291
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM
  2. Replies: 4
    Last Post: 03-12-2006, 01:17 PM
  3. Just a postfix clarification.
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 12-08-2005, 08:47 AM
  4. calculating postfix problem
    By Axolotl in forum C Programming
    Replies: 2
    Last Post: 04-01-2004, 07:49 PM
  5. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 08:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21