K&R2 solutions:Chapter 4:Exercise 4 - clc-wiki

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

Add commands to print the top element of the stack without popping, to duplicate it, and to swap the top two elements. Add a command to clear the stack.

Contents

1 Solution by Bob Wightman

2 Solution by Pilcrow

3 Solution by menonsahab

4 Solution by dasaphro

5 Solution by anonymous

Solution by Bob Wightman

Mr Wightman's solution has a bug. It can be seen by using the command '?'. After entering '?' the result (printing the top item without popping) is delayed until the ENTER key is pressed, which causes a newline ('\n'), which, in turn, causes the top item to be popped and printed. This defeats the intent of the '?' command. The other stack-manipulation commands have the same, or similar problems.
This situation is encountered in most operating systems. This is so that line editing can be done prior to submitting the line.
--- Pilcrow 03:11, 22 September 2011 (UTC)

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

#define MAXOP 100
#define NUMBER  0
#define TRUE 1
#define FALSE 0

/* This programme is a basic calculator.

Extra cases have been added to:
1. Show the top item of the stack without permanently popping it.
2. Swap the top two items on the stack.
3. Duplicate the top item on the stack.
4. Clear the stack.

I have used functions for each of the new cases rather than have the
code inline in order to limit the physical size of the switch block.

In anticipation of the following exercise the following characters have
been used for the operations (in the same order as above): ? ~ # !
rather than use alphabetic characters.

It is actually rather difficult to be original in this exercise.

This is exercise 4-4 from Kernighan & Ritchie, page 79.

 */

int Getop(char s[]);
void push(double val);
double pop(void);
void showTop(void);
void duplicate(void);
void swapItems(void);
void clearStack();

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

    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)
                    push(pop() / op2);
                else
                    printf("\nError: division by zero!");
                break;
            case '%':
                op2 = pop();
                if(op2)
                    push(fmod(pop(), op2));
                else
                    printf("\nError: division by zero!");
                break;
            case '?':
                showTop();
                break;
            case '#':
                duplicate();
                break;
            case '~':
                swapItems();
                break;
            case '!':
                clearStack();
            case '\n':
                printf("\n\t%.8g\n", pop());
                break;
            default:
                printf("\nError: unknown command %s.\n", s);
                break;
        }
    }
    return EXIT_SUCCESS;
}

#define MAXVAL 100

int sp = 0;          /* Next free stack position. */
double val[MAXVAL];  /* value stack. */

/* push: push f onto stack. */
void push(double f)
{
    if(sp < MAXVAL)
        val[sp++] = f;
    else
         printf("\nError: 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("\nError: stack empty\n");
        return 0.0;
    }
}

void showTop(void)
{
    if(sp > 0)
        printf("Top of stack contains: %8g\n", val[sp-1]);
    else
        printf("The stack is empty!\n");
}


void duplicate(void)
{
    double temp = pop();

    push(temp);
    push(temp);
}

void swapItems(void)
{
    double item1 = pop();
    double item2 = pop();

    push(item1);
    push(item2);
}

/* pop only returns a value if sp is greater than zero. So setting the
stack pointer to zero will cause pop to return its error */

void clearStack(void)
{
    sp = 0;
}

int getch(void);
void unGetch(int);

/* Getop: get next operator or numeric operand. */
int Getop(char s[])
{
    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 != '.' && c != '-')
        return c;               

    if(c == '-')
    {
        next = getch();
        if(!isdigit(next) && next != '.')
        {
           return c;
        }
        c = next;
    }
    else
        c = getch();
 
    while(isdigit(s[++i] = c))
            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];
int bufp = 0;

/* Getch: get a ( possibly pushed back) character. */
int getch(void)
{
     return (bufp > 0) ? buf[--bufp]: getchar();
}

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

Solution by Pilcrow

In anticipation of the requirements of exercises 4-5 & 4-6 I have followed Mr Wightman's example by assigning the characters @ ? # ~ ! to various stack operations, rather than using letters.

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


#define MAXOP 100
#define NUMBER '0'

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

