c++ - Stack Data Structure Parenthesis Matching

Question

I was trying this parenthesis matching stack code and every time I run this it only gives me that parenthesis are not matching I don't know what is going wrong. Can you guys please help me out in this and tell me how can I improve this further and is this the right way to use stack in c++ because I was studying from a source that is using c language.

#include<iostream>
    
    using namespace std;
    
    struct stack
    {
        int size;
        int top;
        char *arr;
        
    };
    
    int isEmpty(struct stack *ptr)
    {
        if(ptr->top==-1)
        {
            return 1;
        }
        return 0;
    }
    
    int isFull(struct stack *ptr)
    {
        if (ptr->top == ptr->size-1)
        {
            return 1;
        }
        return 0;
    }
    
    void push(struct stack *ptr,char val)
    {
        if(isFull(ptr))
        {
            cout<<"stack overflow"<<endl;
        }
        else
        {
            ptr->top++;
            ptr->arr[ptr->top] = val;
        }
    }
    
    char pop(struct stack *ptr)
    {
        if (isEmpty(ptr))
        {
            cout<<"stack underflow"<<endl;
            return -1;
        }
        else
        {
            char val = ptr->arr[ptr->top];
            ptr->top-1;
            return val;
        }
    }
    
    int parenthesisMatch (char * exp)
    {
        struct stack * sp = new struct stack;
        sp->size = 80;
        sp->top = -1;
        sp->arr = new char(sp->size);
        
        for(int i=0; exp[i]!=''; i++)
        {
            if (exp[i] == '(')
            {
                push(sp,'(');
            }
            else if(exp[i] == ')')
            {
                if (isEmpty(sp))
                {
                    return 0;
                }
                pop(sp);
            }
            }
        
        
        if (isEmpty(sp))
        {
            return 1;
        }
        return 0;
    }
    
    int main()
    {
        char *exp = "((8)(*--$$9))";
        if(parenthesisMatch(exp))
        {
            cout<<"The parenthesis is matching
";
        }
        else
        {
            cout<<"The parenthesis is not matching
";
        }
        return 0;
    }

question from:https://stackoverflow.com/questions/65858050/stack-data-structure-parenthesis-matching

Answer 1

Just tried to debug the code and found 2 potential errors:

1. As correctly pointed out by @Welbog in the comments, to create an array, use sp->arr = new char[sp->size; in the function parenthesisMatch().
2. In the function pop(), the value of the top is not decremented correctly.

Have a look at the working code:

#include<iostream>

struct stack
{
    int size;
    int top;
    char *arr;
    
};

int isEmpty(struct stack *ptr)
{
    if(ptr->top==-1)
    {
        return 1;
    }
    return 0;
}

int isFull(struct stack *ptr)
{
    if (ptr->top == ptr->size-1)
    {
        return 1;
    }
    return 0;
}

void push(struct stack *ptr,char val)
{
    if(isFull(ptr))
    {
        std::cout<<"stack overflow"<<std::endl;
    }
    else
    {
        ptr->top++;
        ptr->arr[ptr->top] = val;
    }
}

char pop(struct stack *ptr)
{
    if (isEmpty(ptr))
    {
        std::cout<<"stack underflow"<<std::endl;
        return -1;
    }
    else
    {
        char val = ptr->arr[ptr->top];
        ptr->top-=1;
        return val;
    }
}

int parenthesisMatch (char * exp)
{
    struct stack * sp = new struct stack;
    sp->size = 80;
    sp->top = -1;
    sp->arr = new char[sp->size];
    
    for(int i=0; exp[i]!=''; i++)
    {
        if (exp[i] == '(')
        {
            push(sp,'(');
        }
        else if(exp[i] == ')')
        {
            if (isEmpty(sp))
            {
                return 0;
            }
            pop(sp);
        }
        }
    
    
    if (isEmpty(sp))
    {
        return 1;
    }
    return 0;
}

int main()
{
    char *exp = "((8)(*--$$9))";
    if(parenthesisMatch(exp))
    {
        std::cout<<"The parenthesis is matching
";
    }
    else
    {
        std::cout<<"The parenthesis is not matching
";
    }
    return 0;
}