数据结构括号匹配问题

Question

为什么一直提示段错误
6-1 括号匹配
分数 10
作者 黄龙军
单位 绍兴文理学院
要求实现函数，借助如下自定义栈SqStack判断一个中、小括符组成的字符串中的括弧是否匹配，是则返回true，否则返回false。例如，“[[()]]、([[()]])、(()[[]])”是匹配的，而“[[()]]、([[()]])、(()[[]])”是不匹配的。

typedef char ElemType;                    // 为char取别名ElemType
struct SqStack{
    ElemType  *base;                      // 顺序栈的首地址，动态数组的首地址
    int top;                              // 栈顶指针，栈非空时，为栈顶元素的下标(从0开始)
    void Init( );                         // 初始化栈
    ElemType GetTop();                    // 取栈顶元素    
    void Push(ElemType e);                // 入栈
    void Pop();                           // 出栈
    bool Empty();                         // 判断空栈
};

函数接口定义：
bool matching(string exp);
其中参数 exp是一个仅包含中、小括符[、]、(、)的字符串。

裁判测试程序样例：

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        if (matching(s)) cout<<"yes\n";
        else cout<<"no\n";
    } 
    return 0;
}

输入样例：
()[]
[()]
[(()]]
[(])
输出样例：
yes
yes
no
no

这是我的代码：

#include<iostream>
#include<string>
using namespace std;

typedef char ElemType;                    // 为char取别名ElemType
struct SqStack{
    ElemType  *base;                      // 顺序栈的首地址，动态数组的首地址
    int top;                              // 栈顶指针，栈非空时，为栈顶元素的下标(从0开始)
    void Init( );                         // 初始化栈
    ElemType GetTop();                    // 取栈顶元素    
    void Push(ElemType e);                // 入栈
    void Pop();                           // 出栈
    bool Empty();                         // 判断空栈
};

bool matching(string exp){
     SqStack stack;
    int num=0;
    while(exp[num]){ //得到串的长度 
         
        num++;
    }
    
    int i=0;
    int flag=1;
    while(num--){
        switch(exp[i]){
          case '(':
            case '[':
                stack.Push(exp[i]);
                i++;
                break;
            
            case')':{
                if(!stack.Empty()&& stack.GetTop()=='('){  //Empty()函数当栈为空时返回TRUE不为空返回FALSE 
                    stack.Pop();
                    i++;
                }
                else{
                    flag=0;   //说明栈为空或者")"前面不是"(" 都不符合要求 
                }
                break;
            }
            
            
            case']':{
                if(!stack.Empty()&& stack.GetTop()=='['){  //Empty()函数当栈为空时返回TRUE不为空返回FALSE 
                    
                    stack.Pop();
                    i++;
                    break;
                }
                else{
                    flag=0;   //说明栈为空或者")"前面不是"(" 都不符合要求 
                       break;
                }
             
            }             
        }
    }
    
    if(flag&&stack.Empty()){
        return true;
    }
    else{
        return false;
    }
    
}

Answer 1

【以下回答由 GPT 生成】

#include<iostream>
#include<string>
using namespace std;

struct SqStack{
    char *base;
    int top;

    void Init() {
        base = new char[100];
        top = -1;
    }

    char GetTop() {
        if (top == -1) return '#';
        return base[top];
    }

    void Push(char e) {
        top++;
        base[top] = e;
    }

    void Pop() {
        if (top != -1) top--;
    }

    bool Empty() {
        return top == -1;
    }
};

bool matching(string exp) {
    SqStack s;
    s.Init();

    for(int i = 0; i < exp.length(); i++) {
        char c = exp[i];
        if (c == '(' || c == '[') {
            s.Push(c);
        } else if (c == ')' || c == ']') {
            char topChar = s.GetTop();
            if (topChar == '(' && c == ')') {
                s.Pop();
            } else if (topChar == '[' && c == ']') {
                s.Pop();
            } else {
                return false;
            }
        }
    }

    return s.Empty();
}

int main(){
    string s;
    while(cin>>s) {
        if (matching(s)) cout<<"yes\n";
        else cout<<"no\n";
    } 
    return 0;
}

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^