int nopprint = 0;                       /* don't pop & print on ENTER after stack operations */
double op2, op3;

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

    while((type = getop(s)) != EOF) {
        switch (type) {
            case NUMBER:
                push (atof(s));
                break;
            case '@': case '?': case '#': case '~': case '!':       /* stack operations */
                stakop(type);
                break;
            case '_':                       /* unary minus (underscore) negates previous number */
                push( 0.0 - pop());
                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 '%':                       /* floating modulo operator, not integer */
                op2 = pop();
                if(op2 != 0.0) push(fmod(pop(),op2));
                else printf("error: zero divisor\n");
                break;
            case '\n':
                if(!nopprint)
                    printf("\t%.8g\n",pop());
                nopprint = 0;
                break;
            default:
                printf("error: unknown command %s\n", s);
                break;
        }
    }
    return 1;
}

#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);
    return;
}

double pop(void)
{
    if (sp > 0) return val[--sp];
    else {
        printf("stack empty\n");
        return 0.0;
    }
}

#include <ctype.h>

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

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

    while((s[0] = c = getch()) == ' ' || c == '\t') ;       /* skip leading spaces or tabs */
    s[1] = '\0';
    if (!isdigit(c) && c != '.') return c;                  /* was operator */
    i = 0;                                                  /* was digit    */

    if(isdigit(c)) {
        type = NUMBER;
        while(isdigit(s[++i] = c = getch())) ;              /* get digits   */
    }
    if(c == '.') {
        type = NUMBER;
        while(isdigit(s[++i] = c = getch())) ;              /* and dec pt   */
    }

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

#define BUFSIZE 100

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

void stakop(int op)
{
    int i;
    nopprint = 1;                       /* disable pop & print on '\n' */

    switch(op) {
        case '@':                       /* show whole stack (not required by K&R)*/
            if(sp) {
                putchar('\n');
                for(i = sp - 1 ; i >= 0; i--)   /* last in, first shown */
                    printf("*** %.8g\n",val[i]);
            }
            else printf("stack empty\n");
            return;
        case '?':                       /* print top item */
            if(sp) {
                putchar('\n');
                push(op2=pop());
                printf("*** %.8g\n",op2);
            }
            else printf("stack empty\n");
            return;
        case '#':                       /* dup top item */
            push(op2=pop());
            push(op2);
            return;
        case '~':                       /* swap top 2 items */
            op2 = pop();
            op3 = pop();
            push(op2);
            push(op3);
            return;
        case '!':                       /* clear stack */
            nopprint = 0;
            sp = 0;
            return;
        default:                        /* should only get here if there's a bug */
            printf("error: unknown command %s\n",op);
            return;
    }
}

Solution by menonsahab

/* There is one bug in the previous solutions. In the function used to 
duplicate the top element, people are not checking whether there is sufficient 
space for another element to be inserted in the stack. I've made the necessary changes.*/

#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);
void showTop(void);
void swap(void);
void duplicate(void);
void clearStack(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]);
}

void showTop(void)
{
	sp > 0 ? printf("\t%.8g\n", val[sp-1]) : printf("stack is empty\n");
}

void swap(void)
{
	double temp;
	if(sp < 1)
		printf("error: stack has less than 2 elements, can't swap\n");
	else
	{
		temp = val[sp - 1];
		val[sp - 1] = val[sp - 2];
		val[sp - 2] = temp; 
	}
}

void duplicate(void)
{
	if(sp > MAXVAL - 1)
		printf("error: stack is full, can't duplicate\n");
	else
	{
		double temp = pop();
		push(temp);
		push(temp);
		++sp;
	}
}

void clearStack(void)
{
	sp = 0;
}

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 '?': // show top item on stack without popping
				showTop();
				break;
			case '~': // swap top two elements of the stack
				swap();
				break;
			case '#': // duplicate the top element
				duplicate();
				break;
			case '!': // clearStack
				clearStack();
				break;
			case '\n':
				printf("\t%.8g\n", pop());
				break;
			default:
				printf("error: unknown command %s\n", s);
				break;
		}
	}
	return 0;
}

Solution by dasaphro

menonsahab's code still has a few problems. The special commands, when followed by newline, do not produce the desired output; the viewstack function is not used; and duplicate needlessly increments sp (this is already done by push). The following do the trick.

/* There is one bug in the previous solutions. In the function used to 
   duplicate the top element, people are not checking whether there is sufficient 
   space for another element to be inserted in the stack. I've made the necessary changes.*/

#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 view_stack(void);
void show_top(void);
void swap(void);
void duplicate(void);
void clear_stack(void);

int bufp = 0;
char buf[BUFSIZE];
int sp = 0;
double val[MAXVAL];


