【啊哈！算法】算法5：解密回文——栈

啊哈磊

        上一节中我们学习了队列，它是一种先进先出的数据结构。还有一种是后进先出的数据结构它叫做栈。栈限定只能在一端进行插入和删除操作。比如说有一个小桶，小桶的直径只能放一个小球，我们现在向小桶内依次放入2号、1号、3号小球。假如你现在需要拿出2号小球，那就必须先将3号小球拿出，再拿出1号小球，最后才能将2号小球拿出来。在刚才取小球的过程中，我们最先放进去的小球最后才能拿出来，而最后放进去的小球却可以最先拿出来。这就是后进先出，也可以称为先进后出。

        我们生活中还有很多这样的例子，比如我们在吃桶装薯片的时候，要想吃掉最后一片，就必须把前面的全部吃完（貌似现在的桶装薯片为了减少分量，在桶里面增加了一个透明的抽屉）；再比如我们浏览网页时候需要退回到之前的某个网页，我们需要一步步的点击后退键。还有手枪的弹夹，在装子弹的时候，最后装的一发子弹，是被第一个打出去的。栈的实现也很简单，只需要一个一维数组和一个指向栈顶的变量top就可以了。我们通过变量top来对栈进行插入和删除操作。

        这种特殊的数据结构栈究竟有哪些作用呢？我们来看一个例子。“xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回文，但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。

        首先我们需要读取这行字符串，并求出这个字符串的长度。

1. char a[101]; //101是一个估算值，只需比待读入的字符串长度大即可
   
2. int len;
   
3. gets(a);
   
4. len=strlen(a);

复制代码

        如果一个字符串是回文的话，那么它必须是中间对称，我们需要求这个字符串的 中点，即：

1. mid=len/2-1;

复制代码

        接下来就轮到栈出场了。

        我们先将mid之前的部分的字符全部入栈。因为这里的栈是用来存储字符的，所以这里用来实现栈的数组类型是字符数组即char s[101]; 初始化栈很简单，top=0;就可以了。入栈的操作是top++;s[top]=x; （假设需要入栈的字符存储暂存在字符变量x中）其实可以简写为s[++top]=x;

        现在我们就来将mid之前的字符依次全部入栈。这里循环要0开始，因为刚才读取字符串使用了gets()函数，读取的第一个字符存储在s[0]中，随后一个字符存储在s[len-1]中。

1. for(i=0;i<=mid;i++)
   
2. {
   
3.     s[++top]=a[i];
   
4. }

复制代码

        接下来进入判断回文的关键步骤。将当前栈中的字符依次出栈，看看是否能与mid之后的字符一一匹配，如果都能匹配则说明这个字符串是回文字符串，否则这个字符串就不是回文字符串。

1. for(i=mid+1;i<=len-1;i++) //其实这里并不一定是mid+1，需要讨论字符串长度的奇偶性
   
2. {
   
3.     if (a[i]!=s[top])
   
4.     {
   
5.           break;
   
6.     }
   
7.     top--;
   
8. }
   
9. if(top==0)
   
10.     printf("YES");
    
11. else
    
12.     printf("NO");

复制代码

        最后如果top的值为0，就说明栈内所有的字符都被一一匹配了，那么这个字符串就是回文字符串。完整的代码如下。

1. #include <stdio.h>
   
2. #include <string.h>
   
3. int main()
   
4. {
   
5.     char a[101],s[101];
   
6.     int i,len,mid,next,top;
   
7.    
   
8.     gets(a); //读入一行字符串
   
9.     len=strlen(a); //求字符串的长度
   
10.     mid=len/2-1; //求字符串的中点
    
11.    
    
12.     top=0;//栈的初始化
    
13.     //将mid前的字符依次入栈
    
14.     for(i=0;i<=mid;i++)
    
15.         s[++top]=a[i];
    
16.    
    
17.     //判断字符串的长度的是奇数还是偶数，并找出需要进行字符匹配的起始下标   
    
18.     if(len%2==0)
    
19.         next=mid+1;
    
20.     else
    
21.         next=mid+2;
    
22.                   
    
23.     //开始匹配
    
24.     for(i=next;i<=len-1;i++)
    
25.     {
    
26.         if(a[i]!=s[top])
    
27.             break;
    
28.         top--;
    
29.     }
    
30.    
    
31.     //如果top的值为0，则说明栈内的所有的字符都被一一匹配了
    
32.     if(top==0)
    
33.         printf("YES");
    
34.     else
    
35.         printf("NO");
    
36. 
    
37.     getchar();getchar();
    
38.     return 0;
    
39. }

