# Thread: More help needed w/ Shunting Yard Algorithm

1. ## 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;
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.

2. 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. 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. 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```