reverse polish notation calculator problems

[Pole]

Hello, I have several questions regarding the calculator presented in chapter 4.3 of K&R.

1. How can a switch command operate with a case NUMBER, since it is always '0' (not changed anywhere)

2. Line 84 - why is there an ending char (\0) added at the second space in an array/stack.

3. Why does getch function (/* get a (possibly pushed-back) character */), read character rejected by ungetch. (line 105)
I think that we don't need the rejected character (because it's EOF or sth(?) )

The code:

#include <stdio.h> 
#include <stdlib.h> /*for atof*/
#include <ctype.h>


#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 notation calculator */
int main()
{
    int type;
    double op2;
    char s[MAXOP];
    
    while ((type = getop(s)) != EOF) {
        switch (type) {
        case NUMBER:
            push(atof(s));
            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 divisor\n");
            break;
        case '\n':
            printf("\t%.8g\n", pop());
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
    }
    return 0;
}

#define MAXVAL 100 /* maximum depth of val stack */
int sp = 0; /* next free stack position */
double val[MAXVAL]; /* value stack */

/* push: push f onto value stack */
void push(double f)
{
    if (sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error: stack full, can't push %g\n", f);
}
/* 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;
    }
}

/* getop: get next character or numeric operand */
int getch(void);
void ungetch(int);

int getop(char s[])
{
    int i, c;
    while ((s[0] = c = getch()) == ' ' || c == '\t')
        ;
    s[1] = '\0';
    if (!isdigit(c) && c != '.')
        return c;/* not a number */
    i = 0;
    if (isdigit(c))/* collect integer part */
        while (isdigit(s[++i] = c = getch()))
            ;
    if (c == '.')/* collect fraction part */
        while (isdigit(s[++i] = c = getch()))
            ;
    s[i] = '\0';
    if (c != EOF)
        ungetch(c);
    return NUMBER;
}

char buf[MAXOP]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */

int getch(void) /* get a (possibly pushed-back) character */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c)/* push character back on input */
{
    if (bufp >= MAXOP)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}

[std10093]

1- switch checkes the value in every's case condition,so NUMBER is defined as zero so it is ok.Notice that the next case with the sign +,is written like this '+' which is equivalent to it's ASCII code,which is a non-negative integer.
2-The '\0' is the terminating NULL for strings.You can imagine it at the end of the list,which is flaged with a NULL.At strings we need to know where the string terminates ,so it is common to put the '\0' at the end of it.

[Pole]

1- switch checkes the value in every's case condition,so NUMBER is defined as zero so it is ok.Notice that the next case with the sign +,is written like this '+' which is equivalent to it's ASCII code,which is a non-negative integer.
2-The '\0' is the terminating NULL for strings.You can imagine it at the end of the list,which is flaged with a NULL.At strings we need to know where the string terminates ,so it is common to put the '\0' at the end of it.

1. So instead of NUMBER '0' there could be NUMBER '7' or NUMBER anything (in #define of course) ?
2. I know that we add null character at the end of strings, but why should I put it at the second place of an array even though there is no recorded char ? Am I right that while brackets are missing?

[jimblumberg]

Am I right that while brackets are missing?

I don't see any while statement that is missing required braces, however I myself would rewrite the following:

while (isdigit(s[++i] = c = getch()))
            ;
// OR
while (isdigit(s[i] = c = getch()))
   ++i;
// OR
while (isdigit(s[++i] = c = getch()))
{ /* Empty Body */ }

To me the third while is easier to see the empty body, but that is just my opinion. There is actually nothing syntactically wrong with the first while statement. Also I don't like using the pre-increment inside calculations or multiple statements.

Jim

[std10093]

1-Yes.If the type is equal to this defined NUMBER then it will insert this case
2-Not really.Let's see the code again

while ((s[0] = c = getch()) == ' ' || c == '\t')
        ;
    s[1] = '\0';

K&R uses this while style a lot,but it think that it makes the code less readable-it does it more short though-as in life (and in code) everything is a trade of
You can imagine it as if : the body of the loop(actually no body exsists) is included in the condition of the while.It says that if what is c (what is returned by getch()) is ' ' or tab then assign it to the first element of the array.Why does not this is written without iteration?Because getch() may fetch something that is neither a ' ' or a tab,so we want the getch to fetch something again.Then after we are sure that the first element of the array is filled(if not the code repeats the while and does not proceed to the next command),you terminate properly our array with the null terminator '\0'.

As for the format of this while notice that if the body of a statement or a iterative type(such as for,while,do-while) is only one line then the braces can be omitted,but it is ok if you use them because they state exactly which the body is.Especially for beginners i would recommend them to use braces always.
Then you can see a semicolon under the while(...).This is because every while needs a body.But everything that had to be done is already done in condition part of while,so the body does nothing,but we must enter the semicolon or the compiler will produce an error..If you have a question ask

[Pole]

It says that if what is c (what is returned by getch()) is ' ' or tab then assign it to the first element of the array.Why does not this is written without iteration?Because getch() may fetch something that is neither a ' ' or a tab,so we want the getch to fetch something again.Then after we are sure that the first element of the array is filled(if not the code repeats the while and does not proceed to the next command),you terminate properly our array with the null terminator '\0'.

Thanks for an in-depth answer. But what if eg. 5 is entered and getch processes it. Then according to code after 5 which would be saved in array[0], array[1]='\0' would be the next item saved there - which ends input. What if 567 is entered ? 5 would be array[0], 6 in array[1], 7 in array[2] and 6 from array[1] would be overwritten?
I understand why we add '\0' but in that particular case of that s[1]='\0' I don't get why it's in that place instead of counting every inputted key and putting '\0' at the end of it.

[AndiPersti]

I understand why we add '\0' but in that particular case of that s[1]='\0' I don't get why it's in that place instead of counting every inputted key and putting '\0' at the end of it.

s[1] = '\0' is only important if you don't enter a number (either a valid command like '+' or any other character). In the switch-statement in main() there is a default case where an error message is printed using the string s:

default:   
    printf("error: unknown command %s\n", s);
    break;

Of course you could also write this part in such a way that you print just the first character in the array like:

default:
    printf("error: unknown command %c\n", s[0]);  // or even: printf("error: unknown command %c\n", type);
    break;

but I think the reason why K&R have chosen to use a string is a cleaner function interface. Whenever the function returns, the caller can be sure that s will be a valid null-terminated string.

3. Why does getch function (/* get a (possibly pushed-back) character */), read character rejected by ungetch. (line 105)
I think that we don't need the rejected character (because it's EOF or sth(?) )

Consider the case, where there is no space between a number and the following operator:

123 456+

The first two calls to getch() will read in the numbers, but since they always have to read one character ahead to know when the number ends, you would loose the operator if you wouldn't put it back into the buffer.

Bye, Andreas

[Pole]

s[1] = '\0' is only important if you don't enter a number (either a valid command like '+' or any other character). In the switch-statement in main() there is a default case where an error message is printed using the string s:

default:   
    printf("error: unknown command %s\n", s);
    break;

Of course you could also write this part in such a way that you print just the first character in the array like:

default:
    printf("error: unknown command %c\n", s[0]);  // or even: printf("error: unknown command %c\n", type);
    break;

but I think the reason why K&R have chosen to use a string is a cleaner function interface. Whenever the function returns, the caller can be sure that s will be a valid null-terminated string.


Consider the case, where there is no space between a number and the following operator:

123 456+

The first two calls to getch() will read in the numbers, but since they always have to read one character ahead to know when the number ends, you would loose the operator if you wouldn't put it back into the buffer.

Bye, Andreas

Big thanks, now I understand every thing You had written about.
However I still wonder about that - "What if 567 is entered ? 5 would be array[0], 6 in array[1], 7 in array[2] and 6 from array[1] would be overwritten by '\0' ? "

[AndiPersti]

However I still wonder about that - "What if 567 is entered ? 5 would be array[0], 6 in array[1], 7 in array[2] and 6 from array[1] would be overwritten by '\0' ? "

Why should 6 be overwritten?
The line s[1] = '\0' is only executed after the first character was entered (in your case 5). If you continue to enter digits, the variable i (counter for the array index) is set to 0 (line 87) and the next character (in your case 6) is stored in s[++i] (line 89) == s[1]. With every new character, i is incremented and only the last character which was read too much is overwritten by '\0'. In your example, i would be 3 and thus s[3] = '\0' (line 94).

Bye, Andreas

[Pole]

Why should 6 be overwritten?
The line s[1] = '\0' is only executed after the first character was entered (in your case 5). If you continue to enter digits, the variable i (counter for the array index) is set to 0 (line 87) and the next character (in your case 6) is stored in s[++i] (line 89) == s[1]. With every new character, i is incremented and only the last character which was read too much is overwritten by '\0'. In your example, i would be 3 and thus s[3] = '\0' (line 94).

Bye, Andreas

So apparently it is the other way round (than I thought), 6 overwrites \0 which was previously there at s[1] created by line 84?

[AndiPersti]

So apparently it is the other way round (than I thought), 6 overwrites \0 which was previously there at s[1] created by line 84?

Correct.

[jwroblewski44]

I too have a question about this code.In particular:

if (isdigit(c)) /* collect integer part */........while (isdigit(s[++i] = c = getch()))................;

To me, it looks as if the index of string 's' is incremented before var 'c' is assigned. If the input was "5 5 +', and c equals 5 at the moment while var 'i' was just initialized to 0, wouldn't 'i' be incremented to 1 BEFORE c, or 5, was assigned to it. Obviously this is not the case because the code works fine (not to mention created by the actual creator's of the language). Could someone please describe what is happening, step-by-step, in line '89' of code posted by OP?P.S. Sorry for jumping in on your thread Pole!

[AndiPersti]

If the input was "5 5 +', and c equals 5 at the moment while var 'i' was just initialized to 0, wouldn't 'i' be incremented to 1 BEFORE c, or 5, was assigned to it. Obviously this is not the case because the code works fine (not to mention created by the actual creator's of the language). Could someone please describe what is happening, step-by-step, in line '89' of code posted by OP

I'm not quite sure what you mean.

If your input is "5 5 +" (spaces between each character) than s[0] = '5', s[1] = '\0' and c = '5' (the first '5') before line 89. There, getch() gets the next character (a space), this character is assigned to c and finally to s[1]. So s[0] is still '5' but s[1] is now ' '. Then isdigit() returns false and the while-loop ends. The next while loop is skipped and after line 94 s[1] is again '\0'.

After the first call to getop() you only get the first '5'. Does that answer your questions?

Bye, Andreas

[Pole]

If your input is "5 5 +" (spaces between each character) than s[0] = '5'

Yeah, but which line assigns '5' to s[0] ?

[Matticus]

while ((s[0] = c = getch()) == ' ' || c == '\t')