Problems in evaluating postfix

This is a discussion on Problems in evaluating postfix within the C Programming forums, part of the General Programming Boards category; I have got a fully working function that converts infix to postfix, but now I am having trouble w/ the ...

  1. #1
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223

    Problems in evaluating postfix

    I have got a fully working function that converts infix to postfix, but now I am having trouble w/ the second stage in evaluating the equation in postfix. I realise that there is an example given in K&R but I don't really understand it & have decided to make my own from scratch.
    I had this algorithm working yesterday, but I changed it as it was extracting from the wrong end and couldn't parse equations like: 1 2 - 4 5 + *. The problem I am having is:
    given the input 1 2 -, it returns 1 instead of -1;
    given the input 666 1 -, it returns 65 instead of 665;
    given the input 1+2, it returns nothing instead of 3 etc.
    I am sure the function performoperation is working correctly & i have also checked that evaluation is correct for the above inputs after the strncpy function is called. I have not changed anything in what calls this function (& also this function is called on a button-click even so I cannot post it here).
    No idea as to the cause of this problem (I was going really well until this prob arose) Please Help!

    Code:
    //INP: equation OUT: evaluation
    char *EvaluateEquation(char *equation, char *evaluation) {
        int op1, op2, signbit = 0;
        int nextToken = 0;
        char *writeoperation;
        while (*equation != '\0') {
            if (isdigit(*equation)) {  
                while (isdigit(*equation) || *equation == '.') {                     
                    *evaluation++ = *equation++; //Store number to evaluation
                    if (!nextToken) nextToken = 1; //Space Seperate each operand
                }
            }
            else if (CheckIfOperator(*equation)) { 
                op1 = 0;
                op2 = 0;
                evaluation -= 2;
                /*Read operands in reverse order starting from the end */     
                //keep extracting until a ' ' is found & store the number
                do {
                    if (*evaluation == '-') signbit = 1;         
                    else {
                        op2 = op2 * 10 + (*evaluation - '0');
                        if (signbit) {
                            op2 = -op2;
                            signbit = 0; 
                        }  
                    }
                    evaluation--;
                } while (*evaluation != ' ');
                evaluation--; //Skip the space
                //keep extracting until another ' ' is found & store number
                while (*evaluation != ' ' && *evaluation != '\0') {
                    if (*evaluation == '-') signbit = 1;         
                    else {
                        op1 = op1 * 10 + (*evaluation - '0');
                        if (signbit) {
                            op1 = -op1;
                            signbit = 0; 
                        }  
                    }
                    evaluation--;
                }
                writeoperation = performoperation(op1, op2, *equation);  //Works fine upto and including this line
                 
                if (writeoperation == NULL){ //Check for DB0
                    strcpy(evaluation, "ERROR: Division by Zero");
                    return evaluation;
                }
                strncpy(evaluation, writeoperation, sizeof(writeoperation));
                while (*evaluation != ' ') { // ' ' at the end of the operand
                    evaluation++;
                }
                evaluation++; //we shouldn't have removed the space
                /* the operation has been performed so set the reset address to
                  the next element, as the operation cannot be overwritten by
                  an operand. All remains of operands MUST be removed from
                  evaluation before continuing*/
                while (*evaluation != '\0') *evaluation++ = '\0';
                /*Note: if second operator not found, evaluation = evalcopy
                  then evaluation-- till *evaluation == ' ' */
                equation++;
            }                  
            else if (*equation == ' ') equation++;
            //if nextToken add space to evaluation
            if (nextToken) { //Space-seperate each token, this helps w/ multiple
                *evaluation++ = ' '; //digits
                nextToken = 0;
            }
        }
        equation++;
    }
    Last edited by P4R4N01D; 12-21-2008 at 11:23 PM. Reason: Added comment
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  2. #2
    Registered User
    Join Date
    Dec 2008
    Posts
    9
    I wrote one of these for uni a few years ago, wish I could find the code for you. I do remember that it was a lot shorter than your implementation though.

    The biggest thing that leaps out to me about this code is that it is all one function. Debatabley, anything over around 50 lines is too complex.

    You should write a function that parses the strings into arrays, or some other data structure. you will find it easier to work with.

    After that its simply a matter of having a temp variable for the "number_so_far" and a case statement which performs calculations depending on which operator it encounters.

  3. #3
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    This way i get to learn more about pointers . Also I have to output the string as a char *.
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So your "check backward until you see a space" can't possibly work, because there's no space in front of the first number.

  5. #5
    Registered User
    Join Date
    Dec 2008
    Posts
    9
    Learning pointers is one thing, learning to decompose a problem well is another. But all that aside, there are a lot of corner cases in postfix operations that you need to consider. And like tabstop noticed, if you want to read it backwards you will have to take into account the first character read. Hence this is why you should modularize your code, it will be prettier, and if you ever want a job in the software engineering field you will want good programming practices.

    Also, you should be able to convert from one data type to another. just write another function which parses it back :P

    This is how I learnt pointers - anyone reading this should give it a look :P

    http://www.youtube.com/watch?v=r4-9Mh3761E
    Last edited by zigga15; 12-21-2008 at 11:33 PM.

  6. #6
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Both op1 & op2 work & they are the only two times I check backward, it is like a digit is being cutoff from equation.
    Also I have tried to modularise the code by calling two other functions (it would be alot longer w/ performoperation()'s switch inside this function).

    EDIT Here is a better version, filloperands() works as expected so I am not going to include it
    Code:
    //INP: equation OUT: evaluation
    char *EvaluateEquation(char *equation, char *evaluation) {
        int op1, op2, signbit = 0;
        int nextToken = 0;
        char *writeoperation;
        while (*equation != '\0') {
            if (isdigit(*equation)) {  
                while (isdigit(*equation) || *equation == '.') {                     
                    *evaluation++ = *equation++; //Store number to evaluation
                    if (!nextToken) nextToken = 1; //Space Seperate each operand
                }
            }
            else if (CheckIfOperator(*equation)) { 
                op1 = 0;
                op2 = 0;
                evaluation -= 2;
                /*Read operands in reverse order starting from the end */     
                //keep extracting until a ' ' is found & store the number
                do {
                    filloperands(&op2, *evaluation);
                    evaluation--;
                } while (*evaluation != ' ');
                evaluation--; //Skip the space
                //keep extracting until another ' ' is found & store number
                while (*evaluation != ' ' && *evaluation != '\0') {
                    filloperands(&op1, *evaluation);
                    evaluation--;
                }
                writeoperation = performoperation(op1, op2, *equation);  //Works fine upto and including this line
                 
                if (writeoperation == NULL){ //Check for DB0
                    strcpy(evaluation, "ERROR: Division by Zero");
                    return evaluation;
                }
                strncpy(evaluation, writeoperation, sizeof(writeoperation));
                while (*evaluation != ' ') { // ' ' at the end of the operand
                    evaluation++;
                }
                evaluation++; //we shouldn't have removed the space
                /* the operation has been performed so set the reset address to
                  the next element, as the operation cannot be overwritten by
                  an operand. All remains of operands MUST be removed from
                  evaluation before continuing*/
                while (*evaluation != '\0') *evaluation++ = '\0';
                /*Note: if second operator not found, evaluation = evalcopy
                  then evaluation-- till *evaluation == ' ' */
                equation++;
            }                  
            else if (*equation == ' ') equation++;
            //if nextToken add space to evaluation
            if (nextToken) { //Space-seperate each token, this helps w/ multiple
                *evaluation++ = ' '; //digits
                nextToken = 0;
            }
        }
        equation++;
    }
    Last edited by P4R4N01D; 12-21-2008 at 11:59 PM. Reason: modularised further
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you want to affect the integer that op points to, you have to use *op.

  8. #8
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    fixed, posted modified code above. Still having the same problem as I described in the first post though.
    Found what could be the problem, something is stuffed w/ equation & it goes back & does the isdigit() part after it has done the operation w/ the input 1 2 -.
    Last edited by P4R4N01D; 12-22-2008 at 12:28 AM.
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  9. #9
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    This might fix the problem, performoperation() alters equation so the function is posted below:
    Code:
    char *performoperation(int op1, int op2, char chroperator) {
        char *Returnoperation;
        int operation;
        switch (chroperator) {
            case '+': { 
                operation = op1 + op2;
                break;
            }
            case '-': {
                 operation = op1 - op2;
                break;
            }    
            case '*': {
                 operation = op1 * op2;
                break;
            }    
            case '/': {
                if (!op2) return NULL;
                operation = op1 / op2;
                break;
            }
            case '%': {
                operation = op1 % op2;
                break;
            }
        }
        sprintf(Returnoperation, "%d ", operation);
        return Returnoperation;
    }
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Looking some more, this seems odd:
    Code:
     strncpy(evaluation, writeoperation, sizeof(writeoperation));
    presumably you mean strlen(writeoperation). And does writeoperation lose the first character of the answer? Who knows? And aren't you overwriting something important here, should someone be so foolish as to type in more than one operation? (It looks like you keep writing \0 until the end of the string.)

  11. #11
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    I intended it to be strncpy as, say 1 2 is in evaluation. These are the operands. after an oparation is finished, the operands are no longer needed so evaluation can become -1 (if the operator was '-'
    ). Thanks for pointing that out, I meant strlen. writeoperation does not loose part of its answer.
    WOW! that's better, 1 2 - now equals " 2", a slight improvement.
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Do me a favor, because I'm a naturally skeptic person. Add this line to the beginning of your function:
    Code:
    char *original_evaluation = evaluation;
    and change this:
    Code:
                //keep extracting until another ' ' is found & store number
                while (*evaluation != ' ' && *evaluation != '\0') {
    to this:
    Code:
                //keep extracting until another ' ' is found & store number
                while (*evaluation != ' ' && evaluation > original_evaluation) {
    'cause I still think you're walking off the end of that string there.

    If that doesn't help, post/attach the whole thing, so that I don't have to write a lot of code to go around all this.

  13. #13
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Thanks, that fixed it! After that loop, I needed to call filloperands again as op2 was not being read. Thanks for your help tabstop and zigga15. I liked that youtube clip btw, not quite what I meant but anyway. I was thinking more of the push & pop operations on char *s. It's using the stack & these structures that I intended to get more familiar w/. I understand the basics of *s, I just haven't used them for long enough.

    Still, back to the same problem I had yesterday, The output is incorrect for expressions like 1 2 - 4 5 + * and for 1 2 - 4 +. I will post the wole code below:
    Code:
    int CheckIfOperator(char c) {
        char *listofoperators = "+-*/%";
        int found = 0;
        while ((*listofoperators != '\0') && (!found)) {
              if (*listofoperators == c) found = 1;
              listofoperators++;
        }
        return found;
    }
    
    void filloperands(int *op, char evaluation) {
        int signbit = 0; 
        if (evaluation == '-') signbit = 1;         
        *op = *op * 10 + (evaluation - '0');
        if (signbit) {
            *op = -*op;
            signbit = 0; 
        }
        return;
    }
    
    //INP: equation OUT: evaluation
    void EvaluateEquation(char *equation, char *evaluation) {
        int op1, op2, nextToken = 0;
        char *evalcopy;
        char *original_evaluation = evaluation;
        evalcopy = evaluation; //Just for debug
        char *writeoperation;
        while (*equation != '\0') {
            if (isdigit(*equation)) {  
                while (isdigit(*equation) || *equation == '.') {                     
                    *evaluation++ = *equation++; //Store number to evaluation
                    if (!nextToken) nextToken = 1; //Space Seperate each operand
                }
            }
            else if (*equation == ' ') equation++;
            else if (CheckIfOperator(*equation)) { 
                op1 = 0;
                op2 = 0;
                evaluation -= 2;
                /*Read operands in reverse order starting from the end */     
                //keep extracting until a ' ' is found & store the number
                do {
                    filloperands(&op2, *evaluation);
                    evaluation--;
                } while (*evaluation != ' ' && evaluation > original_evaluation);
                evaluation--; //Skip the space
                
                //keep extracting until another ' ' is found & store number
                while (*evaluation != ' ' && evaluation > original_evaluation) {
                    filloperands(&op1, *evaluation);
                    evaluation--;
                }
                filloperands(&op1, *evaluation);
                writeoperation = performoperation(op1, op2, *equation);
                 
                if (writeoperation == NULL){ //Check for DB0
                    strcpy(evaluation, "ERROR: Division by Zero");
                    return;
                }
                strncpy(evaluation, writeoperation, strlen(writeoperation));
                /* the operation has been performed so set the reset address to
                  the next element, as the operation cannot be overwritten by
                  an operand. All remains of operands MUST be removed from
                  evaluation before continuing*/
                /*Note: if second operator not found, evaluation = evalcopy
                  then evaluation-- till *evaluation == ' ' */
                equation++;
            }                  
            //if nextToken add space to evaluation
            if (nextToken) { //Space-seperate each token, this helps w/ multiple
                *evaluation++ = ' '; //digits
                nextToken = 0;
            }
        }
        equation++;
    }
    
    char *performoperation(int op1, int op2, char chroperator) {
        char *Returnoperation;
        int operation;
        switch (chroperator) {
            case '+': { 
                operation = op1 + op2;
                break;
            }
            case '-': {
                 operation = op1 - op2;
                break;
            }    
            case '*': {
                 operation = op1 * op2;
                break;
            }    
            case '/': {
                if (!op2) return NULL;
                operation = op1 / op2;
                break;
            }
            case '%': {
                operation = op1 % op2;
                break;
            }
        }
        sprintf(Returnoperation, "%d ", operation);
        return Returnoperation;
    }
    Last edited by P4R4N01D; 12-22-2008 at 02:07 AM. Reason: EvaluateEquation return value confusion
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Your EvaluateEquation doesn't return anything. What is it supposed to return, and when?

  15. #15
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    woops, it alters evaluation, so effectively that is the return value. The function should be declared as void EvaluateEquation(char *equation, char *evaluation)
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

Page 1 of 2 12 LastLast
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, 07:44 AM
  2. Replies: 4
    Last Post: 03-12-2006, 02:17 PM
  3. Just a postfix clarification.
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 12-08-2005, 09:47 AM
  4. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 09:46 AM
  5. postfix
    By datainjector in forum C Programming
    Replies: 11
    Last Post: 11-20-2002, 08:33 PM

Tags for this Thread


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