# More help needed w/ Shunting Yard Algorithm

• 12-01-2008
P4R4N01D
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.
• 12-02-2008
tabstop
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++;             }```
• 12-02-2008
slingerland3g
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.
• 12-02-2008
P4R4N01D
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```