Author 
Message 
aade #1 / 10

help in K&R2
Hi all and thanks for taking the time to read this. i have copied and compiled the polish calculator program the program compiles on turboc v2.01 and {*filter*}shed dev c++ (as a c prog and not .ccp) it wont compile on borland c++v4.5 as a .c program it gives about five errors any way this calc program compiles ok but has an error on the users output scren saying termination error i am planning (and have spent many hours already) to spend alot of time studyiing this k&r2 c program that i would like some kind person to check it for me to see if i've done things right and i havent yet learnt to debug yet (althoughi am now trying) i dont know if i posted all the code if i am breaking copyright laws could i? should'nt i?? regards aade

Tue, 20 Jan 2004 19:04:37 GMT 


Tom Alsbe #2 / 10

help in K&R2
Read comments below:
<snip /> Quote: > i dont know if i posted all the code if i am breaking copyright laws could > i? should'nt i??
I don't think you will be breaking copyright laws by posting that code. I think it will qualify as fair use under the US Constitution's Copyright Law (refer to section 107  Limitations on exclusive rights: Fair use). And I think people will be able to help much more if they'll see the source of the error. Also post the exact error messages from the compiler and when the runtime errors happen.  Tom Alsberg  certified insane, complete illiterate.
Homepage: http://www.cs.huji.ac.il/~alsbergt/ * An idea is not responsible for the people who believe in it.

Tue, 20 Jan 2004 21:54:37 GMT 


aade #3 / 10

help in K&R2
Quote: > Hi all and thanks for taking the time to read this. > i have copied and compiled the polish calculator program > the program compiles on turboc v2.01 and {*filter*}shed > dev c++ (as a c prog and not .ccp) it wont compile on borland c++v4.5 as a > .c program it gives about five errors > any way this calc program compiles ok but has an error on the users output > scren saying > termination error > i am planning (and have spent many hours already) to spend alot of time > studyiing this k&r2 c program that i would like some kind person to check it > for me to see if > i've done things right > and i havent yet learnt to debug yet (althoughi am now trying) > i dont know if i posted all the code if i am breaking copyright laws could > i? should'nt i?? > regards > aade
i have found out the source of the problem i didnt enter in polish notation, now i do it works a charm i think?? what is polish notation regards aade

Tue, 20 Jan 2004 22:49:29 GMT 


aade #4 / 10

