# Impix or reverse polish notation

• 11-12-2008
P4R4N01D
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.
• 11-12-2008
tabstop
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.
• 11-12-2008
P4R4N01D
Sorry, text[] was meant tobe inputqueue[], I'll fix that up, thanks for pointing that out.
• 11-12-2008
tabstop
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.)
• 11-12-2008
P4R4N01D
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?
• 11-13-2008
tabstop
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 */```
• 11-14-2008
P4R4N01D
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?
• 11-14-2008
tabstop
It's either * or [], not both.
• 11-14-2008
P4R4N01D
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
Quote:

* While there are tokens to be read:
* 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.
• 11-17-2008
P4R4N01D
```        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```
```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; }```