| 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 run-time 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 run-time 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.
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 off-topic.
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 [Off-topic:]
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 off-topic.
> 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 off-topic.
> 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 |
|
| |
|
