Jump to: navigation, search

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 4.03 on page 79

Given the basic framework, it's straightforward to extend the calculator. Add the modulus ( % ) operator and provisions for negative numbers.



Solution by Bob Wightman

In Bob's words:

"Here's my attempt

Adding the modulus is easily done by another case in main and using the fmod function. The standard library has been mentioned at this point so it should be valid to use this for type 0 compliance.

math.h should be added to the list of #includes for fmod."



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

int main(void)
{
    int type;
    double op2;
    char s[MAXOP];
    int flag = TRUE;

    while((type = Getop(s)) != EOF)
    {
        switch(type)
        {
           /* other cases snipped for brevity */
 
            case '%':
                op2 = pop();
                if(op2)
                    push(fmod(pop(), op2));
                else
                    printf("\nError: Division by zero!");
                break;
 
        }
    }
    return EXIT_SUCCESS;
}



Bob goes on to say: "Deal with unary minus when retrieving tokens. This is based on the fact that a unary minus will have no intervening space between it and its operand."



/* Getop: get next operator or numeric operand. */
int Getop(char s[])
{
    #define PERIOD  '.'
    int i = 0;
    int c;
    int next;

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

    /* Not a number but may contain a unary minus. */
    if(!isdigit(c) && c != PERIOD && c != '-')
        return c;               

    if(c == '-')
    {
        next = getch();
        if(!isdigit(next) && next != PERIOD)
        {
           return c;
        }
        c = next;
    }
    else
    {
        c = getch();
    }
 
    while(isdigit(s[++i] = c))
            c = getch();
    if(c == PERIOD)                     /* Collect fraction part. */
        while(isdigit(s[++i] = c = getch()))
                        ;
    s[i] = '\0';
    if(c != EOF)
        unGetch(c);
    return NUMBER;
}

Solution by Xggggg

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 '*':
			push(pop() * pop());
			break;
		case '-':
			op2 = pop();
			push(pop() - op2);
			break;
		case '/':
			if ((op2 = pop()) != 0.0)
				push(pop() / op2);
			else
				printf("error: zero divisor\n");
			break;
		case '%':
			if ((op2 = pop()) != 0.0)
				push(fmod(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;
}

int getop(char s[])
{
	int i = 0, c, k;
	while ((s[0] = c = getch()) == ' ' || c == '\t');
	s[1] = '\0';
	if (isdigit(c) || c == '.' || ((c == '-' || c == '+') && (isdigit(k = getchar()) || k == '.')))
	{
		if (c == '-' || c == '+')
			s[++i] = c = k;
		if (isdigit(c))
			while (isdigit(s[++i] = c = getch()));
		if (c == '.')
			while (isdigit(s[++i] = c = getch()));
		s[i] = '\0';
		if (c != EOF)
			ungetch(c);
		c = NUMBER;
	}
	if (c == '-' || c == '+')
		ungetch(k);
	return c;
}

Solution by menonsahab

//I've added a viewstack() function that let's you see the values in the stack after every iteration.
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

#define MAXOP 100
#define NUMBER 0
#define MAXVAL 100
#define BUFSIZE 100

int getop(char *);
void push(double);
double pop(void);
int getch(void);
void ungetch(int);
void viewstack(void);

int bufp = 0;
char buf[BUFSIZE];
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");
		exit(1);
		//return 0.0;
	}
}

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

int getop(char *s)
{
	int i, c, d;
	while((s[0] = c = getch()) == ' ' || c == '\t');
	s[1] = '\0';
	if(!isdigit(c) && c != '.' && c != '-')
		return c;
	if(c == '-')
	{
		d = getch();
		if(d == ' ')
			return c;
		else
			ungetch(d);
	}
	i = 0;
	if(isdigit(c) || c == '-')
		while(isdigit(s[++i] = c = getch()));
	if(c == '.')
		while(isdigit(s[++i] = c = getch()));
	s[i] = '\0';
	if(c != EOF)
		ungetch(c);
	return NUMBER;
}

