Is there a way to avoid isEmpty() function for a stack?

Question

The following program use an interger stack. Which value the function int pop() can return when the stack is empty, if I want to avoid using isEmpty() before calling the pop() ?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STK_SIZE 100
#define INSTR_SIZE 5
int push(int * stack,int * stk_top,int operand);
int pop(int * stack,int * stk_top);

int main()
{
    
    int n_instr=0;
    int operand=0;
    int stack[STK_SIZE];
    int stk_top = -1;
    char line[INSTR_SIZE+5];

    FILE * fp = fopen("instructions.txt", "r");
            
    fgets(line, sizeof(line), stdin);
    n_instr = atoi(line);
        
    for(int i=0;i<n_instr;i++)
    {
     fgets(line, sizeof(line), stdin);
     char * opcode = strtok(line, " \n");
           
    if(!strcmp(opcode,"PUSH")){
        
        operand = atoi(strtok(NULL, " "));
        push(stack,&stk_top,operand);
                }
    else if(!strcmp(opcode,"POP")){
        
        printf("%d\n",pop(stack,&stk_top));
        
        }
    
    else if(!strcmp(opcode,"ADD")){
        
        int n1 = pop(stack,&stk_top);
        int n2 = pop(stack,&stk_top);
        push(stack,&stk_top,n1 + n2);
        
        }

    else if(!strcmp(opcode,"SUB")){
        
        int n1 = pop(stack,&stk_top);
        int n2 = pop(stack,&stk_top);
        push(stack,&stk_top,n2 - n1);
        
        }
    
    }
     fclose(fp);
     
    while(stk_top>=0)printf("%d\n",pop(stack,&stk_top));
   
    return 0;

}

int push(int * stack,int * stk_top,int operand){

if(*stk_top<STK_SIZE-1){
            (*stk_top)++;
            stack[*stk_top]=operand;
            return 0;
            }
return 1;

}

int pop(int * stack,int *stk_top){
if(*stk_top>-1){
            int n = stack[*stk_top];
            (*stk_top)--;
            return n;
            }
return 0;
}

I use the above code for simulating the machine language instructions PUSH and POP ,ADD and SUB.For each POP instruction, output the value that was popped from the stack. After processing all instructions, print the final content of the stack, from the top to the bottom, one value per line.

Tried returning Integer values but it confuses with stack content, is there any work around ?

Ask yourself, "How does fgets() return a value (an input string) while it can also return whether or not the operation succeeded?" — user17592432
– user17592432, Commented Sep 17, 2023 at 7:53
Your pop function might return a pointer to the stack! If nothing is in the stack it returns null! Otherwise you shall use something as isEmpty() or a control variable but in this case you should control the stack situation before to call pop! On the other hand, also returning a null pointer if the stack is empty you have to control the result after the pop call. — Sir Jo Black
– Sir Jo Black, Commented Sep 17, 2023 at 8:28
If you were truly simulating machine language you would allow a stack underflow. You cannot have both a high fidelity simulation and "safe" code (safe with respect to the simulated code, the simulator itself can if course, and should be safe). Rather than a stack array, you would simply have a memory array for all memory which an SP can address, in which the stack-pointer were an index using modulo-n where n is the memory size. — Clifford
– Clifford, Commented Sep 17, 2023 at 9:20
Related: , there's a reason why the standard library pop operation on the stack adapter doesn't return anything. It's on you to grab top, then pop, and do neither unless empty is false. top'ing or pop'ing an empty stack is considered a runtime error condition. Don't treat it as a workflow option; treat it for what it is: an error. — WhozCraig
– WhozCraig, Commented Sep 17, 2023 at 9:28

Zakk · Accepted Answer · 2023-09-17 08:40:44Z

1

You could change pop() to this:

bool pop(int *stack, int *stk_top, int *old_top)
{
    if (*stk_top > -1) {
        if (old_top)
            *old_top = stack[*stk_top];

        (*stk_top)--;
        return true; // operation succeeded
    }
    return false;    // operation failed
}

