论坛 › 数据结构与算法 › 括号匹配（栈的应用）

瞬秒爆加速 发表于 2015-1-27 20:16:05

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

此地无银 发表于 2015-1-28 16:34:42

#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");
    }

}

此地无银 发表于 2015-1-28 16:51:29

楼上我写的代码是错的。修改了下调试成功了。
基本跟小甲鱼老师一样，不过在主函数里，写法稍有不同。下面是主函数源代码：
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 发表于 2015-2-1 10:41:01

强烈支持楼主ing……

bluegyfrys 发表于 2015-2-15 14:03:17

强烈支持楼主ing……

gk-jsj 发表于 2015-3-2 21:49:50

强烈支持楼主ing……

星星当空照 发表于 2015-3-8 15:45:27

VIP都要回复啊

天外飞mao 发表于 2015-3-13 15:18:47

比较一下啦！

weiqi7777 发表于 2015-3-14 13:49:18

#include"iostream"
using namespace std;

typedef struct {
        int top;
        char a;
}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. 发表于 2015-3-25 09:42:26

强烈支持楼主ing……

stopit 发表于 2015-3-27 09:57:46

1111111111

喵小乐cherry 发表于 2015-3-31 19:26:38

我能说小甲鱼帮了我一个大忙吗?{:7_114:}

喵小乐cherry 发表于 2015-3-31 21:42:59

{:1_1:}

ryoko 发表于 2015-4-11 12:22:51

强烈支持楼主ing……

Alphacoder 发表于 2015-4-11 23:48:25

丢个5鱼币顶一下

陈轸 发表于 2015-4-14 23:03:32

强烈支持楼主ing……

馨馨予 发表于 2015-4-22 16:56:56

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

无影飞飞雪 发表于 2015-5-6 13:42:11

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

FTD_Chen 发表于 2015-5-10 19:23:44

真是难得给力的帖子啊。

yuelintao 发表于 2015-5-14 10:56:15

感兴趣，看看。。。。

查看完整版本: 括号匹配（栈的应用）