Thread: Impix or reverse polish notation

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

    Impix or reverse polish notation

    I am currently working on a (Windows GUI) calculator that accepts impix notation and (hopefully) will contain most of the features of a standard scientific calculator (like sin, cos and tan) w/ the eventual aim being for it to do calculus. However the first objective is to perform standard operations.
    I was wondering if it would be easier to work completely in impix or convert impix into reverse polish. Richie & Kerrigan provide algorithms for working in reverse polish but don't mention the shunting yard algorithm or conversion between these two notations. If it is easier to work in impix then how would this be achieved, remember the program needs to work w/ brackets and numbers more than one digit. Otherwise, I need help w/ my 'Shunting yard algorithm' as follows, which gives afew warnings:
    Code:
    //Pass in inputqueue for reading, and outputqueue for writing
    char ConvertToPolishNotation(char inputqueue[], char outputqueue[]) {
        int length = sizeof(inputqueue);
        char operatorqueue[50];
        int i, counter = 0;
        for (i=0;i<length; i++) {  //Read token
            if ((inputqueue[i] >= '0') && (inputqueue[i] <= '9')) //NUMBER
                pushelement(inputqueue[i], outputqueue);    
            else if ((inputqueue[i] < 42) || (inputqueue[i] > 45)
             && (inputqueue[i] != 47) && (inputqueue[i] != 94))  //OPERATOR
                pushelement(inputqueue[i], operatorqueue); 
            else if (inputqueue[i] == 40) //BRACKET
                pushelement(inputqueue[i], operatorqueue); 
            else if (inputqueue[i] == 41) {//BRACKET    
                while ((strcmp(operatorqueue[counter],"(") != 0) && (counter < 50)) {
                    //Until the token at the top of the stack is a left parenthesis,
                    //pop operators off the stack onto the output queue  
                    outputqueue[i+1] = popelement(counter, operatorqueue);  
                    counter++; 
                } //ENDWHILE
                if (counter == 50) { //BRACKET MISMATCH
                    MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                    return 0;
                }
                //Pop the left parenthesis from the stack, but not onto the output queue.    
                popelement(counter, operatorqueue);
            } //END BRACKET 
        } //NO MORE TOKENS
        counter = 0;
        //While there are still operator tokens in the stack:
        while (strcmp(operatorqueue[counter], "") != 0) {
            if ((operatorqueue[counter] == ")") || (operatorqueue[counter] == "(")) {//BRACKET  
                MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                return 0;
            }
                    outputqueue[i] = popelement(counter, operatorqueue);
        }
        return &outputqueue;  
    }
    What I don't think I have accounted for:
    1. Operator preceedance
    2. Working w/ digits > 9
    3. Functions (like sin x etc.)

    Warnings: return makes integer from pointer without a cast, function returns address of local variable. Also, sorry for the long post & I wasn't sure whether I should put this in Windows Programming, but I figured this would be alright as it doesn't require any windows-only function calls.
    Last edited by P4R4N01D; 11-12-2008 at 11:46 PM. Reason: Fixed up ConvertToPolishNotation
    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
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You can't return the entire outputqueue[] array from ConvertToPolishNotation, which only returns a single char. You're also using inputqueue in that function, despite the fact that it has nothing in it. Maybe you intend to use text instead? Anyway, decide what it is you're trying to do there, and if the answer is "return all these queues", then pass them in to the function as parameters to be filled.

  3. #3
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Sorry, text[] was meant tobe inputqueue[], I'll fix that up, thanks for pointing that out.
    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,336
    As to the operator precedence, I don't recall that being a big problem (I think my source is at school, since I don't seem to have it here), since there are only really two categories */ and +-. Exponents would be a third, I guess, if you allowed them.

    As to numbers bigger than 0-9, the way that seems like the best idea to me right now (danger!) is to, when you read a digit, look forward until you see something that's not a digit and then parse the whole number. Alternatively, you can use strtol, which will both read a number and tell you where the number stops. (That might not fit in with your for-loop idea; I used a character pointer that I moved through the input.)

  5. #5
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    I fixed up the ConvertToPolishFunction again, I the hope that this is how passed parameters can be changed in a function. Is it called with ConvertToPolishNotation(&inputqueue, &outputqueue);?

    I thought of reading in a number that way (and then when printing it put a space to seperate and define where the number starts and stops, i.e. (123+1) would become 123 1+. I couldn't implement this because I coun't see how it wa feasible w/ my current solution. I would not of thought of using a character pointer to loop through, how would this be acheived, would all the character arrays have to be char *s?
    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. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Arrays are automatically passed by pointer, so you shouldn't need &. Don't redeclare outputqueue! It had better already be large enough.

    When I output RPN, I always use spaces between everything, because sure 479+* looks cool and all, but still. Granted I was building a tree out of it, so it was easy to do. If all you're doing is printing, just put a space before every operator and it should happen automagically.

    As to the character pointer, it's something like
    Code:
    char *currentpointer = inputarray[0];
    while (*currentpointer != '\n') { /*or whatever your end of input is*/
        if (isdigit(*currentpointer)) {
            /* do digit things */
            currentpointer++;  /*or if you're reading an entire number, += number_of_digits_read */
        } else if (currentpointer=='+' || *currentpointer == '-') {
            /* do plus/minus things */
            currentpointer++;
        } /* and so on */

  7. #7
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    I have changed the function to use char*s instead, but am getting alot of warnings and produces a segmentation fault on runtime. Here is the updated ConvertToPolishNotation:

    Code:
    //Pass in inputqueue for reading, and outputqueue for writing
    char ConvertToPolishNotation(char *inputqueue, char *outputqueue) {
        char operatorqueue[50];
        char *currentpointer = inputqueue;
        //currentpointer++;
        char *oqpointer = operatorqueue;
        char *lastwritteninoq = outputqueue;
        int counter = 0;
        while (*currentpointer != '\0') { /*or whatever your end of input is*/
            if (isdigit(*currentpointer)) {
                while (isdigit(*currentpointer++)) {
                    pushelement(*oqpointer, &outputqueue);
                }
                lastwritteninoq++;    
                currentpointer++;
            }  /*or if you're reading an entire number, += number_of_digits_read */
            else if (*currentpointer=='+' || *currentpointer == '-' || 
                      *currentpointer=='*' || *currentpointer == '/') {
                pushelement(*oqpointer, &operatorqueue); 
                currentpointer++;
            } 
            else if (*currentpointer=='(') {
                 while ((*oqpointer != '(') && (counter < 50)) {
                       //Until the token at the top of the stack is a left parenthesis,
                       //pop operators off the stack onto the output queue  
                       outputqueue[*lastwritteninoq] = popelement(counter, &operatorqueue);
                       counter++;
                       lastwritteninoq++;
                       oqpointer++;
                       currentpointer++; 
                 }
                 if (counter == 50) { //BRACKET MISMATCH
                    MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                    return 0;
                }
                //Pop the left parenthesis from the stack, but not onto the output queue.    
                popelement(counter, &operatorqueue);
            } //END BRACKET 
        } //NO MORE TOKENS
        *oqpointer = operatorqueue[0];
        //While there are still operator tokens in the stack:
        while (*oqpointer != '\0') {
            if ((oqpointer == ')') || (oqpointer == '(')) {//BRACKET  
                MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                return 0;
            }
            else oqpointer++;
            outputqueue[*lastwritteninoq] = popelement(counter, operatorqueue);
            lastwritteninoq++;
        }
        return &outputqueue;  
    }
    Each line that calles either popelement or pushelement raises a warning so I have included them below:
    Code:
    void pushelement(char c, char *queue[255]) {
        int i = 0;
        while ((queue[i] != 0) || (i<255))
            i++;
        if (i=255) return;
        queue[i+1] = c;
        return; 
    }
    
    char popelement(int position, char *queue[]) {
         int length = sizeof(queue);
         int i;
         char c = queue[position]; 
         queue[position] = 0;
         position++;
         for (i=0; i<length; i++) {
             queue[i] = queue[i + position];
         }
         return c;
    }
    On debugging, I found that inputqueue[0] equals the whole of the character array that was passed two it, and is not split up between elements. This means that inputqueue[1] is out of bounds and so incrementing currentpointer will go out of bounds. Any ideas on how to fix this?
    Last edited by P4R4N01D; 11-14-2008 at 07:50 PM. Reason: Edited ConvertToPolishNotation
    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. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    It's either * or [], not both.

  9. #9
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Here is the next version, I have removed all but one of the warnings (I have not thought about return &outputqueue) and have removed all the calls to the popelement and pushelement functions. After debugging, I have found that '('s don't get removed from the operatorqueue, so a "bracket mismatch" always gets generated. I have highlighed where this problem is in red. I have also fixed up all the warnings and errors, but it doesn't produce the right outputqueue (which instead has garbage values). Thanks for your help so far, tabstop, but i'm really stuck on the logic of this one.

    Code:
    //Pass in inputqueue for reading, and outputqueue for writing
    int ConvertToPolishNotation(char inputqueue[], char outputqueue[]) {
        char *lastwritteninoq = outputqueue, operatorqueue[50];
        memset(operatorqueue,0, 50);
        char *currentpointer = inputqueue, *oqpointer = operatorqueue;
        int counter = 0;
        while (*currentpointer != '\0') { /*or whatever your end of input is*/
            if (isdigit(*currentpointer)) {
                while (isdigit(*currentpointer++)) 
                    *lastwritteninoq++ = *currentpointer;
                lastwritteninoq++;
                currentpointer++;
            }  /*or if you're reading an entire number, += number_of_digits_read */
            else if (*currentpointer=='+' || *currentpointer == '-' || 
                      *currentpointer=='*' || *currentpointer == '/') {
                *oqpointer++ = *currentpointer;
                currentpointer++;
            } 
            else if (*currentpointer=='(') {//Push it onto stack
                *oqpointer++ = *currentpointer;
                currentpointer++;
            }
            else if (*currentpointer==')') {
                 while ((*oqpointer != '(') && (*currentpointer != '\0')
                      && (counter < 50)) {
                       //Until the token at the top of the stack is a left parenthesis,
                       //pop operators off the stack onto the output queue  
                       outputqueue[*lastwritteninoq] = *--oqpointer;
                       counter++;
                       lastwritteninoq++;
                       oqpointer++;
                       currentpointer++; 
                 }
                 if (counter == 50) { //BRACKET MISMATCH
                    MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                    return -1;
                }
                //Pop the left parenthesis from the stack, but not onto the output queue.    
                *--oqpointer;
            } //END BRACKET 
        } //NO MORE TOKENS
        oqpointer = operatorqueue; //Reset pointer
        //While there are still operator tokens in the stack:
        while (*oqpointer != '\0') {
            if ((*oqpointer == ')') || (*oqpointer == '(')) {//BRACKET  
                MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                return -1;
            }
            else oqpointer++;
            outputqueue[*lastwritteninoq] = *--oqpointer;
            lastwritteninoq++;
        }
        return 1;  
    }
    Here is a proceedure of what the function should do from wikipedia
    * While there are tokens to be read:
    * Read a token.
    * If the token is a number, then add it to the output queue.
    * Until the topmost element of the stack is a left parenthesis, pop the element from the stack and push it onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
    * If the token is an operator, o1, then:
    * while there is an operator, o2, at the top of the stack, and either
    o1 is associative or left-associative and its precedence is less than (lower precedence) or equal to that of o2, or
    o1 is right-associative and its precedence is less than (lower precedence) that of o2,
    pop o2 off the stack, onto the output queue;
    * push o1 onto the stack.
    * If the token is a left parenthesis, then push it onto the stack.
    * If the token is a right parenthesis:
    * Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
    * Pop the left parenthesis from the stack, but not onto the output queue.
    * If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
    * When there are no more tokens to read:
    * While there are still operator tokens in the stack:
    * If the operator token on the top of the stack is a parenthesis, then there are mismatched parenthesis.
    * Pop the operator onto the output queue.
    * Exit.
    Last edited by P4R4N01D; 11-15-2008 at 08:55 PM. Reason: update problem, error fixes
    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
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223

    Still having trouble, Please help!

    Sorry for double posting, but I am still stuck. I have found what is going wrong and what needs to be fixed though, so I have only included the lines where the problem occurs. The first problem is that *lastwritteninoq is meant to point to the last element, but instead points to the first so the operator gets placed at the begining of the list instead of the end. The second problem is that left brackets don't get removed from the operator queue. After these two problems are fixed, then the function should be finished.
    Code:
            while (*currentpointer != '\0') { /*or whatever your end of input is*/
            if (isdigit(*currentpointer)) {
                    *lastwritteninoq++ = *currentpointer;
                    currentpointer++;
            }  /*or if you're reading an entire number, += number_of_digits_read */
            else if (*currentpointer=='+' || *currentpointer == '-' || 
                      *currentpointer=='*' || *currentpointer == '/') {
                *oqpointer++ = *currentpointer;
                currentpointer++;
            } 
            else if (*currentpointer=='(') {//Push it onto stack
                *oqpointer++ = *currentpointer;
                currentpointer++;
            }
           else if (*currentpointer==')') {
                 while ((*oqpointer != '(') && (*currentpointer != '\0')
                      && (counter < 50)) {
                       //Until the token at the top of the stack is a left parenthesis,
                       //pop operators off the operator stack onto the output queue
                       outputqueue[*lastwritteninoq] = *--oqpointer;
                       counter++;
                       lastwritteninoq++;
                       currentpointer++; 
                 }
                 if (counter == 50) { //BRACKET MISMATCH
                    MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                    return -1;
                }
                //This line is meant to pop the left bracket from the stack, but not onto the output queue, but doesn't work    
                *--oqpointer;
            } //END BRACKET
    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);

  11. #11
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    I have fixed the above errors, but I run into a problem when I enter "(1-2)*(4+5). *lastwritteninoq = '\0' after the first '(' and the '*' and everything after it gets disgarded. I have highlighted the line where the '*' gets disgarded, and have tried removing that line to no avail. Anyway, it is getting there, and sorry again, but I couldn't edit the last post. Note: (1-2)*(4+5) should be converted to 1 2 - 4 5 + *, but instead gets converted to 1 2 -.

    Code:
    int ConvertToPolishNotation(char inputqueue[], char outputqueue[]) {
        char *lastwritteninoq = outputqueue, operatorqueue[50];
        memset(operatorqueue,0, 50);
        char *currentpointer = inputqueue, *oqpointer = operatorqueue;
        int counter = 0;
        while (*currentpointer != '\0') { /*or whatever your end of input is*/
            if (isdigit(*currentpointer)) {
                //while (isdigit(*currentpointer++)) 
                    *lastwritteninoq++ = *currentpointer++;
                //}
            }  /*or if you're reading an entire number, += number_of_digits_read */
            else if (*currentpointer=='+' || *currentpointer == '-' || 
                      *currentpointer=='*' || *currentpointer == '/') {
                *oqpointer++ = *currentpointer++;
            } 
            else if (*currentpointer=='(') {//Push it onto stack
                *oqpointer++ = *currentpointer++;
            }
            else if (*currentpointer==')') {
                 while ((*oqpointer != '(') && (*currentpointer != '\0')
                      && (counter < 50)) {
                       //Until the token at the top of the stack is a left parenthesis,
                       //pop operators off the operatorqueue onto the outputqueue
                       *lastwritteninoq++ = *--oqpointer;
                       counter++;
                       lastwritteninoq++; 
                       currentpointer++;
                 }
                 if (counter == 50) { //BRACKET MISMATCH
                    MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                    return -1;
                }
                //Pop the left parenthesis from the stack, but not onto the output queue.    
                *--oqpointer = '\0';
            } //END BRACKET 
        } //NO MORE TOKENS
        oqpointer = operatorqueue; //Reset pointer
        //While there are still operator tokens in the stack:
        while (*oqpointer != '\0') {
            if ((*oqpointer == ')') || (*oqpointer == '(')) {//BRACKET  
                MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                return -1;
            }
            else {
                 oqpointer++;
                 *lastwritteninoq++ = *--oqpointer;
                 lastwritteninoq++;
                 *--oqpointer = '\0';
            }
        }
        return 1;
    }
    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);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reverse Polish Notation
    By Lucid15 in forum C Programming
    Replies: 7
    Last Post: 02-16-2009, 10:05 PM
  2. Postfix (reverse polish notation) calculator
    By ottomated in forum C Programming
    Replies: 7
    Last Post: 05-06-2008, 05:32 PM
  3. gethostbyaddr() reverse lookups failing (???)
    By Uncle Rico in forum C Programming
    Replies: 9
    Last Post: 08-19-2005, 09:22 AM
  4. infix vs Reverse Polish notation
    By dionys in forum C Programming
    Replies: 1
    Last Post: 05-10-2004, 02:25 PM
  5. Reverse Polish Notation???
    By Wizard_D in forum C Programming
    Replies: 6
    Last Post: 11-01-2001, 12:20 AM