问题描述
编写一个算法判断输入的表达式中括号是否配对(假设只含有左、右圆括号)编写一个算法判断输入的表达式中括号是否配对(假设只含有左、右圆括号)

输入:
(1+2*(5+3)/2)

输出:
(1+2*(5+3)/2) 是括号匹配的

代码实现1

#include <iostream>
#include <string.h>

using namespace std;

typedef char ElemType;

typedef struct linknode
{
    ElemType data;
    struct linknode *next;
}LinkStNote;


void InitStack(LinkStNote *&s)
{
    s = (LinkStNote *)malloc(sizeof(LinkStNote));
    s->next = NULL;
}

void DestoryStack(LinkStNote * &s)
{
    LinkStNote *pre = s, *p = s->next;
    while(p != NULL)
    {
        free(pre);
        pre = p;
        p = pre->next;

    }
    free(pre);
}

bool StackEmpty(LinkStNote * s)
{
    return (s->next == NULL);
}

void Push(LinkStNote *&s, ElemType e)
{
    LinkStNote *p;
    p = (LinkStNote *)malloc(sizeof(LinkStNote));
    p->data = e;
    p->next = s->next;
    s->next = p;
}

bool Pop(LinkStNote *&s, ElemType &e)
{
    LinkStNote *p;
    if(s->next == NULL)
    {
        return false;
    }
    p = s->next;
    e = p->data;
    s->next = p->next;
    free(p);
    return true;
}

bool GetTop(LinkStNote *s, ElemType &e)
{
    if(s->next == NULL)
    {
        return false;
    }
    e = s->next->data;
    return true;
}

bool Match(string exp, int n)
{
    int i = 0;
    char e;
    bool match = true;
    LinkStNote *st;
    InitStack(st);
    while(i < n && match)
    {
        if(exp[i] == '(')
        {

            Push(st, exp[i]);
        }else if(exp[i] == ')')
        {
            if(GetTop(st, e) == true)
            {
                if(e != '(')
                    match = false;
                else
                    Pop(st, e);
            }
            else match = false;
        }
        i++;
    }
    if(!StackEmpty(st))
    {
        match = false;
    }
    DestoryStack(st);

    return match;
}




int main()
{
    string exp;
    //从控制台输入字符串
    cin>>exp;
    if(Match(exp, exp.length()) == 1)
        cout<<exp<<" 是括号匹配的";
    else
        cout<<exp<<" 不是括号匹配的";

    return 0;
}


代码实现2

#include <iostream>
#include <string.h>

using namespace std;

typedef char ElemType;

typedef struct linknode
{
    ElemType data;
    struct linknode *next;
}LinkStNote;


void InitStack(LinkStNote *&s)
{
    s = (LinkStNote *)malloc(sizeof(LinkStNote));
    s->next = NULL;
}

void DestoryStack(LinkStNote * &s)
{
    LinkStNote *pre = s, *p = s->next;
    while(p != NULL)
    {
        free(pre);
        pre = p;
        p = pre->next;

    }
    free(pre);
}

bool StackEmpty(LinkStNote * s)
{
    return (s->next == NULL);
}

void Push(LinkStNote *&s, ElemType e)
{
    LinkStNote *p;
    p = (LinkStNote *)malloc(sizeof(LinkStNote));
    p->data = e;
    p->next = s->next;
    s->next = p;
}

bool Pop(LinkStNote *&s, ElemType &e)
{
    LinkStNote *p;
    if(s->next == NULL)
    {
        return false;
    }
    p = s->next;
    e = p->data;
    s->next = p->next;
    free(p);
    return true;
}

bool GetTop(LinkStNote *s, ElemType &e)
{
    if(s->next == NULL)
    {
        return false;
    }
    e = s->next->data;
    return true;
}

bool Match(char exp[], int n)
{
    int i = 0;
    char e;
    bool match = true;
    LinkStNote *st;
    InitStack(st);
    while(i < n && match)
    {
        if(exp[i] == '(')
        {

            Push(st, exp[i]);
        }else if(exp[i] == ')')
        {
            if(GetTop(st, e) == true)
            {
                if(e != '(')
                    match = false;
                else
                    Pop(st, e);
            }
            else match = false;
        }
        i++;
    }
    if(!StackEmpty(st))
    {
        match = false;
    }
    DestoryStack(st);

    return match;
}




int main()
{
    char exp[50];
    //从控制台输入字符串
    gets(exp);
    if(Match(exp, strlen(exp)) == 1)
        cout<<exp<<"是括号匹配的";
    else
        cout<<exp<<"不是括号匹配的";

    return 0;
}


运行结果1
在这里插入图片描述
运行结果2
在这里插入图片描述

Logo

GitCode 天启AI是一款由 GitCode 团队打造的智能助手,基于先进的LLM(大语言模型)与多智能体 Agent 技术构建,致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话,还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力,真正做到“一句话,让 Al帮你完成复杂任务”。

更多推荐