KR2 Exercise 5-10 - clc-wiki

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 5.10 on page 118

Write the program expr , which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,
expr 2 3 4 + *
evaluates 2 X (3 + 4).

Contents

1 Solution by Lars Wirzenius

2 Solution by Alex Hoang (Category 0)

3 Solution by menonsahab

4 Solution by i9383

5 Solution by anonymous

6 Solution by Foowar

Solution by Lars Wirzenius

Note: Lars uses EXIT_FAILURE on error. As far as I can tell, this is the only thing which makes this a Category 1, rather than Category 0, solution.

/*
 * Solution to exercise 5-10 in K&R2:
 *
 *	Write the program expr, which evaluates a reverse Polish expression
 *	from the command line, where each operator or operand is a separate 
 *	argument. For example,
 *
 *		expr 2 3 4 + *
 *
 *	evaluates 2*(3+4).
 *
 * This is very similar to the program in 4.3 (and should ideally have been
 * a modification of that).
 *
 * Feel free to modify and copy freely.
 *
 * Lars Wirzenius <liw@iki.fi>
 */

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

#define STACK_SIZE 1024

double stack[STACK_SIZE];
int stack_height = 0;

void panic(const char *msg) {
	fprintf(stderr, "%s\n", msg);
	exit(EXIT_FAILURE);
}

void push(double value) {
	if (stack_height == STACK_SIZE)
		panic("stack is too high!");
	stack[stack_height] = value;
	++stack_height;
}

double pop(void) {
	if (stack_height == 0)
		panic("stack is empty!");
	return stack[--stack_height];
}

int main(int argc, char **argv) {
	int i;
	double value;
	
	for (i = 1; i < argc; ++i) {
		switch (argv[i][0]) {
		case '\0':
			panic("empty command line argument");
			break;
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			push(atof(argv[i]));
			break;
		case '+':
			push(pop() + pop());
			break;
		case '-':
			value = pop();
			push(pop() - value);
			break;
		case '*':
			push(pop() * pop());
			break;
		case '/':
			value = pop();
			push(pop() / value);
			break;
		default:
			panic("unknown operator");
			break;
		}
	}

	printf("%g\n", pop());
	return 0;
}

Solution by Alex Hoang (Category 0)

/* Allows for leading plus/minus as well as decimal numbers */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define NUMBER 0

void push(double f);

double pop(void);


main(int argc, char *argv[])
{
    int type;
    int c;
    double op1, op2, latest;
    while (--argc > 0)
    {
        *++argv;
        if (!isdigit(c = **argv) && strlen(*argv) == 1)
            type = c;
        else
            type = NUMBER;
        switch (type)
        {
            case NUMBER:
                push(atof(*argv));
                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: zero divisor\n");
                break;
            case '^':
                op2 = pop();
                op1 = pop();
                if (op1 == 0.0 && op2 <= 0)
                    printf("if x = 0.0, y must be greater than 0\n");
                else
                    push(pow(op1, op2));
                break;
            case 'e':
                push(exp(pop()));
                break;
            case '~':
                push(sin(pop()));
                break;
            default:
                printf("error: unknown command: %c\n", type);
                break;
        }
    }
    latest = pop();
    printf("\t%.8g\n", latest);
    return 0;
}

#define MAXVAL 100

int sp = 0;
double val[MAXVAL];
/* maximum depth of val stack */
/* next free stack position */
/* 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;
    }
}

Solution by menonsahab

(Note for Menonsahab and readers: The reason that * is causing issues is that it is a shell wildcard. You are calling the program from your shell and the argument is passing to the shell first, which expands it into a list of all files in the current folder. If you use the escape sequence \* instead of * as an argument while calling your c program, you should get the expected result.). However, if you escape the asterisk and you are still having problems, it could be that you are using MinGW's version of gcc. See anonymous' solution to that problem.

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

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

int main(int argc, char *argv[])
{
	int i, c, op2;
	char *p;
	for(i = 1; i < argc; i++)
	{
		p = argv[i];
		printf("argv[%d] = %s\n", i, argv[i]);
		while(*p && isdigit(*p))
			p++;
		printf("*p = %d, %c\n", *p, *p);
		switch(*p)
		{
			case '\0':
				push(atoi(argv[i]));
				break;
			case '+':
				push(pop() + pop());
				break;
			case '-':
				op2 = pop();
				push(pop() - op2);
				break;
			case 'x':
				push(pop() * pop());
				break;
			case '/':
				op2 = pop();
				if(op2 != 0.0)
					push(pop() / op2);
				else
					printf("error: zero divisor\n");
				break;
		}
	}
	printf("Final result = %lf\n", pop());
	return 0;
}

/*
I noticed that the program was giving weird results when I was 
using the multiplication symbol '*' as a command line input.
I couldn't figure out why that was happening so now I'm just 
using the 'x' symbol to denote multiplication.
I even ran the other two solutions on this page but to no avail.
*/

