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.

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.

Sorry, text[] was meant tobe inputqueue[], I'll fix that up, thanks for pointing that out.

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.)

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?

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 */

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?

It's either * or [], not both.

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:
* 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.

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

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; }