int main()
{
    int type, ignore_newline = 0;
    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 '%':
	    op2 = pop();
	    if(op2 != 0.0)
		push(fmod(pop(), op2));
	    else
		printf("error: modulo zero\n");
	    break;
	case '?': // show top item on stack without popping
	    show_top();
	    ignore_newline = 1;
	    break;
	case '~': // swap top two elements of the stack
	    swap();
	    ignore_newline = 1;
	    break;
	case '#': // duplicate the top element
	    duplicate();
	    ignore_newline = 1;
	    break;
	case '!': // clear_stack
	    clear_stack();
	    ignore_newline = 1;
	    break;
	case '$':
	    view_stack();
	    ignore_newline = 1;
	    break;
	case '\n':
	    if (ignore_newline) {
		ignore_newline = 0;
	    }
	    else {
		printf("\t%.8g\n", pop());
	    }
	    break;
	default:
	    printf("error: unknown command %s\n", s);
	    break;
	}
    }
    return 0;
}

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 is empty\n");
	return 0.0;
    }
}

int getch(void)
{
    if (bufp > 0) {
	return buf[--bufp];
    }
    else {
	return 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 view_stack(void)
{
    int i;
    printf("\nstack:\n");
    for(i = sp - 1; i >= 0; i--) {
	printf("%lf\n", val[i]);
    }
}

void show_top(void)
{
    if (sp > 0) {
	printf("\t%.8g\n", val[sp-1]);
    }
    else {
	printf("error: stack is empty\n");
    }
	    
}

void swap(void)
{
    double temp;
    if(sp < 1)
	printf("error: stack has less than 2 elements, can't swap\n");
    else
    {
	temp = val[sp - 1];
	val[sp - 1] = val[sp - 2];
	val[sp - 2] = temp; 
    }
}

void duplicate(void)
{
    if(sp > MAXVAL - 1)
	printf("error: stack is full, can't duplicate\n");
    else
    {
	double temp = pop();
	push(temp);
	push(temp);
    }
}

void clear_stack(void)
{
    sp = 0;
}

Solution by anonymous

dasaphro's code has a small mistake of checking if sp < 1 before performing a swap. sp is similar to a 1 based index since it points to the next free stack position. If sp == 1, the next free stack position is s[1]. This is confirmed by looking at the push function, where the sp value is used before incrementing.

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

/*
    Exercise 4-4. Add commands to print the top element of the stack without popping, to duplicate it, and to swap the top two elements. Add a command to clear the stack.
*/

#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 

enum boolean {FALSE, TRUE};

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);
void printTop(void);
void duplicateTop(void);
void swapTopTwo(void);
void clearStack(void);

// 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];
    char skipNextNewline = FALSE;

    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 '?':
            printTop();
            skipNextNewline = TRUE;
            break;
        case '#':
            duplicateTop();
            skipNextNewline = TRUE;
            break;
        case '~':
            swapTopTwo();
            skipNextNewline = TRUE;
            break;
        case '!':
            clearStack();
            skipNextNewline = TRUE;
            break;
        case '\n':
            if (skipNextNewline)
                skipNextNewline = FALSE;
            else
                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;
}

// prints the top element in the value stack
void printTop(void)
{
    if (sp > 0)
        printf("\t%.8g\n", val[sp - 1]);
    else
        printf("error: stack empty\n");
}

void duplicateTop(void)
{
    if (sp < MAXVAL) // only need to see if there is space for one more
        push(val[sp - 1]); // duplicates top item
    else
        printf("error: stack full, can't duplicate top element\n");
}

void swapTopTwo(void)
{   // if sp == 2, there are at least two elements stored
    if (sp > 1)
    {                               // <third> <second> <first>
        double first = pop();       // <third> <second>
        double second = pop();      // <third>
        push(first);                // <third> <first>
        push(second);               // <third> <first> <second>
    }
    else
        printf("error: can't swap top two, not enough elements\n");
}

// sets next free stack position to zero (meaning the value stack is empty).
// all of the original values are still there, but they will no longer be accessible by the current functions and they will be overwritten when new elements are stored
void clearStack(void)
{
    sp = 0; 
}

From clc-wiki

Contents

Solution by Bob Wightman

Solution by Pilcrow

Solution by menonsahab

Solution by dasaphro

Solution by anonymous

Views

Personal tools

Site_logo

Search

Content_hierarchy

Tools