/*
On running:
expr 2 3 4 + x
the output is:
Final result = 14.000000
*/

Solution by i9383

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

#define MAXVAL	100

main(int argc, char *argv[])
{
	double d[MAXVAL];
	double *pd = d;

	while (--argc) {
		if (isdigit(**++argv))
			*pd++ = atof(*argv);
		else if (*argv[0] == '-') {
			pd -= 2;
			*pd = *pd - *(pd+1);
			++pd;
		}
		else if (*argv[0] == '/') {
			pd -= 2;
			*pd = *pd / *(pd+1);
			++pd;
		}
		else if (*argv[0] == '*') {
			pd -= 2;
			*pd = *pd * *(pd+1);
			++pd;
		}
		else if (*argv[0] == '+') {
			pd -= 2;
			*pd = *pd + *(pd+1);
			++pd;
		}
		else
			argc = 1;
	}
	printf("%f\n", *--pd);
	return 0;
}

Solution by anonymous

I took the reverse Polish calculator program from pages 76-79 and adapted it to use command line arguments instead of relying on getch() and ungetch(). I originally had the program from exercise 4.10 working, but I figured someone could add that functionality back since I kept this solution similar to the book's version of the calculator. Plus, it is 150 lines shorter.

During the conversion I ran into an annoying issue when an asterisk (*) was given as a command line argument in Windows. It turns out that the MinGW version of gcc adds in globbing for command line arguments by default and it cannot be escaped. This is because a program compiled by it will take an asterisk and expand it inside of the program. Fortunately, this annoying documentation-lacking feature is easily disabled by setting _CRT_glob to 0. Afterwards, everything worked as expected.

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

/*
    Exercise 5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument.
    For example, expr 2 3 4 + * evaluates 2 x (3 + 4).
*/

extern int _CRT_glob = 0;    // disables MinGW globbing that is added to this program. Source: https://willus.org/mingw/_globbing.shtml

#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 MAXLINE 1000 // buffer size for line

int sp = 0;                  // next free stack position
double val[MAXVAL];          // value stack
char line[MAXLINE] = {'\0'}; // buffer for getline. Set all values to zero from the start for logic below
int linep = 0;               // current position in line buffer

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

// reverse Polish calculator
int main(int argc, char *argv[])
{
    int type, c, i = 0;
    double op2;
    char s[MAXOP];

    if (argc < 2) // if no arguments were given, print usage and exit
    {
        printf("Usage: expr <reverse Polish expression>\n");
        return -1;
    }
    while (--argc > 0) // while there are arguments left, add them to the line char array
    {
        argv++; // This prevents the first argument from being processed and moves to next argument on each iteration
        while ((c = *(*argv)++)) // gets each character in the argument until it reaches '\0'
            line[i++] = c;
        line[i++] = ' '; // space delimit the arguments for the getop function
    }
    line[i++] = '\n'; // since the switch below expects a newline character to print the data, add it at the end
    line[i] = '\0'; // then terminate the string

    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 '-':
            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 '\n':
            printf("%.8g\n", pop()); // print the final result
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
    }
    return 0;
}

// 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 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. Update the pointer to point to the item below it
        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 = 0, c;
    if (line[linep] == '\0') // if at end of line return EOF to terminate the loop in main
        return EOF;
    while ((s[0] = c = line[linep++]) == ' ' || 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 != '.')
        return c; // not a number. Probably an operator, so return it.
    if (isdigit(c)) // collect integer(s), if any, after first digit found
        while (isdigit(s[++i] = c = line[linep++]))
            ;
    if (c == '.') // collect fraction part if period is found
        while (isdigit(s[++i] = c = line[linep++]))
            ;
    s[i] = '\0'; // terminate string after digits were captured
    if (c != EOF)
        linep--; // since we read too far, move the line position back one
    return NUMBER;
}

Solution by Foowar

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

#define MAX_STACK 1000

double stack[MAX_STACK];
int top = 0;

double
pop() {
	return stack[--top];
}

void
push(double x) {
	stack[top++] = x;
}

int
main(int argc, char **argv)
{
	while (*++argv) {
		double op2;

		if ((*argv)[1] != 0) {
			/* can't be an operator, therefore it is a number */
			push(atof(*argv));
			continue;
		}

		switch (**argv) {
			case '+':
				push(pop() + pop());
				break;
			case '*':
				push(pop() * pop());
				break;
			case '-':
				op2 = pop();
				push(pop() - op2);
				break;
			case '/':
				op2 = pop();
				push(pop() / op2);
				break;
			default:
				push(atof(*argv));
				break;
		}
	}

	if (top != 1) {
		printf("bad input\n");
		return 1;
	}

	printf("%f\n", pop());

	return 0;
}

From clc-wiki

Contents

Solution by Lars Wirzenius

Solution by Alex Hoang (Category 0)

Solution by menonsahab

Solution by i9383

Solution by anonymous

Solution by Foowar

Views

Personal tools

Site_logo

Search

Content_hierarchy

Tools