Thread: More help needed w/ Shunting Yard Algorithm

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

    More help needed w/ Shunting Yard Algorithm

    I am still having trouble w/ my function to convert infix to postfix notation. I have figured out how to convert equations with two numbers and one operand successfully and how to work w/ numbers that are > 1 digit, but the algortihm does not work correctly for equations w/ more than one operator e.g. (1-2)*(4+5) which should output 1 2 - 4 5 + * instead outputs 1 2 -. I am pretty sure it is the result of pointers being incremented to far so they point to '\0', but I am not sure how to fix it.
    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, nextToken = 0;
        while (*currentpointer != '\0') { /*or whatever your end of input is*/
            while (isdigit(*currentpointer)) {                
                    *lastwritteninoq++ = *currentpointer++;
                    nextToken = 1;
            }  /*or if you're reading an entire number, += number_of_digits_read */
            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) && (*currentpointer==')')) {
                       //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 operatorqueue, but not onto the outputqueue. 
                *--oqpointer = '0';
            } //END BRACKET 
            if (nextToken) { //Space-seperate each token, this helps w/ multiple
                *lastwritteninoq++ = ' '; //digits
                nextToken = 0;
            }
        } //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 if (*oqpointer == '0') oqpointer++;
            else {
                 oqpointer++;
                 *lastwritteninoq++ = *(--oqpointer);
                 lastwritteninoq++;
                 *oqpointer = '0';
            }
        }
        return 1;
    }
    For the example above, *lastwritteninoq = '\0' when *currentpointer = ')' and from there nothing can be added to the outputqueue. I beleive a similar thing happens w/ oqpointer but I am stumped on how to fix it.
    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
    Code:
                 while ((*oqpointer != '(') && (*currentpointer != '\0')
                      && (counter < 50) && (*currentpointer==')')) {
                       //Until the token at the top of the stack is a left parenthesis,
                       //pop operators off the operatorqueue onto the outputqueue
                       
                       *lastwritteninoq++ = *(--oqpointer); /*Increment me once*/
                       counter++;
                       lastwritteninoq++; /*Increment me twice?*/
                       currentpointer++;
                 }

  3. #3
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    I have been researching this very thing in a book called "Algorithms in C" Third ed. by Robert Sedgwick. You may want to review section 4.2 and again in section 5 if you get this book! The technique uses a pushdown stack ADT and most complex mathematical algorithms use this technique to break them down to smaller and smaller pieces. Makes for good recursive function techniques as well.

    Solution is in the book and is a good read.

  4. #4
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    Thanks tabstop, I had tried that before but w/ the input (1-2), it produced 1 2- - which led me to beleive leave that line as it was. However, (1-2)*(4+5) worked fine outputing
    Code:
    1 2- 4 5+ *
    Note that there is no space when *currentpointer = ')'. This is easily fixed by adding *lastwritteninoq++ = ' ';. This is all the code that has been changed below.

    Code:
     while ((*oqpointer != '(') && (*currentpointer != '\0')
                      && (counter < 50) && (*currentpointer==')')) {
                       //Until the token at the top of the stack is a left parenthesis,
                       //pop operators off the operatorqueue onto the outputqueue
                       
                       *lastwritteninoq++ = ' ';
                       *lastwritteninoq++ = *(--oqpointer);
                       counter++;
                       currentpointer++;
                 }
                 if (counter == 50) { //BRACKET MISMATCH
                    MessageBox(NULL, "Bracket Mismatch", "Error", MB_OK);
                    return -1;
                }
                //Pop the left parenthesis from the operatorqueue, but not onto the outputqueue. 
                *--oqpointer = '0';
                *++oqpointer = '0';
            } //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);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shunting yard algorithm.
    By Homunculus in forum C++ Programming
    Replies: 1
    Last Post: 05-01-2008, 02:41 AM
  2. Shunting Yard Algorithm
    By EvilGuru in forum C Programming
    Replies: 3
    Last Post: 11-04-2005, 01:20 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM