Thread: Reverse Polish Calcullator

  1. #1
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193

    Question Reverse Polish Calcullator

    Good evening. I'm studying the reverse polish calculator of KnR but there are some lines I'm not understanding very well.

    Code:
    #include <stdio.h> 
    #include <stdlib.h>
    
    #ifndef MAXOP
      #define MAXOP 100
    #endif   
    
    #ifndef NUMBER
      #define NUMBER '0'
    #endif  
    
    int getop(char[]);
    void push(double);
    double pop(void);
    
    int main(void) 
    { 
      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 '-': 
            op2 = pop();
            push(pop() - op2);
            break;
         case '*': 
            push(pop() * pop());
            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
    
    int sp = 0; 
    double val[MAXVAL];
    
    void push(double f) 
    { 
      if(sp < MAXVAL) 
        val[sp++] = f;
      else
        printf("error: stack full, can't push %g\n", f);          
    }     
    
    double pop(void) 
    { 
       if(sp > 0) 
       { 
         return val[--sp];  
       }
       else  { 
         printf("error: stack empty\n");
         return 0.0;       
       }       
    }
    
    #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';
       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;   
    }
    
    #define BUFSIZE 100
    
    char buf[BUFSIZE]; /* buffer for ungetch */
    int bufp = 0; /* next free position in buf */     
    
    int getch(void)
    { 
      return (bufp > 0)? buf[--bufp] : getchar();    
    } 
    
    void ungetch(int c) 
    { 
       if(bufp >= BUFSIZE) 
         printf("Ungetch: too many characters\n");
       else 
         buf[bufp++] = c;      
    }

    this section

    Code:
     
    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()))
    Why did he insert the null terminator in s[1] ? to stop getting blanks ? after that, did he reset i to overwrite '\0' with an input ? (isdigit(s[++i]) ) ... if so, why did he insert the null terminator in the first place? I don't get it ...

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    This code in my eyes does the following (line by line)
    • Line 1 --> It will read a character.It will store this character to c.Then c will be stored in s[0].Then i will check if what was read was a space or a tab.If so read again and execute all the procedure again.In other words he 'eats' whitespaces and tabs by this way.
    • Line 2 --> An empty while body, because all work is done in line 1.
    • Line 3 --> Set s[1] to the null terminator, because no matter how many times the while loop is going to be executed we always will assign c to s[0]
    • Line 4 --> If c is not a digit AND it is not a dot, then go to line 5
    • Line 5 --> return c because it is not a number
    • Line 6 --> Assign to i the value of zero
    • Line 7 --> If c is a digit go to line 8
    • Line 8 --> First increment i by one.Then read a char, assign it to c, and then assign c to s[i].Check if s[i] is digit.If so the while loop will be executed



    Hmm.. I admit it is not clear why he sets s[1] to null terminator.But if you look the whole function, when on line 98 and 101 the if conditions are false, then this means that i still has value of zero,thus he will assign first element with null terminator ( it was read by the first while in the function ).But again i am not really convinced that s[1] = '\0' was mandatory...

    EDIT : Can you please provide me with the page of the book where this function lies to?
    Last edited by std10093; 11-19-2012 at 06:01 PM.

  3. #3
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    when on line 98 and 101 the if conditions are false
    But if the input isn't a digit, then c will be returned.

    by the away, congratulations for the 1000th post !!! [open champagne]

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Haha,yeah you are right....!! Thank you a lot. I hope it was a helpful one

    I see your point.. can you tell me the page ?

  5. #5
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    page 90 of the second edition.

  6. #6
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    have a good night people!

  7. #7
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    Code:
     
    Reading symbols from /home/ethereal/C/DataStructures/reversepolish...done.
    (gdb) break 101
    Breakpoint 1 at 0x4008fe: file reversepolish.c, line 101.
    (gdb) break 111
    Breakpoint 2 at 0x4009ba: file reversepolish.c, line 111.
    (gdb) break 114
    Breakpoint 3 at 0x4009d6: file reversepolish.c, line 114.
    (gdb) run
    Starting program: /home/ethereal/C/DataStructures/reversepolish 
    2.5 3.5 + 4.0 *
    
    Breakpoint 2, getop (s=0x7fffffffe640 "2.5 ") at reversepolish.c:111
    111        s[i] = '\0';
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "2.5") at reversepolish.c:114
    114        return NUMBER; 
    (gdb) cont
    Continuing.
    
    Breakpoint 2, getop (s=0x7fffffffe640 "3.5 ") at reversepolish.c:111
    111        s[i] = '\0';
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "3.5") at reversepolish.c:114
    114        return NUMBER; 
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "+") at reversepolish.c:101
    101          return c; /* not a number */
    (gdb) cont
    Continuing.
    
    Breakpoint 2, getop (s=0x7fffffffe640 "4.0 ") at reversepolish.c:111
    111        s[i] = '\0';
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "4.0") at reversepolish.c:114
    114        return NUMBER; 
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "*") at reversepolish.c:101
    101          return c; /* not a number */
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "\n") at reversepolish.c:101
    101          return c; /* not a number */
    (gdb) cont
    Continuing.
        24
    I think I understood the reason of assigning '\0' to s[1]. he's eliminating ' ' or '\t'. As you can see, Those don't appear inside s after the digits start to be input. My idea is strengthened by the fact the null terminator is overwritten with the first digit input.
    Almost in the same way, he overwrites the next char after the digit with '\0' (like the program did with ' '). That's the meaning of assigning '\0' to s[i].
    Last edited by thames; 11-20-2012 at 07:31 AM.

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Still i am not convinced.Which will the problem if we remove this line?

  9. #9
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    Still i am not convinced.Which will the problem if we remove this line?
    the problem, I don't know. But I noticed a difference in the last three breaks. There's a ".0" after some chars.

    without s[1] = '\0'

    Code:
     
    gdb -q reversepolish
    Reading symbols from /home/ethereal/C/DataStructures/reversepolish...done.
    (gdb) break 99
    Breakpoint 1 at 0x40086f: file reversepolish.c, line 99.
    (gdb) break 108
    Breakpoint 2 at 0x4008e5: file reversepolish.c, line 108.
    (gdb) break 111
    Breakpoint 3 at 0x400901: file reversepolish.c, line 111.
    (gdb) run
    Starting program: /home/ethereal/C/DataStructures/reversepolish 
    1.5 2.5 + 4.0 *
    
    Breakpoint 2, getop (s=0x7fffffffe640 "1.5 ") at reversepolish.c:108
    108       s[i] = '\0'; 
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "1.5") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont
    Continuing.
    
    Breakpoint 2, getop (s=0x7fffffffe640 "2.5 ") at reversepolish.c:108
    108       s[i] = '\0'; 
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "2.5") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont 
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "+.5") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont 
    Continuing.
    
    Breakpoint 2, getop (s=0x7fffffffe640 "4.0 ") at reversepolish.c:108
    108       s[i] = '\0'; 
    (gdb) cont 
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "4.0") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "*.0") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "\n.0") at reversepolish.c:99
    99        return c; /* not a number */
    with s[1] = '\0';

    Code:
     
    /home/ethereal/C/DataStructures/reversepolish 
    1.5 2.5 + 4.0 *
    
    Breakpoint 2, getop (s=0x7fffffffe640 "1.5 ") at reversepolish.c:108
    108       s[i] = '\0'; 
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "1.5") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont
    Continuing.
    
    Breakpoint 2, getop (s=0x7fffffffe640 "2.5 ") at reversepolish.c:108
    108       s[i] = '\0'; 
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "2.5") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "+") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont
    Continuing.
    
    Breakpoint 2, getop (s=0x7fffffffe640 "4.0 ") at reversepolish.c:108
    108       s[i] = '\0'; 
    (gdb) cont
    Continuing.
    
    Breakpoint 3, getop (s=0x7fffffffe640 "4.0") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "*") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont
    Continuing.
    
    Breakpoint 1, getop (s=0x7fffffffe640 "\n") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont
    Continuing.
        16

  10. #10
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Oh, now i see your point. Great observation.Bravo

  11. #11
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    Thank you for the compliment. But what does that ".0" mean? a kind of junk ?

  12. #12
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    When you encounter code such as this one, you can rewrite/refactor it to make it more readable:
    Code:
    /* getop: get next operator or numeric operand */
    int getop(char s[])
    {
       int i, c;
    
       do {
         c = getch();
       } while (c == ' ' || c == '\t');
    
       s[0] = c;
       s[1] = '\0';
    
       if(!isdigit(c) && c != '.')
         return c;
    
       i = 0;
    
       /* Integer part */
       if(isdigit(c))
         do {
             s[++i] = c;
             c = getch();
         } while (isdigit(c));
    
       /* Fractional part */
       if(c == '.')
         do {
           s[++i] = c;
           c = getch();
         } while (isdigit(c));
    
       s[i] = '\0';
    
       if(c != EOF)
         ungetch(c);
    
       return NUMBER;  
    }
    When the function is written this way, the intent becomes clear.

    On lines 6-8 the function reads the next character, skipping all spaces and tabs.

    On lines 10-11, the function constructs a string of that character into the char array specified by the caller.

    On lines 13-14, if the character was not a number, the function returns the character code. (The char array was filled with a string, to make other operations easier.)

    On lines 17-22, the function adds the integer part, if any, of a number into the character array.

    On lines 25-29, the function adds the fractional part, if any, starting with the decimal point, into the character array.

    On line 31, the function adds a NUL to the character array, so that the contents form a proper string. (The number just read.)

    The first character not part of the number is still in variable c. Therefore, on lines 33-34, if there really was a character (and not just end of input), that character is unread: put back into the stream. (This is internal to the C library, just something that makes parsing complicated stuff easier. It is not visible outside the process in any way, it is just part of the buffering mechanisms the C library does.)

    Compare the original function and my version side-by-side; perhaps the contrast will make it easier to decipher the intent behind the code?

    (I do take this approach when I see obtuse code. One must be extra careful to test that the rewritten code works exactly like the original. To my shame I admit I was too lazy to do that step here, so there may be bugs or typos in my version.)

  13. #13
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by thames View Post
    Thank you for the compliment. But what does that ".0" mean? a kind of junk ?
    Not really. This is what was left by previous call.

    I will use your own - beautiful - in my mind explanation ( which i really appreciate and thank you for that, because it really gave me the answer in a question i was thinking all the time in bed the last night. Thank you again .)

    See the following breakpoints
    Without the s[1] = '\0';

    Code:
    Breakpoint 3, getop (s=0x7fffffffe640 "2.5") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont 
    Continuing.
     
    Breakpoint 1, getop (s=0x7fffffffe640 "+.5") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont 
    Continuing.
    Now with the s[1] = '/0';
    Code:
    Breakpoint 3, getop (s=0x7fffffffe640 "2.5") at reversepolish.c:111
    111       return NUMBER;  
    (gdb) cont
    Continuing.
     
    Breakpoint 1, getop (s=0x7fffffffe640 "+") at reversepolish.c:99
    99        return c; /* not a number */
    (gdb) cont
    Continuing.
    So in the first call we have 2.5 inside s <- the parameter of getop.
    Then we get the plus operator ( + ) .
    If we remove line s[1] = '\0' (first piece of code) then we have in the buffer 2.5 , but then when we read the + operator, because it is only one element - one cell, only the first element of the buffer is going to be overwritten, while the the second (had the '.' from previous call) and third (had the '5' from previous call) elements will not be overwritten.

    As a result in the second call of getop we will have inside the buffer +.5

    Now ,with the line s[1]='\0'; we have in the first call of getop 2.5 inside the buffer and in the second call we have + inside the buffer , which is what we want

    Then in the last three breakpoints you have , you receive in the first call of the function 4.0 , thus buffer gets the 4.0 as content of it.Then you read * , but without the s[1]='\0' line you will get *.0 . The dot and the zero come from the 4.0 , because again only the first element of buffer (array s) will be overwritten.

    Can you understand what i am saying?

    Again thank for this beautiful question and your nice breakpoints

  14. #14
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193

    Talking

    (This is internal to the C library, just something that makes parsing complicated stuff easier. It is not visible outside the process in any way, it is just part of the buffering mechanisms the C library does.)
    actually, getch and ungetch were coded.

    If we remove line s[1] = '\0' (first piece of code) then we have in the buffer 2.5 , but then when we read the + operator, because it is only one element - one cell, only the first element of the buffer is going to be overwritten, while the the second (had the '.' from previous call) and third (had the '5' from previous call) elements will not be overwritten.
    Thank you. As clear as water!!! "many thanks high power. "

    edit:

    Nominal code was very enlightening. I couldn't picture the getch char was being assigned to c before assigning it to s[0]. To be honest, that simultaneous assigning confused me a bit.
    Last edited by thames; 11-20-2012 at 05:52 PM.

  15. #15
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by thames View Post
    actually, getch and ungetch were coded.
    True, but nomimal knows what he is talking about.If I remember well they were not yet introduced to you at the current point of the book

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reverse polish calculator
    By Tool in forum C Programming
    Replies: 3
    Last Post: 12-30-2009, 04:46 PM
  2. reverse polish calculator
    By Tool in forum C Programming
    Replies: 1
    Last Post: 12-24-2009, 05:25 PM
  3. Reverse Polish Notation
    By Lucid15 in forum C Programming
    Replies: 7
    Last Post: 02-16-2009, 10:05 PM
  4. c++ Reverse Polish Calculator Help
    By knight101 in forum C++ Programming
    Replies: 5
    Last Post: 11-12-2001, 09:31 AM
  5. Reverse Polish Notation???
    By Wizard_D in forum C Programming
    Replies: 6
    Last Post: 11-01-2001, 12:20 AM

Tags for this Thread