括号匹配（栈的应用）

瞬秒爆加速

原来python的逆波兰的思路在这个地方

此地无银

#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 20
#define STACKINCREAMENT 10

typedef char ElemType;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

void initStack( sqStack *s )
{
    s->base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if( !s->base )
    {
        exit(0);
    }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

void Push( sqStack *s, ElemType *e )
{
    if( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType*)realloc( s->base, ( s->stackSize + STACKINCREAMENT ) * sizeof(ElemType) );
        if( !s->base )
        {
            exit(0);
        }
    }
    *(s->top) = e;
    s->top++;
}

void Pop( sqStack *s, ElemType *e )
{
    if(s->top == s->base)
        return;
    *e = * --(s->top);
}

int StackLen(sqStack s)
{
    return (s.top - s.base);
}

int main()
{
    sqStack s;
    char c;
    int e;

    initStack( &s );

    printf("请输入需要验证的括号，以#结束：\n");
    scanf("%c", &c);

    while(c != '#')
    {
        if( c!='(' && c!=')' && c!='[' && c!=']' && c!='{' && c!='}' && c!='<' && c!='>')
            {
                printf("输入的字符不为括号！\n");
                return -1;
            }
        if( c == s.base )
        {
            Push(&s, e);
            break;
        }
        Pop( &s, c );
    }

    if( s.top == s.base )
    {
        printf("\n输入的括号匹配成功！\n");
    }
    else
    {
        printf("\n输入的括号不匹配！\n");
    }

}

此地无银

楼上我写的代码是错的。修改了下调试成功了。
基本跟小甲鱼老师一样，不过在主函数里，写法稍有不同。下面是主函数源代码：
int main()
{
    sqStack s;
    char c;
    int e;

    initStack( &s );

    printf("请输入需要验证的括号，以#结束：\n");
    scanf("%c", &c);

    while(c != '#')
    {
       // 如果是括号，就压栈
        if( c=='(' || c==')' || c=='[' || c==']' || c=='<' || c=='>' || c=='\'' || c=='\"' || c=='{' || c=='}' )
        {
            if( !StackLen(s) )
            {
                Push(&s, c);
            }
            else
            {

                if( match(s.top, c) )
                {
                    Pop( &s, e);
                }
                else
                {
                    Push( &s, c);
                }
            }
        }

        scanf("%c", &c);    // 输入下一个字符
    }

    if( !StackLen(s) )
    {
        printf("\n输入的括号匹配成功！\n");
    }
    else
    {
        printf("\n输入的括号不匹配！\n");
    }

}

具体来说，每次先判定s.top和c是否匹配，如果匹配，则栈底出栈；如果不匹配，则将c入账。最后判定栈里无字符，则全部匹配成功。

wuyixin

强烈支持楼主ing……

bluegyfrys

强烈支持楼主ing……

gk-jsj

强烈支持楼主ing……

星星当空照

VIP都要回复啊

天外飞mao

比较一下啦！

weiqi7777

#include"iostream"
using namespace std;

typedef struct {
        int top;
        char a[100];
}stack;

void push(stack s, char a)
{
        if (s.top == 99)
                return;
        else
                s.a[++s.top] = a;
}

char pop(stack s)
{
        if (s.top == -1)
                return 0;
        else
                return s.a[--s.top];
}

int main()
{
        stack s;
        s.top = -1;
        char k;
        char n;
        int flag = 1;

        cin >> k;
        while (k != '#')
        {
                cin >> k;
                if (k == '(' || k == '{' || k == '[')
                        push(s, k);
                if (k == ')')
                {
                        n = pop(s);
                        if (n != '(')
                                flag = 0;
                }
                if (k == '}')
                {
                        n = pop(s);
                        if (n != '{')
                                flag = 0;
                }
                if (k == ']')
                {
                        n = pop(s);
                        if (n != '[')
                                flag = 0;
                }
        }

        if (flag == 1)
                printf("输入字符串的括号完全匹配\n");
        else
                printf("输入字符串的括号不完全匹配\n");
}

wmh.

强烈支持楼主ing……

stopit

1111111111

喵小乐cherry

我能说小甲鱼帮了我一个大忙吗?

喵小乐cherry

{:1_1:}

ryoko

强烈支持楼主ing……

Alphacoder

丢个5鱼币顶一下

陈轸

强烈支持楼主ing……

馨馨予

好好学习了 强烈支持楼主ing……

无影飞飞雪

感谢小甲鱼强烈支持楼主ing……

FTD_Chen

真是难得给力的帖子啊。

yuelintao

感兴趣，看看。。。。