simple calculator / reverse Polish notation

This is a discussion on simple calculator / reverse Polish notation within the C Programming forums, part of the General Programming Boards category; Everything works on this calculator except handling standard subraction '-'. For example: (4+5)*(3/7) is written as 4 5+ 3 7/*, ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    8

    Question simple calculator / reverse Polish notation

    Everything works on this calculator except handling standard subraction '-'.
    For example:
    (4+5)*(3/7) is written as 4 5+ 3 7/*, and the program answers correctly. It also works for negative numbers: -4 -9+ or -34 273*. However, normal subtraction requires a double '-' to work. Like this: 4 9--. If you use just a single - like this: 4 9-, it just reprints the last character (9). The problem seems to be in calling the getch() and ungetch() functions in 'getop()' but I cannot pinpoint it....

    (ps. if you see the problem please also explain the concept I am missing here)
    Allan




    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXOP 100
    #define NUMBER '0'
    
    int getop(char []);
    void push(double);
    double pop(void);
    void swap(double);
    void clear(double);
    
    main () { /*reverse-Polish-notation calculator*/
    	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((int)pop()%(int)op2);
    				else
    					printf("error: zero divisor\n");
    				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[])
    {
    	int i,c;
    	while ((s[0]=c=getch())==' ' || c == '\t')
    		;
    	s[1]='\0';
    	i=0;
    	if(!isdigit(c)&&c!='.')
    		if (c=='-' && (isdigit(s[++i]=c=getch()))) /*have to use '2 3--' (double -) to get subtraction...*/
    			;
    		else
    			return c; /*not a number*/
    
    	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) /*get a (possibly pushed-back) character */
    {
    	return (bufp>0) ? buf[--bufp] : getchar();
    }
    
    void ungetch(int c)
    {
    	if (bufp>=BUFSIZE)
    		printf("ungetch:too many characters\n");
    	else
    		buf[bufp++]=c;
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Quote Originally Posted by allan01123 View Post
    Code:
    	if(!isdigit(c)&&c!='.')
    		if (c=='-' && (isdigit(s[++i]=c=getch()))) /*have to use '2 3--' (double -) to get subtraction...*/
    			;
    		else
    			return c; /*not a number*/
    I don't think there's a problem in getch or ungetch, or really any problem at all (except failing to fail on an invalid expression). "4 9-" is invalid according to your grammar. Here is what happens:

    You grab the 4 and push it on the stack, then grab the 9 and push it on the stack. Then, you find a '-'. You enter the first if block, if (!isdigit(c) && c != '.'). Then you execute the second if statement. Since c is a '-', you get to the second half of your condition and do isdigit(s[++i]=c=getch()), which grabs the new line, stuffs it in c and in s[++i], but fails the test since a newline is not a digit, so you drop to the else and return c, which is now '\n'.

    In your main case statement, you drop to the '\n' case, since you returned that instead of a subtraction operator or error. You print the result of pop(), the last number pushded on the stack, which was 9.

    As a side note, you should put a set of { } around the if (c=='-'... section to avoid the dangling else issue and make your intentions clear.

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    8
    I see the \n problem now.

    I was using that isdigit() condition to check (if) the next char was a digit, which would then tell the program it was a negative (sign) vs. a negative (operator). i.e. this allows '-45' to be read in as a negative number rather than an error.

    So the code seems to work right, which is to say when it sees a \n (after a '-'), then that '-' is representing an operand (instead of a sign). Then it should jump to: 'return c' and I wanted it to pass the 'c' (-) sign back up to the main case, but I see now it is passing the '\n' instead.

    I can see where a simple if/then right before the 'return c;' could get around this, but it seems there should be a more natural flow/method to accomplish this. Like using ungetch to push that '-' back onto the stack. But everytime I try it I get "error:stack empty".

    Code:
    		else
    		{ungetch(c);return c;} /*not a number*/

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Remember, c is '\n' at that point, so ungetch(c) pushes a newline back into the input buffer, then you pull it off with getch, processing it, which leads you to do a pop/print in your main switch statement. After the 9 is popped and printed, you pop and print the 4, then there's nothing left, and your program doesn't handle that very well, looping forever on the newline you keep pushing back into your getch/ungetch input buffer. Try something like:
    Code:
    if (c == '-') {
        c2 = getch()
        if (c2 == '-') {
            return '-';
        }
        else if (isdigit(c2)) {
            ungetch(c2);  // fall out of this statement to process as a number
        }
        else {
            printf("error: invalid token\n");
            return ERROR;
        }
    }
    else {
        return c; // other operators like '+', '/', etc
    }

  5. #5
    Registered User
    Join Date
    Jan 2011
    Posts
    8
    I tried the suggested code, and it did work for the (--) double negative, i.e. 9 4--. But I still got a similar error for the single: 4 9- . Then I realized the 'Main' was already at EOF after the '/n' was input, so passing a '-' back up from getop was triggering the correct case, but then the program stopped without output and just waited for the next input (i.e. 'main' needs that '\n' to printf the output).

    So I tried the following code (& added another printf in the '-' case) and it works, but it seems overly long/wordy. This was a basic level problem and I think my answer was not the one intended... is there something basic I am missing?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXOP 100
    #define NUMBER '0'
    
    int getop(char []);
    void push(double);
    double pop(void);
    void swap(double);
    void clear(double);
    
    main () { /*reverse-Polish-notation calculator*/
    	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);
    				printf("\t%.8g\n",pop());
    				break; }
    			case '%':
    				op2=pop();
    				if (op2 != 0.0)
    					push((int)pop()%(int)op2);
    				else
    					printf("error: zero divisor\n");
    				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[])
    {
    	int i,c;
    	while ((s[0]=c=getch())==' ' || c == '\t')
    		;
    	s[1]='\0';
    	i=0;
    	if(!isdigit(c)&&c!='.') 
    	{
    		if (c=='-' && (isdigit(s[++i]=c=getch()))) /*have to use '2 3--' (double -) to get subtraction...*/
    			;
    		else if (c=='\n' && s[i-1]=='-')
    			return '-';
    		else
    			return c; /*not a number*/
    	}
    
    	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) /*get a (possibly pushed-back) character */
    {
    	return (bufp>0) ? buf[--bufp] : getchar();
    }
    
    void ungetch(int c)
    {
    	if (bufp>=BUFSIZE)
    		printf("ungetch:too many characters\n");
    	else
    		buf[bufp++]=c;
    }

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Quote Originally Posted by allan01123 View Post
    I tried the suggested code, and it did work for the (--) double negative, i.e. 9 4--. But I still got a similar error for the single: 4 9- . Then I realized the 'Main' was already at EOF after the '/n' was input, so passing a '-' back up from getop was triggering the correct case, but then the program stopped without output and just waited for the next input (i.e. 'main' needs that '\n' to printf the output).

    So I tried the following code (& added another printf in the '-' case) and it works, but it seems overly long/wordy. This was a basic level problem and I think my answer was not the one intended... is there something basic I am missing?
    I don't think it's too wordy for a "basic level" problem, and I don't think you're missing anything. As for your waiting for input problem, you need to ungetch the newline if you find only a single - at the end of the line. That extra printf you added is a problem too, since after a subtraction, you pop the result off the stack to print, so complex expressions like "9 5-- 2*" will fail. When you hit the multiplier, it tries to pop off two numbers from the stack, but the result of 9-5 was removed so there's only one number, the 2, on the stack. Remove it:
    Code:
    			case '-': {
    				op2=pop();
    				push(pop()-op2);
    				printf("\t%.8g\n",pop());
    				break; }

  7. #7
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    I don't know why you are using your own buffer for parsing./push back
    Is it supposed to be K&R RPN calculator exercise?
    Code:
    typedef union {
       double val;
       char *str;            // for function call ,var       PI sin -> 0.0
    }Value;
    
    int getop(Value *v)
    {
        double val;
        int c;
        while( (c = getchar()) == ' ' || c == '\t')
             ;
        if(c == EOF) return EOF;
        if( isdigit(c) || c == '.' || c == '-') {     // number?
           ungetc(c,stdin);
           if( scanf("%lf",&v.val) == 1 ) {
                return NUMBER;
            }
         }
         if( isalpha(c) || c == '_') {        // variable or function name
                /* code; code; code*/
         }
           return c;
    }
    Last edited by Bayint Naung; 02-03-2011 at 10:08 PM.

  8. #8
    Registered User
    Join Date
    Jan 2011
    Posts
    8
    (Yes, it a KR RPN example, and we only have a few basic tools we are allowed to use, hence the buffer)

    I deleted the extra printf and added the ungetch(c):

    Code:
    	if(!isdigit(c)&&c!='.') 
    	{
    		if (c=='-' && (isdigit(s[++i]=c=getch()))) 
    			;
    		else if (c=='\n' && s[i-1]=='-')
    		{ungetch(c);return '-';}
    		else
    			return c; /*not a number*/
    	}
    It now works for almost everything. The last issues are:

    7 5-- 4* (which should return an error because the second '-' does not have 2 operands to pop... however the program returns '8')

    7 5- 2+ (which should return '4', but instead returns 'error:unknown command - ..' and then '7')

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. polish notation calc problem
    By deedlit in forum C Programming
    Replies: 6
    Last Post: 06-14-2004, 10:17 PM
  4. problem on reverce polish notation
    By dionys in forum C++ Programming
    Replies: 0
    Last Post: 05-14-2004, 01:30 PM
  5. infix vs Reverse Polish notation
    By dionys in forum C Programming
    Replies: 1
    Last Post: 05-10-2004, 02:25 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21