Like Tree6Likes

reverse polish notation calculator problems

This is a discussion on reverse polish notation calculator problems within the C Programming forums, part of the General Programming Boards category; Hello, I have several questions regarding the calculator presented in chapter 4.3 of K&R. 1. How can a switch command ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    39

    reverse polish notation calculator problems

    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:

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

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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 likes this.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    39
    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?

  4. #4
    Registered User
    Join Date
    May 2010
    Posts
    2,677
    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:
    Code:
    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
    Pole likes this.

  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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
    Code:
    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 likes this.

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    39
    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.

  7. #7
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Pole View Post
    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:
    Code:
    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:
    Code:
    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.

    Quote Originally Posted by Pole View Post
    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:
    Code:
    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 likes this.

  8. #8
    Registered User
    Join Date
    Nov 2011
    Posts
    39
    Quote Originally Posted by AndiPersti View Post
    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:
    Code:
    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:
    Code:
    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:
    Code:
    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' ? "

  9. #9
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Pole View Post
    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

  10. #10
    Registered User
    Join Date
    Nov 2011
    Posts
    39
    Quote Originally Posted by AndiPersti View Post
    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?

  11. #11
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Pole View Post
    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.
    Pole likes this.

  12. #12
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    287
    I too have a question about this code.In particular:
    Code:
    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!

  13. #13
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by jwroblewski44 View Post
    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 likes this.

  14. #14
    Registered User
    Join Date
    Nov 2011
    Posts
    39
    If your input is "5 5 +" (spaces between each character) than s[0] = '5'
    Yeah, but which line assigns '5' to s[0] ?

  15. #15
    Registered User
    Join Date
    Jun 2011
    Posts
    2,197
    Code:
    while ((s[0] = c = getch()) == ' ' || c == '\t')

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple Reverse Polish Notation Calculator
    By thegivingtree in forum C Programming
    Replies: 2
    Last Post: 09-21-2011, 12:25 AM
  2. simple calculator / reverse Polish notation
    By allan01123 in forum C Programming
    Replies: 7
    Last Post: 02-04-2011, 03:16 PM
  3. Reverse Polish Notation Calculator
    By jazzyqueen in forum C Programming
    Replies: 1
    Last Post: 09-02-2009, 03:55 AM
  4. Reverse Polish Notation
    By Lucid15 in forum C Programming
    Replies: 7
    Last Post: 02-16-2009, 09:05 PM
  5. Postfix (reverse polish notation) calculator
    By ottomated in forum C Programming
    Replies: 7
    Last Post: 05-06-2008, 05:32 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21