Thread: K & R Reverse Polish Calculator

Hope fully someone can help me with this one! I can't get my head around one crucial part. Here is the full code:

Code:

#include <stdio.h>
#include<stdlib.h>

#define MAXOP 100
#define NUMBER '0'

/* function prototypes */
int getop(char []);
void push(double);
double pop(void);

/* reverse Polish calculator */
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;
}

#include <ctype.h>

int getch(void);
void ungetch(int);

/* getop: get next character or numeric operand */
int getop(char s[]) /* we pass s[] to getop to store input */
{
	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;
/* getch: the function which actually gets chars! */
int getch(void) /* get a (possibly pushed-back) character */
{
	return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* push character back in input */
{
	if (bufp >= BUFSIZE)
		printf("ungetch: too many characters\n");
	else
		buf[bufp++] = c;
}

I have problems comprehending the whole getch ungetch section and as a result the getop function. In the book, it says the following:

"It is often the case that a program cannot determine that it has read enough input until it has read too much. One instance is collecting characters that make up a number: until the first non-digit is seen, the number is not complete. But then the program has read one character too far, a character that it is not prepared for."

"The problem would be solved if it were possible to "un-read" the unwanted character. Then, every time the program reads one character too many, it could push it back on the input so the rest of the code could behave as if it had never been read."

Apparently this is what getch and ungetch do. Can someone please explain with a simple example what exactly this pushing back is? i.e. an example of when it is useful/applicable and what it involves? I can't for the life of me get my head around it in the K & R example.

Cheers

BIOS

P.S Loving the new code display! Great improvement to the board! Makes code infinitely more readable. Kudos!

Apparently this is what getch and ungetch do. Can someone please explain with a simple example what exactly this pushing back is? i.e. an example of when it is useful/applicable and what it involves? I can't for the life of me get my head around it in the K & R example.

Think of the input stream (which is generally the stuff you're typing at the keyboard) as a long queue of characters. If you want to read 10 characters, you pluck them off of the input stream, one by one.

So you have a function that asks the user to enter a number, and he types this: 1234+

Until you start reading what he typed (using scanf(), getchar(), fgets(), or a similar function), you can't know what he entered. The easy thing to do is use getchar() to read a character. So you do that, and get back '1'. Keep doing this, and eventually you'll see an '+'.

Now, the user did nothing wrong, because your program told him to use '+' to add numbers together, so that's what he did. Your problem is that you have absolutely no idea how long the number he entered was. In this case, it's 4 digits, but it could have been 1, or 10, or anything. The crux of the matter is that you cannot know that the number is 4 digits until you read 5 digits. You know the number's done when you read a non-digit character.

Of course, here's the problem: now that you've read the '+', it's no longer available to be read. If you do nothing, the '+' "disappears". It would be as if the user never typed it. Ideally, the next time you call getchar() (or getch() in the case of this program), the '+' would still be there. That's the point of ungetch(): it puts the '+' back so it can be read by the next call to getch(). Now, the next time you call getch() you'll get that '+'. It's like you never accidentally read it in the first place. The '+' is pushed back onto the input stream (or, at least, it looks that way). That's what the pushing back is referring to.

Have you traced this by hand? You need to sit down, and go through every line on paper, and keep track of every variable at every step of the code. Yeah, it's a pain, and yeah, it uses a lot of paper, but being able to read through code is an absolute necessity as a programmer. Start by understanding your problem. Read through the following article: Reverse Polish notation - Wikipedia, the free encyclopedia.

I usually used (and reused) a single piece of paper for each function when I did this. I write down the parameters passed into the function and any input from the user at the top of the piece of paper. I then make boxes for each variable, so I can track their values at each point in the code. Basically, you are making yourself a human debugger, allowing yourself to step through each line of code and examine all relevant variables.

You should start with a paper for main, showing boxes for type, op2 and s. You don't need all 100 boxes for s, just 5 is sufficient for your example. The first thing that happens is getop is called, and passed s to store the first operator/operand. Take your "getop" paper, and make 5 boxes for s, and a box for i and c also. They're all uninitialized, so leave them empty. Now, start with the first while loop:

Code:

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

That calls getch, which returns the next character in the input. Since it's our first call, we get the first '2', and assign that to c and to s[0]. Fill in the appropriate boxes. A '2' is not a space or a tab, so we're done with our loop. The next thing to do is

Code:

s[1] = '\0';

so put a '\0' in the second box for s. Now, on to our if statements:

Code:

if (!isdigit(c) && c != '.')
    return c; /* not a number */

c is '2', so isdigit(c) will return true, and we skip the body of that if statement. Next:

Code:

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

Write a 0 in the box for i. c is a digit, so we go into this loop body, and again, get the next character from our input. It's a space. We now put a ' ' in the box for c, and in the box for s[++i]. i was 0, but it gets pre-incremented (the ++ comes before the i), so i becomes 1 (change the box for i), and we put a space in s[1], replacing the '\0'. A space is not a digit however, so the isdigit call fails, and our loop is over. Next check:

Code:

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

c is a space, not a '.', so skip this if statement. On we go:

Code:

s[i] = '\0';
if (c != EOF)
    ungetch(c);
return NUMBER;

i is 1, so make s[1] a '\0', replacing the space we just put in there. c is a space, not EOF, so we put it back by calling ungetch, and return NUMBER.
EDIT: Fixed backwards if statement in previous sentence.

Egads! That was quite a process for just one function. Unfortunately, you need to do this for all the functions that get called, until you finish the program (when you return from main). Fortunately, after doing a few on paper, it becomes fairly easy to do this in your head, and it goes much quicker, especially for small functions like getop().

So we finished our first call to getop(). That takes us back into main, and back to our "main" paper. Put NUMBER in the box for type, then evaluate the switch(type) statement. Keep on until you finish processing the entire input, print an answer and return from main.