help in K&R2
Quote: > Read comments below:
> <snip /> > > i dont know if i posted all the code if i am breaking copyright laws could > > i? should'nt i?? > I don't think you will be breaking copyright laws by posting that > code. I think it will qualify as fair use under the US Constitution's > Copyright Law (refer to section 107  Limitations on exclusive rights: > Fair use). > And I think people will be able to help much more if they'll see the > source of the error. Also post the exact error messages from the > compiler and when the runtime errors happen. >  > Tom Alsberg  certified insane, complete illiterate.
> Homepage: http://www.***.com/ ~alsbergt/ > * An idea is not responsible for the people who believe in it.
it worked on a {*filter*}shed dec++ compiler and workd but on a turboc v2.01 i get these errors scanf: floating point formats not linked abnormal program termination heres the code /* this file of code compiles on turboc v 2.01 */ /* but terminates with errors */ #include <stdio.h> #include <stdlib.h> /* for atof() */ #define MAXOP 100 /*max size of operand or operator */ #define NUMBER '0' /* signal that a number was found */ int getop(char []); void push(double); double pop(void); /* reverse polish calculator */ int main () { int type; double op2; char s[MAXOP]; while ((type = getop(s)) != EOF) { switch (type) { case NUMBER: push(atof(s)); /* convert string to float */ break; case '+': push(pop() + pop()); break; case '*': push(pop() * pop()); break; case '': op2 = pop(); push(pop()  op2); break; case '/': op2 = pop(); if (op2 != 0.0) push(pop() / op2); else printf("error: zero division\n"); break; case'\n': printf("\t%.8g\n" , pop()); break; default: printf("error: unknown command %s\n",s); break; } } return 0; Quote: }
#define MAXVAL 100 /* max depth of val stack */ int sp = 0; /* next free position */ double val[MAXVAL]; /* value of stack */ /**/ /* push: push f onto value stack */ void push(double f) /**/ { if(sp < MAXVAL) val[sp++] = f; else printf("error: stack full, cant push %g\n",f); Quote: }
/**/ /* pop: pop and return top value from stack */ double pop(void) /**/ { if (sp > 0) return val[sp]; else { printf("error: stack empty\n"); return 0.0; } Quote: }
#include <ctype.h> int getch(void); void ungetch(int); /**/ /* getop: get next operator or numeric operand */ int getop(char s[]) /**/ { int i ,c; while ((s[0] = c = getch()) == ' '  c == '\t') s[1] = '\0'; /* digit means a number */ if (!isdigit(c) && c != '.') /*!isdigit not true if c isa digit */ return c; /* not a number */ i = 0; if (isdigit(c)) /*collect integer part */ while (isdigit(s[++i] = c = getch())) ; if (c == '.') /* collect fractional part */ while (isdigit(s[++i] = c = getch())) ; s[i] = '\0'; if (c != EOF) ungetch(c); return NUMBER; /* number found */ } #define BUFSIZE 100 char buf[BUFSIZE]; /* buffer for ungetch */ int bufp = 0; /* next free position in buf */ /**/ /* get a (possibly pushed back) character */ int getch(void) /**/ { return (bufp > 0) ? buf[bufp] : getchar(); /*bufp pointer to next free position in buf[] */ Quote: }
/**/ /* push char back on input */ void ungetch(int c) /**/ { if (bufp >=BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; Quote: }
sorry about over embelishing function s its just to point them out to me for a while regards aade

Tue, 20 Jan 2004 23:09:11 GMT 


#5 / 10

help in K&R2

Wed, 18 Jun 1902 08:00:00 GMT 


Gergo Bara #6 / 10

help in K&R2
Quote:
> i have found out the source of the problem i didnt enter > in polish notation, now i do it works a charm i think?? > what is polish notation
K&R explain that briefly on page 74: it's a notation where an operator follows its operands. The usual (infix) way of denoting the addition of 2 and 3 is to put a + sign between the numbers: 2 + 3 This format is what humans are used to seeing, but it is harder to write a program that correctly parses it. The idea of Reverse Polish notation is to put the operator *after* its operands: 2 3 + This looks unusual but is much simpler to parse in software, partly because no parentheses are needed. The way to parse it is simple (error checking omitted):  Read the next token.  If that token is a number:  Push it onto a stack.  Else if the token is an operator:  Pop the required number of operands off the stack.  Apply the operator to the operands.  Push the result onto the stack.  If there are unread tokens in the input stream:  Go to the first line.  Else (if no syntax errors occured):  There is exactly one value on the stack. Pop it off to get the input expression's value. The implementation is given by K&R, and I think it should be fairly easy to understand their code. The question that remains is "how do I convert an expression from infix notation to Reverse Polish and vice versa?" A simple way to do that is to draw (or at least imagine) a parse tree. Consider the following expression as an example: ((1 + 2) * 3) % 4 + 5 * 6 As you can see, parentheses were needed to indicate which operations should be performed first. As a first step towards a parse tree, it helps to add even more parentheses (I'll use square brackets instead to make them stick out) according to operator precedence: [ [ [ ((1 + 2) * 3) ] % 4 ] + [ 5 * 6 ] ] At this point, knowledge of precedence is no longer needed: we don't need to remember that multiplication comes before addition because the brackets leave no ambiguity. Once we have come this far, we can start drawing the parse tree (you'll need to view this mess in a fixed width font). The next thing to do is to find the "uppermost" operator, i.e. the one that has the least number of brackets around it. In our case that is the second + sign in the expression. We use that + sign as the root of a tree and draw two children: the two subexpressions it operates on. "+" / \ / \ [ [ ((1 + 2) * 3) ] % 4 ] [ 5 * 6 ] Now you apply the same rule recursively to each of the children: "+" / \ / \ "%" "*" / \ / \ [ ((1 + 2) * 3) ] 4 5 6 You keep going until there are no brackets or parentheses left. The complete parse tree then looks like this: "+" / \ / \ "%" "*" / \ / \ "*" 4 5 6 / \ "+" 3 / \ 1 2 If this looks like a lot of work so far, that's because it was. But you don't really have to draw the parse tree every time you want to parse an infix expression; with a little practice it will form in your head automatically. Now that we have built the tree, we'll take it apart right away: to build the expression's Reverse Polish representation, you start at the bottom and work upwards, taking two operands off the tree and writing the connecting operator behind them. In our example, we first take 1 and 2 and the + sign that operates on them: 1 2 + (Inside the calculator, as soon as these three tokens are read, their result is computed and pushed back to the stack. In our tree that would mean deleting 1 and 2 and replacing the first + sign by the literal 3, the result of the addition.) Now we look at he next operator from the bottom: It's the * sign that connects (1 2 +) and 3. Again, we write down the operands, followed by their operator: 1 2 + 3 * We keep executing this step until the whole tree has been processed. In our example [as a reminder to you, and especially to me, the original expression was ((1 + 2) * 3) % 4 + 5 * 6 ], the complete Reverse Polish expression comes out to be the following: 1 2 + 3 * 4 % 5 6 * + Note that the numbers appear in the same order as they did in the original expression, and the operators in the order we read them out of the parse tree, i.e. bottom to top, left to right. For the conversion back to infix notation we can use these properties to again build a parse tree, this time from bottom to top; start with "1 2 +": "+" / \ 1 2 then add the 3 and the multiplication sign, etc. The tree will come out to be the same as the one we built to convert from infix. To read the infix representation out of the parse tree, read it again, from bottom to top, left to right. First you will encounter the branches denoting this subexpression: 1 + 2 Surround it with parentheses: (1 + 2) Keep going, on to the multiplication and the 3, and add parentheses: ((1 + 2) * 3) and so on, until the whole tree has been read: ((((1 + 2) * 3) % 4) + (5 * 6)) Finally, drop unnecessary parentheses: ((1 + 2) * 3) % 4 + 5 * 6 and you are back to the original expression. I hope this explanation was clear and detailed enough to answer your questions about Reverse Polish notation; further questions are welcome but should maybe dealt with outside of comp.lang.c where this is increasingly offtopic. Fla^H^H^HCorrections are also welcome. Gergo  In the stairway of life, you'd best take the elevator.

Wed, 21 Jan 2004 00:31:47 GMT 


Tom Alsbe #7 / 10

help in K&R2
[Offtopic:] This is a good way to convert infix notation to postfix notation. But there is a simpler one for an algorithm to follow, without needing to parenthesise or build a parse tree. Given that the stream is tokenized, and the operator precedence/associativity is known, the following does it using a stack, getting an infix noted expression on input and outputting a postfix noted expression: While there are tokens left in the input, do: Read token from input If token is:  an operand  send to output.  an operator or opening paren  pop elements from stack and send to output until either of the following is reached: * an operator of lower precedence, or * a right associative operator of equal precedence. then push operator/paren to stack.  a closing paren  pop elements from stack and send to output until an opening paren is reached.  end of input  pop remaining tokens from stack, and send to output.  Tom
<snip /> Quote: > The question that remains is "how do I convert an expression from > infix notation to Reverse Polish and vice versa?" A simple way to do > that is to draw (or at least imagine) a parse tree. Consider the > following expression as an example: > ((1 + 2) * 3) % 4 + 5 * 6 > As you can see, parentheses were needed to indicate which operations > should be performed first. As a first step towards a parse tree, it > helps to add even more parentheses (I'll use square brackets instead > to make them stick out) according to operator precedence: > [ [ [ ((1 + 2) * 3) ] % 4 ] + [ 5 * 6 ] ] > At this point, knowledge of precedence is no longer needed: we don't > need to remember that multiplication comes before addition because > the brackets leave no ambiguity. > Once we have come this far, we can start drawing the parse tree > (you'll need to view this mess in a fixed width font). The next > thing to do is to find the "uppermost" operator, i.e. the one that > has the least number of brackets around it. In our case that is the > second + sign in the expression. We use that + sign as the root of a > tree and draw two children: the two subexpressions it operates on. > "+" > / \ > / \ > [ [ ((1 + 2) * 3) ] % 4 ] [ 5 * 6 ] > Now you apply the same rule recursively to each of the children: > "+" > / \ > / \ > "%" "*" > / \ / \ > [ ((1 + 2) * 3) ] 4 5 6 > You keep going until there are no brackets or parentheses left. The > complete parse tree then looks like this: > "+" > / \ > / \ > "%" "*" > / \ / \ > "*" 4 5 6 > / \ > "+" 3 > / \ > 1 2 > If this looks like a lot of work so far, that's because it was. But > you don't really have to draw the parse tree every time you want to > parse an infix expression; with a little practice it will form in > your head automatically. > Now that we have built the tree, we'll take it apart right away: to > build the expression's Reverse Polish representation, you start at > the bottom and work upwards, taking two operands off the tree and > writing the connecting operator behind them. > In our example, we first take 1 and 2 and the + sign that operates > on them: > 1 2 + > (Inside the calculator, as soon as these three tokens are read, > their result is computed and pushed back to the stack. In our tree > that would mean deleting 1 and 2 and replacing the first + sign by > the literal 3, the result of the addition.) > Now we look at he next operator from the bottom: It's the * sign > that connects (1 2 +) and 3. Again, we write down the operands, > followed by their operator: > 1 2 + 3 * > We keep executing this step until the whole tree has been processed. > In our example [as a reminder to you, and especially to me, the > original expression was ((1 + 2) * 3) % 4 + 5 * 6 ], the complete > Reverse Polish expression comes out to be the following: > 1 2 + 3 * 4 % 5 6 * + > Note that the numbers appear in the same order as they did in the > original expression, and the operators in the order we read them out > of the parse tree, i.e. bottom to top, left to right. > For the conversion back to infix notation we can use these > properties to again build a parse tree, this time from bottom to > top; start with "1 2 +": > "+" > / \ > 1 2 > then add the 3 and the multiplication sign, etc. The tree will come > out to be the same as the one we built to convert from infix. To > read the infix representation out of the parse tree, read it again, > from bottom to top, left to right. First you will encounter the > branches denoting this subexpression: > 1 + 2 > Surround it with parentheses: > (1 + 2) > Keep going, on to the multiplication and the 3, and add parentheses: > ((1 + 2) * 3) > and so on, until the whole tree has been read: > ((((1 + 2) * 3) % 4) + (5 * 6)) > Finally, drop unnecessary parentheses: > ((1 + 2) * 3) % 4 + 5 * 6 > and you are back to the original expression. > I hope this explanation was clear and detailed enough to answer your > questions about Reverse Polish notation; further questions are > welcome but should maybe dealt with outside of comp.lang.c where > this is increasingly offtopic. > Fla^H^H^HCorrections are also welcome. > Gergo
 Tom Alsberg  certified insane, complete illiterate.
Homepage: http://www.cs.huji.ac.il/~alsbergt/ * An idea is not responsible for the people who believe in it.

Wed, 21 Jan 2004 01:05:26 GMT 


aade #8 / 10

help in K&R2
Quote:
> > i have found out the source of the problem i didnt enter > > in polish notation, now i do it works a charm i think?? > > what is polish notation > K&R explain that briefly on page 74: it's a notation where an > operator follows its operands. The usual (infix) way of denoting the > addition of 2 and 3 is to put a + sign between the numbers: > 2 + 3 > This format is what humans are used to seeing, but it is harder to > write a program that correctly parses it. The idea of Reverse Polish > notation is to put the operator *after* its operands: > 2 3 + > This looks unusual but is much simpler to parse in software, partly > because no parentheses are needed. > The way to parse it is simple (error checking omitted): >  Read the next token. >  If that token is a number: >  Push it onto a stack. >  Else if the token is an operator: >  Pop the required number of operands off the stack. >  Apply the operator to the operands. >  Push the result onto the stack. >  If there are unread tokens in the input stream: >  Go to the first line. >  Else (if no syntax errors occured): >  There is exactly one value on the stack. Pop it off to get the > input expression's value. > The implementation is given by K&R, and I think it should be fairly > easy to understand their code. > The question that remains is "how do I convert an expression from > infix notation to Reverse Polish and vice versa?" A simple way to do > that is to draw (or at least imagine) a parse tree. Consider the > following expression as an example: > ((1 + 2) * 3) % 4 + 5 * 6 > As you can see, parentheses were needed to indicate which operations > should be performed first. As a first step towards a parse tree, it > helps to add even more parentheses (I'll use square brackets instead > to make them stick out) according to operator precedence: > [ [ [ ((1 + 2) * 3) ] % 4 ] + [ 5 * 6 ] ] > At this point, knowledge of precedence is no longer needed: we don't > need to remember that multiplication comes before addition because > the brackets leave no ambiguity. > Once we have come this far, we can start drawing the parse tree > (you'll need to view this mess in a fixed width font). The next > thing to do is to find the "uppermost" operator, i.e. the one that > has the least number of brackets around it. In our case that is the > second + sign in the expression. We use that + sign as the root of a > tree and draw two children: the two subexpressions it operates on. > "+" > / \ > / \ > [ [ ((1 + 2) * 3) ] % 4 ] [ 5 * 6 ] > Now you apply the same rule recursively to each of the children: > "+" > / \ > / \ > "%" "*" > / \ / \ > [ ((1 + 2) * 3) ] 4 5 6 > You keep going until there are no brackets or parentheses left. The > complete parse tree then looks like this: > "+" > / \ > / \ > "%" "*" > / \ / \ > "*" 4 5 6 > / \ > "+" 3 > / \ > 1 2 > If this looks like a lot of work so far, that's because it was. But > you don't really have to draw the parse tree every time you want to > parse an infix expression; with a little practice it will form in > your head automatically. > Now that we have built the tree, we'll take it apart right away: to > build the expression's Reverse Polish representation, you start at > the bottom and work upwards, taking two operands off the tree and > writing the connecting operator behind them. > In our example, we first take 1 and 2 and the + sign that operates > on them: > 1 2 + > (Inside the calculator, as soon as these three tokens are read, > their result is computed and pushed back to the stack. In our tree > that would mean deleting 1 and 2 and replacing the first + sign by > the literal 3, the result of the addition.) > Now we look at he next operator from the bottom: It's the * sign > that connects (1 2 +) and 3. Again, we write down the operands, > followed by their operator: > 1 2 + 3 * > We keep executing this step until the whole tree has been processed. > In our example [as a reminder to you, and especially to me, the > original expression was ((1 + 2) * 3) % 4 + 5 * 6 ], the complete > Reverse Polish expression comes out to be the following: > 1 2 + 3 * 4 % 5 6 * + > Note that the numbers appear in the same order as they did in the > original expression, and the operators in the order we read them out > of the parse tree, i.e. bottom to top, left to right. > For the conversion back to infix notation we can use these > properties to again build a parse tree, this time from bottom to > top; start with "1 2 +": > "+" > / \ > 1 2 > then add the 3 and the multiplication sign, etc. The tree will come > out to be the same as the one we built to convert from infix. To > read the infix representation out of the parse tree, read it again, > from bottom to top, left to right. First you will encounter the > branches denoting this subexpression: > 1 + 2 > Surround it with parentheses: > (1 + 2) > Keep going, on to the multiplication and the 3, and add parentheses: > ((1 + 2) * 3) > and so on, until the whole tree has been read: > ((((1 + 2) * 3) % 4) + (5 * 6)) > Finally, drop unnecessary parentheses: > ((1 + 2) * 3) % 4 + 5 * 6 > and you are back to the original expression. > I hope this explanation was clear and detailed enough to answer your > questions about Reverse Polish notation; further questions are > welcome but should maybe dealt with outside of comp.lang.c where > this is increasingly offtopic. > Fla^H^H^HCorrections are also welcome. > Gergo >  > In the stairway of life, you'd best take the elevator.
thank you gergo Barany for such a great explanation i'll be saving this for lookup times regards aade

Wed, 21 Jan 2004 01:04:05 GMT 


#9 / 10

help in K&R2

Wed, 18 Jun 1902 08:00:00 GMT 


rand mair fhe #10 / 10

help in K&R2
Quote: >i have found out the source of the problem i didnt enter >in polish notation, now i do it works a charm i think?? >what is polish notation >regards >aade
would you rather remember lucasiewicz notation with a bar trhough the l he realized that if you prefixed operators only with fixed arity you do not need parenthesis + * 1 2 * 3 4 for 1*2 + 3*4 * + 1 2 + 3 4 for (1+2)*(4+4) + * 2 3 4 for 2*3 + 4 * + 2 3 4 for (2+3) * 4 polish notation can be implemented with an operator stack and operand stack reverse polish notation uses postfixed operators so it only needs an operand stack 1 2 * 3 4 * + 1 2 + 3 4 + * 2 3 * 4 + 2 3 + 4 *

Wed, 21 Jan 2004 03:20:47 GMT 


