时间戳

首页 > 解决方案 > 堆栈数据结构括号匹配

c++ - 堆栈数据结构括号匹配

问题描述

我正在尝试这个括号匹配堆栈代码，每次我运行它只会给我括号不匹配我不知道出了什么问题。你们能帮我解决这个问题并告诉我如何进一步改进吗？这是在 c++ 中使用堆栈的正确方法吗，因为我是从使用 c 语言的源学习的。

#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]!='\0'; 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\n";
        }
        else
        {
            cout<<"The parenthesis is not matching\n";
        }
        return 0;
    }

标签： c++data-structures

解决方案

刚刚尝试调试代码，发现2个潜在错误：

  1. 正如@Welbog在评论中正确指出的那样，要创建一个数组，sp->arr = new char[sp->size;请在函数中使用parenthesisMatch()。
  2. 在函数pop()中， 的值top没有正确递减。

看看工作代码：

#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]!='\0'; 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\n";
    }
    else
    {
        std::cout<<"The parenthesis is not matching\n";
    }
    return 0;
}

推荐阅读