You can choose to make use of the old stack top value or to discard it by simply making old_top NULL:

// Print all stack elements (except the top one) while deleting them altogether.

// Discard the first element (i.e. the top)
pop(stack, &stk_top, NULL);

int old_top = 0;
while (pop(stack, &stk_top, &old_top))
    printf("%d ", old_top);

answered Sep 17, 2023 at 8:40

Zakk

2,0931 gold badge9 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

score 0 · Accepted Answer · 2023-09-18 04:41:54Z

"I want to avoid using isEmpty() before calling the pop()"

Using isEmpty() to avoid calling pop() on an empty stack handles the "pre-" case. You can avoid this (if pop() handles underflow gently), but the code then has to check the operation's success testing a return code (the "post-" case). (Your "test" code expects push() to always succeed. Not wise.)

Below is an implementation that uses fewer parameters (only two in each case) and shows how both functions are called with their return values evaluated:

#include <stdio.h>

#define STACK_SIZE 5

int pop( int **stk, int *val ) { // NB: Address of popped value
    int *pTop = *stk;

    if( *pTop == 0 ) return 0; // failed

    *val = pTop[-1]; // fetch value
    pTop[-1] = pTop[0] - 1; // decrement count and store "below"
    *stk = pTop - 1;
    return 1; // success
}

int push( int **stk, int val ) {
    int *pTop = *stk;

    if( *pTop >= STACK_SIZE ) return 0; // failed

    pTop[1] = pTop[0] + 1; // incr count and store "above"
    pTop[0] = val;
    *stk = pTop + 1;
    return 1; // success
}

int main( void ) {
    int stk[ STACK_SIZE + 1 ] = { 0 };
    int *pStk = stk;
    int i, x;

    for( i = 0; i < STACK_SIZE + 2; i++ )
        printf( push( &pStk, 1<<i ) ? "pushed %d\n" : "Can't\n", 1<<i );

    for( i = 0; i < STACK_SIZE; i++ )
        printf( "stk[%d] = %d\n", i, stk[i] );

    for( i = 0; i < STACK_SIZE + 2; i++ )
        printf( pop( &pStk, &x ) ? "popped %d\n" : "Exhausted\n", x );

    return 0;
}

This works with a stack of int's. It uses the cell that is one above the top of the current stack to store the number of used cells below it. This value can be tested, to prevent both overflow and underflow.

Below is the same thing shortened by using double pointers. (this makes the code more challenging.)

int push( int **stk, int val ) {
    if( **stk >= STACK_SIZE ) return 0;

    *(*stk + 1) = **stk + 1; // record increase of current ceiling
    *(*stk)++ = val; // store value, then increment to new ceiling
    return 1;
}

int pop( int **stk, int *val ) {
    if( **stk == 0 ) return 0;

    *val = *(--*stk); // decrement and retrieve value
    **stk = *(*stk + 1) - 1; // replace (lower) top of stack with new count
    return 1;
}

halfer · Accepted Answer · 2023-09-20 08:30:40Z

You can for example change the function definition the following way:

int pop( int * stack, int *stk_top, int *value )
{
    int success = *stk_top != -1;

    if( success )
    {
        *value = stack[*stk_top];
        --*stk_top;
    }

    return success;
}

and call it like:

int n1
pop( stack, &stk_top, &n1 );

or like:

int n1
if ( pop( stack, &stk_top, &n1 ) )
{
    // do somethimg with n1
}

Your code would be clearer if you were to combine the array stack and the variable stk_top. For example:

struct Stack
{
    int a[STK_SIZE];
    int stk_top;
};

In main you could define an object of the structure type:

struct Stack stack = { .stk_top = -1 };

In this case the function will have less parameters and will be more clear as for example:

int pop( struct Stack *stack, int *value )
{
    int success = stack->stk_top != -1;

    if( success )
    {
        *value = stack->a[stack->stk_top];
        --stack->stk_top;
    }

    return success;
}

Collectives™ on Stack Overflow

Is there a way to avoid isEmpty() function for a stack?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related