复制代码

       可以输入以下数据进行验证

1. ahaha

复制代码

        运行结果是

1. YES

复制代码

        栈还可以用来进行验证括号的匹配。比如输入一行只包含“()[]{}”的字符串，形如“([{}()])”或者“{()[]{}}”请判断是否可以正确匹配。显然上面两个例子都是可以正确匹配的。“([)]”是不能匹配的。有兴趣的同学可以自己动手来试一试。

        堆栈最早由Alan M. Turing（艾伦·图灵）于1946年提出，当时为了解决子程序的调用和返回。艾伦·图灵这个大帅哥可是个大牛人，图灵奖就是以他的名字命名的。如果你对他感兴趣不妨去读一读他的传记《艾伦•图灵传：如谜的解谜者》。

4399APPLE

HAO！！            

cad20020601

先抢前排！

超神级

回头看,                           

shock

回文用不到栈的啊，还是下文那个判断符号匹配的例子比较好

cad20020601

磊大大！！不要把标题弄成刮刮乐啦！

绝处逢生

我想起了 “贱”

981013

回文我一直是硬拆成数组（字符串就不用了，本身是数组{:soso_e113:}，数字的话就先转成字符串【字符串I/O】或者先%10再/10），然后从两头往中间判断是否一样来判断的

981013

个人觉得栈最大的用处是表达式求值

嗨，强哥！

为了帮助新手输入，我画蛇添足加了几个输入语句

[mw_shl_code=c,true]//【啊哈算法】5 解密回文————栈
//链接复制地址：http://www.ahalei.com/thread-4515-1-1.html

#include <stdio.h>
#include <string.h>
int main()
{
    char a[101],s[101];
    int i,len,mid,next,top;
   
    printf ("这是一个关于栈的判断回文例子\n");
   
    while (1)            //这是个死循环，运行时请点黑窗口的X来结束程序！
    {
                printf ("\n\n请输入一行字符串：");
                gets (a);        //读入一行字符串
                len = strlen(a); //求字符串的长度
                mid = len/2-1;   //求字符串的中点
   
                top=0;           //栈的初始化
                //将mid前的字符依次入栈
                for(i=0;i<=mid;i++)
                        s[++top]=a;  
   
                //判断字符串的长度的是奇数还是偶数，并找出需要进行字符匹配的起始下标   
                if(len%2==0)
                        next=mid+1;
                else
                        next=mid+2;
                  
                //开始匹配
                for(i=next;i<=len-1;i++)
                {
                        if(a!=s[top])
                                break;
                                top--;
                }
   
                //如果top的值为0，则说明栈内的所有的字符都被一一匹配了
                if(top==0)
                        printf("输入的字符串是否为回文？ YES!");
                else
                        printf("输入的字符串是否为回文？ NO!");
        }
   
    sytem ("pause");
    return 0;
}
[/mw_shl_code]

rosynirvana

这个例子用栈非常古怪，明显头尾一起扫会更自然

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. int isParlindromic(const char*);
   
5. 
   
6. int main()
   
7. {
   
8.         char input[512];
   
9.         scanf("%511s", input);
   
10.         puts(isParlindromic(input) ? "Yes" : "No");
    
11.         return 0;
    
12. }
    
13. 
    
14. int isParlindromic(const char* input)
    
15. {
    
16.         int length = strlen(input);
    
17.         int head, tail;
    
18.         if(length == 0)
    
19.                 return 1;
    
20. 
    
21.         for(head = 0, tail = length-1; head<tail; ++head, --tail)
    
22.                 if(input[head] != input[tail])
    
23.                         return 0;
    
24.         return 1;
    
25. }

复制代码

kuaile1210

rosynirvana 发表于 2014-9-7 01:17
这个例子用栈非常古怪，明显头尾一起扫会更自然

长见识了，好多新鲜的用法！
来自: 微社区

yealove

“{()[]{}}”这个不是回文吧，第二个括号和倒数第二个大括号不匹配的呀..

cai_zhenAn

    char a[100] = "eehee";
    char s[100];
    int i,len,mid,next,top;
    len = strlen(a);
    mid=len/2-1;
    top=0;
    for (int i=0; i<=mid; i++) {
        int temp = top++;
        printf("%d",temp);
        s[temp]=a[i];
    }
    if (len%2==0) {
        next=mid+1;
    }else{
        next=mid+2;
    }
   
    for (i=next; i<len; i++) {
        printf("哈哈哈哈哈%c",s[top--]);
        if (a[i]!=s[top]) {
            break;
        }
    }
    if (top==0) {
        printf("YES");

    }else{
         printf("NO");
    }