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; If you do change it to void, you'll have to change all those places where you really did return something ...

  1. #16
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you do change it to void, you'll have to change all those places where you really did return something useful.

    Just to keep from getting "bus error" I needed to malloc room for Returnoperation to do its thing inside performoperation.

    And even though you said you needed to clear out and move forward (or at least move forward!) after writing an answer back to evaluation, as you can see by the following trace (where I'm printing out equation and original_evaluation each time through):
    Code:
     ./postfix
    At top of loop: 1 2 + 4 5 + * and xxxxxxxxx
    At top of loop:  2 + 4 5 + * and 1 xxxxxxx
    At top of loop: 2 + 4 5 + * and 1 xxxxxxx
    At top of loop:  + 4 5 + * and 1 2 xxxxx
    At top of loop: + 4 5 + * and 1 2 xxxxx
    op2 is 2 and evaluation is now  2 xxxxx.
    op1 is 1 and evaluation is now 1 2 xxxxx.
    writeoperation is 3 .
    At top of loop:  4 5 + * and 3 2 xxxxx
    At top of loop: 4 5 + * and 3 2 xxxxx
    At top of loop:  5 + * and 4 2 xxxxx
    At top of loop: 5 + * and 4 2 xxxxx
    At top of loop:  + * and 4 5 xxxxx
    At top of loop: + * and 4 5 xxxxx
    op2 is 5 and evaluation is now  5 xxxxx.
    op1 is 4 and evaluation is now 4 5 xxxxx.
    writeoperation is 9 .
    At top of loop:  * and 9 5 xxxxx
    At top of loop: * and 9 5 xxxxx
    op2 is -112 and evaluation is now .
    op1 is -48 and evaluation is now .
    writeoperation is 5376 .
      5 xxxxx
    Edit: Oh, and once you get that fixed you will still have to deal with the whole backwards-off-the-list-thing. Right now, you have a filloperand call after that loop finishes -- but if you actually only backed into a space, well, that will multiply by 10 and subtract 16, which isn't what you want.
    Last edited by tabstop; 12-22-2008 at 01:23 AM.

  2. #17
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Quote Originally Posted by tabstop View Post
    If you do change it to void, you'll have to change all those places where you really did return something useful.
    There is nothing useful the function can return that can't be put in evaluation. The function can succeed or fail, ie. sucess is it returns an answer or a fail for an error (like the division by zero error). Both these can be put in evaluation as if a zero division error arrises it is not nesscary to show any more information than "ERROR: Division by zero".

    I have allocated space for Returnoperation.

    In an effort to remove both operands from evaluation after the operation has been performed I have modified the code to what is below. The first operation works correctly and the operands get removed from evaluation. op1 gets the right value, but op2 gets 44 instead of 4 as evaluation doesn't start with a space. Therefore evaluation becomes "3 49 " after the second operation (presuming that the original equation was "1 2 + 4 5 + *. I can't seem to figure out why this happens. Thanks for the trace btw. It helped. I still can't figure out why it is collecting garbage in the third operation let alone how to fix it.

    Code:
    int CheckIfDigit(char c) {
        return (isdigit(c) || c == '.');
    }
    
    //INP: equation OUT: evaluation
    void EvaluateEquation(char *equation, char *evaluation) {
        int op1, op2, nextToken = 0, n = 0;
        char *original_evaluation = evaluation;
        char *writeoperation;
        while (*equation != '\0') {
            if (isdigit(*equation)) {  
                while (CheckIfDigit(*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 (CheckIfDigit(*evaluation) && evaluation > original_evaluation) {
                    filloperands(&op1, *evaluation);
                    evaluation--;
                }
                if (*evaluation == ' ') evaluation++;
                if (CheckIfDigit(*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));
                evaluation += 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*/
                while (*evaluation != '\0') {
                      *evaluation++ = '\0';
                      n++;
                }
                evaluation -= n;
                /*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++;
    }
    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);

  3. #18
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The reason is that this notion you have of scanning backwards is such a bad idea I'm surprised we've made it last this long. But if we're going to stick with it (and why not, it's got us this far), then you CANNOT just blindly add another digit when moving backwards. You see that you've backed into a space, which is good; so you move forward and add the first digit back in again, which is not. If you've backed into a space, just STOP; don't do anything anymore, because you've already GOT your number.

  4. #19
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Quote Originally Posted by tabstop View Post
    The reason is that this notion you have of scanning backwards is such a bad idea I'm surprised we've made it last this long.
    Scanning backwards is still there as I didn't think it was a bad idea earlier. Having found that multiple operands have to be read backwards, I will try scanning forwards & using a seperate char * to hold the operands. Anyway, the function below now works for single digits w/ one operation, equations like 1 2 + 4 5 + *, but does not work for equations in the form 1 2 + 3 -. It also doesn't work for operands w/ > 1 digit:
    Code:
    //INP: equation OUT: evaluation
    void EvaluateEquation(char *equation, char *evaluation) {
        int op1, op2, nextToken = 0, n = 0;
        char *original_evaluation = evaluation;
        char *writeoperation;
        while (*equation != '\0') {
            if (isdigit(*equation)) {  
                while (CheckIfDigit(*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;
                if (!CheckIfDigit(*evaluation)) evaluation -= 2;
                /*while (CheckIfDigit(*(evaluation-1))) evaluation--; // Go to 
                if (CheckIfDigit(*(evaluation+1))) evaluation++; */
                /*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
                do {
                    filloperands(&op1, *evaluation);
                    evaluation--; //The first element is not always a ' '
                 } while (CheckIfDigit(*evaluation) && evaluation > original_evaluation);
                if (*evaluation == '\0' || *evaluation == ' ') evaluation++; 
    
                writeoperation = performoperation(op1, op2, *equation);
                if (writeoperation == NULL){ //Check for DB0
                    strcpy(evaluation, "ERROR: Division by Zero");
                    return;
                }
                strncpy(evaluation, writeoperation, strlen(writeoperation));
                evaluation += strlen(writeoperation);
    
                //if (*evaluation == ' ' ) evaluation++; //don't remove 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';
                      n++;
                }
                evaluation -= n;
                /*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++;
    }
    Even though this is working for more scenarios than anytime earlier, it still requires alot of a rewrite. The operands will need to be filled in the new char *, then the operation on them can be stored in evaluation. Also, if there are no more operands left, then it will need to look in evaluation. Any suggestions on how this could be fixed/improved??
    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);

  5. #20
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Well, it took me less than a day to modify the existing function, since (unusually) I knew pretty much what how what I wanted the function to do was going to be acheived (and sort of understand the function below. It is still abit buggy but works for more things than ever before! I was thinking of breaking it up into more functions, but the pointers (namely operands) doesn't get incremented properly when I try this.
    Works for: Single digit operands w/ one operator, 1 2 + 4 5 + *, 1 2 + 4 5 - *, 1 2 - 4 5 + *, 1 2 - 4 5 - *, Multiple digits w/ one operator.
    Doesn't work for: Multiple digits w/ > one operator, greater than one operator.
    Still looking for more cases that it doesn't work for (this function will need to work for ALL cases):

    Code:
    //INP: equation OUT: evaluation
    void EvaluateEquation(char *equation, char *evaluation) {
        int op1, op2, signbit, nextToken = 0, SetBack = 0;
        char *original_evaluation = evaluation;
        char *writeoperation, *operands;
        operands = (char *) malloc(51);
        memset(operands, '\0', 51);
        char *original_operands = operands;
        while (*equation != '\0') {
            if (isdigit(*equation)) {  
                while (CheckIfDigit(*equation)) {                     
                    *operands++ = *equation++; //Store number to operands
                    if (!nextToken) nextToken = 1; //Space Seperate each operand
                }
            }
            else if (*equation == ' ') equation++;
            else if (CheckIfOperator(*equation)) { 
                op1 = 0;
                op2 = 0;
                //Go back to start to read operands in correct order
                operands = original_operands; 
                /*Neither operand is an operator, this needs
                 to be set this back after oparands have been stored */
                if (!(CheckIfDigit(*operands)  || *operands == '-')) {
                    operands = original_evaluation;
                    SetBack = 1;
                } 
                //keep extracting until a ' ' is found & store the number
                signbit = 0; 
                do {
                    if (*operands == '-') {
                            signbit = 1;
                            operands++;
                    }   
                    filloperands(&op1, *operands);
                    operands++;
                } while (*operands != ' ' && *operands != '\0');
                if (signbit) op1 = -op1;
                operands++; //Skip the space
                
                /*Neither operand is an operator, this needs
                 to be set this back after oparands have been stored */
                if (!(CheckIfDigit(*operands)  || *operands == '-')) {
                    operands = evaluation;
                    SetBack = 1;
                } 
                
                //keep extracting until another ' ' is found & store number
                signbit = 0; 
                do {
                    if (*operands == '-') {
                            signbit = 1;
                            operands++;
                    }
                    filloperands(&op2, *operands);
                    operands++; //The first element is not always a ' '
                 } while (*operands != ' ' && *operands != '\0');
                 if (signbit) op2 = -op2;
                
                writeoperation = performoperation(op1, op2, *equation);
                
                //All remains of operands MUST be removed before continuing
                while (*operands != '\0') *operands-- = '\0';
                if (SetBack) evaluation = original_evaluation;
                
                if (writeoperation == NULL){ //Check for DB0
                    strcpy(evaluation, "ERROR: Division by Zero");
                    return;
                }
                strncpy(evaluation, writeoperation, strlen(writeoperation));
                evaluation += strlen(writeoperation);
                //MessageBox(NULL, original_evaluation, "original_evaluation", MB_OK);
                
                operands = original_operands;
                equation++;
            }                  
            //if nextToken add space to evaluation
            if (nextToken) { //Space-seperate each token, this helps w/ multiple
                *operands++ = ' '; //digits
                nextToken = 0;
            }
        }
        equation++;
    }
    void filloperands(int *op, char evaluation) {
           
        *op = *op * 10 + (evaluation - '0');
        return;
    }
    Also, thanks tabstop for helping so much (don't know if I would have gotten her on my own). Hope the function is not too long.
    Last edited by P4R4N01D; 12-24-2008 at 09:46 PM. Reason: fixed up signbit & works for more cases
    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);

  6. #21
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If *operands==1 ye canna call filloperands wi' it, forbye ye'll add a weird bit to yer number. (I could possibly have been reading too much BritLit recently.)

    Also, you can't get a negative number, since you persistenly un-set the signbit every time through your do-while loop.

    I haven't seen any (additional) problems with two-digit numbers.

  7. #22
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    I fixed signbit, I did notice that a -ve number was impossible to attain but it didn't strike me how to fix it. Fixed now...
    If *operands==1 ye canna call filloperands wi' it, forbye ye'll add a weird bit to yer number. I am confused about what you mean by this. Firstly *operands would equal '1' not 1 as operands is a char *. Secondly:
    Code:
    *op = *op * 10 + (evaluation - '0');
    say op = 0, 0 = 0 * 10 + ('1' - '0')
    op = 0 + (49 - 48) //chars are converted to their decimal ASCII equivilant automatically
    op = 1 //works!
    Going through, filloperands() should work as expected.
    P.S. I had to look up forbye.
    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);

  8. #23
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Aah! I meant if *operands==-, not 1 (and of course that's '-' as noted), since you're adding -16 or whatever it is.

  9. #24
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    I fixed what I think you are refering to above. It now handles negative numbers better.

    EDIT: The reason the function above "Doesn't work for: Multiple digits w/ > one operator, greater than one operator", is a problem w/ an earlier function so the wrong equation was being passed. I have not fixed this up yet so I am unsure if the solution above works for ALL equations (note: functions haven't been implemented yet...)
    Last edited by P4R4N01D; 12-25-2008 at 07:51 PM.
    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 2 of 2 FirstFirst 12
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. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 08:46 AM
  5. postfix
    By datainjector in forum C Programming
    Replies: 11
    Last Post: 11-20-2002, 07: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