void viewstack(void)
{
	int i;
	printf("\nstack:\n");
	for(i = sp - 1; i >= 0; i--)
		printf("%lf\n", val[i]);
}

int main()
{
	int type;
	double op2;
	char s[MAXOP];

	while((type = getop(s)) != EOF)
	{
		//viewstack();  Use this function if you wish to see the stack after every iteration
		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 '%':
				op2 = pop();
				if(op2 != 0.0)
					push(fmod(pop(), op2));
				else
					printf("error: division by zero\n");
				break;
			case '\n':
				printf("\t%.8g\n", pop());
				break;
			default:
				printf("error: unknown command %s\n", s);
				break;
		}
	}
	return 0;
}

Solution by Luke Panayi

My take on minus compatibility. I'm uncertain if it's as clean as the alternatives or not, but it is an alternative.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#define MAXOP 100
#define NUMBER '0'
#define MAXVAL 100
#define BUFSIZE 100


int getop(char []);
void push(double);
double pop(void);
int getch(void);
void ungetch(int);

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

int getop(char s[])	{
	int i, c;

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

	if (!isdigit(c) && c != '.' && c != '-')
		return c;
	i = 0;

	if (c == '-') 	{
		s[i] = c;
		if (!isdigit(c = getch()))	{
			return '-';
		}
		else
			s[++i] = c;
	}
	if (isdigit(c))
		while (isdigit(s[++i] = c = getch()));
	if (c == '.')
		while (isdigit(s[++i] = c = getch()));

	s[i] = '\0';
	printf("%s\n", s);
	if (c != EOF)
		ungetch(c);
	return NUMBER;
}

char buf[BUFSIZE];
int bufp = 0;

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

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 '/':
				if (op2 != 0.0)	{
					op2 = pop();
					push(pop() / op2);
				}
				else
					printf("error: zero divisor\n");
				break;
			case '%':
				op2 = pop();
				if (op2 != 0.0)	{
					push(fmod(pop(), op2));
				}
				else
					printf("error: zero divisor\n");
				break;
			case '\n':
				printf("\t%.8g\n", pop());
				break;
		}
	}
	return 0;
}

Solution by anonymous

Like most, I utilized fmod to get the modulus since the data type for both numbers are doubles and the modulo operator only supports ints. I choose to modify getop to store a '-' if first char found and, if any digits are found after it, to store them as well. I had to check to see if only '-' was added to s at the end of the function, but it's simple and required little modification from the original program.

I also added many comments explaining what the code from the book since it took me a while to understand it all. Furthermore, since my '%' case code is essentially the same as everyone else's, I will just highlight the getop differences.

// original: return c if it is not a digit or period
if (!isdigit(c) && c != '.')
     return c;

// mine: this prevents an immediate return if a - is found. Returns if not a digit, period, or minus symbol
if (!isdigit(c) && c != '.' && c != '-')
     return c;

// original: only continue if c is a digit (c at this point is the first digit or period found)
if (isdigit(c))
    while (isdigit(s[++i] = c = getch()))
        ;

// mine: only continue if c is a digit or a minus symbol (c at this point is the first digit, period, or minus symbol found)
if (c == '-' || isdigit(c))
    while (isdigit(s[++i] = c = getch()))
        ;

// original: return number signal after storing the last non-EOF char read in the getch buffer
if (c != EOF)
    ungetch(c);
return NUMBER;

// mine: after the getch buffer is updated, check to see if the only char read was a - since i[0] == '-' and i == 1 which means i[1] == '\0' since it never reached any s[++i] = c parts of the code
if (c != EOF)
    ungetch(c);
if (i == 1 && s[0] == '-')
    return '-';
return NUMBER;

Here is the entire program

#include <stdio.h>
#include <stdlib.h> // for atof()
#include <ctype.h>
#include <math.h>

/*
    Exercise 4-3. Given the basic framework, it's straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers.
*/

