Postfix evaluation using stacks and C

Question

I was on here a while a go with a similar problem but I think with the wrong question. To give a bit of background, I a tasked with creating a C program to solve a postfix expression in the form

8 7 - 9 * =

What I think my problem is, is that my prof gave as some incorrect stack code. I say this because I am constantly getting the stack overflow (lol) error and my stack is nowhere near full. If it helps I'm using visual studio 2005. Here's my code:

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

    #define STACK_SIZE 20

    typedef int Bit;

    Bit contents[STACK_SIZE];
    int top = 0;

    void make_empty(void);
    int is_empty(void);
    int is_full(void);
    void push(Bit i);
    int pop(void);
    void stack_overflow(void);
    void stack_underflow(void);

    int main(void) {
      Bit bit;
      char operation;
      int operand;
      Bit current;
      int result;

        while(scanf("%d",&current)!= '=')
        {
            push(current);
        }

        scanf("%c", &operation);
        while(operation != '=')
        {
            scanf("%d", &operand);
            printf("%d\n",top);
            //Pushes any number into the stack
            if(operand==1||operand==2||operand==3||operand==4||operand==5||operand==6||operand==7||operand==8||operand==9||operand==0)
            {
                printf("entered number loop\n");
                bit = operand;
                if(top==20)
                {
                    stack_overflow();
                }
                push(&bit);
            }

            //Performs subtraction operation
            else if(operation == '-')
            {
                printf("entered minus loop\n");
                if(top==1)
                {
                    stack_underflow();
                }

                result = pop() - pop();

                bit = result;

                if(top==20)
                {
                    stack_overflow();
                }

                push(&bit);
            }

            //Performs addition operation
            else if(operation == '+')
            {
                if(top==1)
                {
                    stack_underflow();
                }

                result = pop() + pop();
                bit = result;

                if(top==20)
                {
                    stack_overflow();
                }

                push(&bit);
            }

            //Performs multiplication operation
            else if(operation == '*')
            {
                if(top==1)
                {
                    stack_underflow();
                }

                result = pop() * pop();
                bit = result;

                if(top==20)
                {
                    stack_overflow();
                }

                push(&bit);
            }

            //Performs division operation
            else if(operation == '/')
            {
                if(top==1)
                {
                    stack_underflow();
                }

                result = pop() / pop();
                bit = result;

                if(top==20)
                {
                    stack_overflow();
                }

                push(&bit);
            }

            else if(operation == '=')
            {
                if(top==0)
                {
                    stack_underflow();
                }

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

void make_empty(void) {
  top = 0;
}

int is_empty(void) {
  return top == 0;
}

int is_full(void) {
  return top == STACK_SIZE;
}

void push(Bit i) {
  if (is_full())
    stack_overflow();
  else
    contents[top++] = i;
}

int pop(void) {
  if (is_empty())
    stack_underflow();
  else
    return contents[top--];
}

void stack_overflow(void) {
  printf("Error: stack overflow!\n");
  exit(EXIT_FAILURE);
}

void stack_underflow(void) {
  printf("Error: stack underflow!\n");
  exit(EXIT_FAILURE);
}

Now I realize that my code is a little barbaric right now and for that I apologize. That being said, any help or input at all would be greatly appreciated and thank you all in advance.

---

Ok, so after taking everything into account, I think I'm getting close. Everything going into the stack properly and everything is being read properly. However, my new implementation includes making everything a character and then converting the integers when they need to be used. Here is my source code once again:

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

#define STACK_SIZE 20

typedef int Bit;

char contents[STACK_SIZE];
int top = 0;

void make_empty(void);
int is_empty(void);
int is_full(void);
void push(char i);
char pop(void);
void stack_overflow(void);
void stack_underflow(void);

int main(void) {
    char current = 'a';
    char result = 'a';
    char operation = 'a';
    char char1;
    char char2;
    int number1;
    int number2;

    scanf("%c", &current);
    //While program successfully scanned a number
    while(current != '=')
    {

        //Performs subtraction operation
        if(current == '-')
        {
            printf("entered if 2\n");
            char1 = pop();
            number1 = char1 - '0';
            printf("%d\n", number1);
            char2 = pop();
            number2 = char2 - '0';
            printf("%d\n", number2);
            result = number1 - number2;

            push(result);
        }

        //Performs addition operation
        else if(current == '+')
        {
            printf("entered if 2\n");
            char1 = pop();
            number1 = char1 - '0';
            printf("%d\n", number1);
            char2 = pop();
            number2 = char2 - '0';
            printf("%d\n", number2);
            result = number1 + number2;

            push(result);
        }

        //Performs multiplication operation
        else if(current == '*')
        {
            printf("entered if 2\n");
            char1 = pop();
            number1 = char1 - '0';
            printf("%d\n", number1);
            char2 = pop();
            number2 = char2 - '0';
            printf("%d\n", number2);
            result = number1 * number2;

            push(result);
        }

        //Performs division operation
        else if(current == '/')
        {
            printf("entered if 2\n");
            char1 = pop();
            number1 = char1 - '0';
            printf("%d\n", number1);
            char2 = pop();
            number2 = char2 - '0';
            printf("%d\n", number2);
            result = number1 / number2;

            push(result);
        }

        else
        {
            push(current);
            printf("%c\n", current);
        }

        scanf(" %c", &current);
    }   

    //Prints result
    printf("%c\n",pop());

    return 0;
}

void make_empty(void) {
  top = 0;
}

int is_empty(void) {
  return top == 0;
}

int is_full(void) {
  return top == STACK_SIZE;
}

void push(char i) {
  if (is_full())
    stack_overflow();
  else
    contents[top++] = i;
}

char pop(void) {
  if (is_empty())
    stack_underflow();
  else
    return contents[top--];
}

void stack_overflow(void) {
  printf("Error: stack overflow!\n");
  exit(EXIT_FAILURE);
}

void stack_underflow(void) {
  printf("Error: stack underflow!\n");
  exit(EXIT_FAILURE);
}

Please keep in mind that I have been playing around with it quite a bit, so there are random printfs and useless variables all for debugging purposes. Whenever I run it (with example input 3 5 + =) I get:

So again, please excuse my some what messy code as I am quite new to C but any help would be great!

Answer 1

You have a problem with the following line:

while(scanf("%d",&current)!= '=')

The scanf function returns the number of items scanned, not the item. And scanning for %d will attempt to get an integer, not a character.

I think you should be looking more into something like:

while (scanf("%d",&current) == 1)
    push(current);

which will push integers on to the stack until it can no longer scan one (i.e., you get an operation).

This is almost certainly your problem since that particular scanf will generally only return 0 or 1, meaning it will never be equal to = (which is hex 0x3d or decimal 61 if you're using ASCII). It could return EOF in some cases but that still won't give you a value of 61.

The fact that it will never return 61 means that it will simply keep looping, pushing the value of current on to your stack until it overflows, which is the behaviour you're seeing.

Answer 2

I don't see any problem with the stack. But there are at least two problems in your main.

push(&bit);

push accepts a Bit, not a Bit *. You should get a warning here, which you probably have ignored. Do not ignore the warnings.

while(scanf("%d",&current)!= '=')

This is definitely wrong. scanf retuns the number of successful input.

operand==1||operand==2||operand==3||operand==4||operand==5||operand==6||operand==7||operand==8||operand==9||operand==0

Though this is not a bug, why should you write like this? You can easily replace with:

operand >= 0 && operand <= 9

And there might be many more problems.

Answer 3

This is an endless loop:

while(scanf("%d",&current)!= '=') { push(current); }

scanf returns the number of fields read successfully. In your case this can be 0 or 1. You are comparing it to '=' which is ASCII 61. So the '"!=" is always true and you never come past this loop.

BTW, if you look at how push is implemented you see that the check for "stack overflow" is done using the is_full() function. is_full() is comparing top against STACK_SIZE. You are comparing top==20. You better should use is_full. This is more abstract and would work even if someone changed STACK_SIZE. You could even omit your checks for top==20 and top==0 because the only thing you do is call stack_underflow/stack_overflow, which is already done by the pop/push functions.