#define MAXOP 100   // max size of operand or operator
#define NUMBER '0'  // signal that a number was found
#define MAXVAL 100  // maximum depth of val stack
#define BUFSIZE 100 

int sp = 0;         // next free stack position
double val[MAXVAL]; // value stack
char buf[BUFSIZE];  // buffer for ungetch
int bufp = 0;       // next free position in buf

int getop(char s[]);
void push(double f);
double pop(void);
int getch(void);
void ungetch(int c);

// reverse Polish calculator
// note: convert ((((-1 - 2) * (4 + -5)) / -3) % 5) * (-1 - -10) to -1 2 - 4 -5 + * -3 / 5 % -1 -10 - * for reverse Polish notation. -1 2 - 4 -5 + * -3 / 5 % -1 -10 - * == -9
int main()
{
    int type;
    double op2;
    char s[MAXOP];

    while ((type = getop(s)) != EOF)
    {
        switch (type)
        {
        case NUMBER:
            push(atof(s)); // convert the string to type double and push it on the stack
            break;
        case '+':
            push(pop() + pop()); // pop last two digits to sum them and push the result on the stack
            break;
        case '*':
            push(pop() * pop()); // pop last two digits to multiply them and push the result on the stack
            break;
        case '-':
            /*
                Because + and * are commutative operators, the order in which the popped operands are combined is irrelevant, but for - and / the left and right operands
                must be distinguished. In push(pop() - pop());, the order in which the two calls of pop are evaluated is not defined. To guarantee the right order, it is
                necessary to pop the first value into a temporary variable. Hence op2 = pop() in - and / but not in + and *
            */
            op2 = pop();
            push(pop() - op2); // pop last two digits to subtract them in the correct order and push the result on the stack
            break;
        case '/':
            op2 = pop();
            if (op2 != 0.0)
                push(pop() / op2); // pop last two digits to divide them in the correct order and push the result on the stack
            else
                printf("error: zero divisor\n");
            break;
        case '%':
            op2 = pop();
            if (op2 != 0.0)
                push(fmod(pop(), op2)); // pop last two digits in the correct order to find the modulus and push the result on the stack
            else
                printf("error: zero divisor\n");
            break;
        case '\n':
            printf("\t%.8g\n", pop()); // get the final result
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
    }
    return 0;
}

// push: push f onto value stack
void push(double f)
{
    if (sp < MAXVAL) // if value stack still has space, add f
        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) // if the next free stack position is greater than zero, return the highest level item from stack
        return val[--sp];
    else
    {
        printf("error: stack empty\n");
        return 0.0;
    }
}

// getop: get next operator or numeric operand
int getop(char s[])
{
    int i, c;

    while ((s[0] = c = getch()) == ' ' || c == '\t') // skip white space
        ;
    s[1] = '\0'; // terminate string in case input is not a number (s is expected to be a string throughout program)
    if (!isdigit(c) && c != '.' && c != '-')
        return c; // not a number. Probably an operator, so return it. Minus operator is a special case and is handled right before return NUMBER;
    i = 0;
    if (c == '-' || isdigit(c)) // collect integer(s), if any, after first digit found or after minus symbol found
        while (isdigit(s[++i] = c = getch()))
            ;
    if (c == '.') // collect fraction part if period is found
        while (isdigit(s[++i] = c = getch()))
            ;
    s[i] = '\0'; // terminate string after digits were captured
    if (c != EOF) 
        ungetch(c); // since we read to far, push the last read char back on the getch buffer. This buffer is read first before getting the next char from input
    if (i == 1 && s[0] == '-') // if s[0] == '-' && s[1] == '\0', return minus operator
        return '-';
    return NUMBER;
}

// get a (possibly pushed back) character
// checks to see if there are any chars in buffer. If there are, get those and return it. If not, call getchar() from stdio.h to get next char from input
int getch(void)
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

// push character back on input
// if bufp is less than BUFSIZE, there is room to store more chars to be read by getch next and it stores c and updates the index for it
void ungetch(int c)
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}
Personal tools