【蓝桥杯】【啊哈！算法】解密回文——栈

一时失言乱红尘 2022-11-16 15:13 207阅读 0赞

## [【啊哈！算法】系列文章目录][Link 1] ##

--------------------

### 目录 ###

*   *  【啊哈！算法】系列文章目录
     *   *  需求介绍
         *  思路分析
         *  C语言代码
         *  C++ STL 库中的栈Stacks
         *   *  1. 整体应用
             *  2. 用C++ 解决需求
         *  附录：配对括号

--------------------

### 需求介绍 ###

**判断一个字符串是否为回文。**  
  **说明：** “xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如 “aha” 和 “ahaha” 均是回文，但“ahah”不是回文。

--------------------

### 思路分析 ###

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

char a[101]; 
    int len; 
    gets(a); 
    len=strlen(a);

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

mid=len/2-1;

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

for(i=0;i<=mid;i++) 
    {  
    	s[++top]=a[i]; 
    }

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

for(i=mid+1;i<=len-1;i++) 
    {  
    	if (a[i]!=s[top]) 
    	{  
    		break; 
    	} 
    	top--; 
    } 
    if(top==0) 
    	printf("YES"); 
    else 
    	printf("NO");

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

--------------------

### C语言代码 ###

#include <stdio.h>
    #include <string.h>
    
    int main() 
    { 
    	char a[101],s[101];
    	int i,len,mid,next,top;
    	
    	gets(a); //读入一行字符串
    	len = strlen(a); //求字符串的长度
    	mid = len/2; //求字符串的中点
    	
    	top=0;//栈的初始化
    	//将mid前的字符依次入栈
    	for(i=0;i<mid;i++)
    		s[top++] = a[i];
    	
    	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标
    	if(len%2==0) { 
    		next = mid;
    	}
    	else { 
    		next = mid+1;
    	}
    	
    	//开始匹配
    	for(i=next;i<len;i++) { 
    		if(a[i]!=s[top-1]) { 
    			break;
    		}
    		top--;
    	}
    	
    	//如果top的值为0，则说明栈内所有的字符都被一一匹配了
    	if(top==0) { 
    		printf("YES");
    	}
    	else { 
    		printf("NO");
    	}
    	
    	getchar();getchar();
    	return 0;
    }

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

--------------------

### C++ STL 库中的栈Stacks ###

The C++ Stack is a container adapter that gives the programmer the functionality of a stack – specifically, a FILO (first-in, last-out) data structure.

>   C++堆栈是一个容器适配器，它为程序员提供了堆栈的功能——具体地说，是FILO（先入，后出）数据结构。

<table> 
 <thead> 
  <tr> 
   <th>序号</th> 
   <th>函数</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td><code>top()</code></td> 
   <td>返回堆栈的顶部元素</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td><code>pop()</code></td> 
   <td>删除堆栈的顶部元素</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td><code>push()</code></td> 
   <td>将元素添加到堆栈顶部</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td><code>size()</code></td> 
   <td>返回堆栈中元素的个数</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td><code>empty()</code></td> 
   <td>如果堆栈空则返回真</td> 
  </tr> 
 </tbody> 
</table>

函数可分为以下几类：

1.  `top()`
2.  `pop()` `push()`
3.  `size()` `empty()`

#### 1. 整体应用 ####

#include <iostream>
    #include <stack> 
    using namespace std;
    
    int main()
    { 
    	stack<int> s;	//定义堆栈
    	s.push(3);		//向堆栈添加数
    	s.push(4);		//向堆栈添加数
    	s.push(5);		//向堆栈添加数
    	s.push(6);		//向堆栈添加数
    	s.pop();		//从堆栈取出数
    	
    	cout << "s.top() = " << s.top() << endl;		
    	cout << "s.size() = " << s.size() << endl;			
    	cout << "s.empty() = " << s.empty() << endl;	
    	return 0;
    }

![在这里插入图片描述][20210407184351107.png]

#### 2. 用C++ 解决需求 ####

#include <iostream>
    #include <stack> 
    #include <string>
    using namespace std;
    
    int main()
    { 
    	stack<char> s;
    	string str; 
    	
    	cin >> str; 			//读入一行字符串
    	int len = str.length(); //求字符串的长度
    	int mid = len/2; 		//求字符串的中点 
    	
    	//将mid前的字符依次入栈
    	for(char i=0; i<mid; i++)
    		s.push(str[i]);
    		
    	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标
    	int next = (len%2==0 ? mid : mid+1);
    
    	//开始匹配
    	for(char i=next; i<len; i++) 
    	{ 
    		if(str[i]!=s.top()) 
    		{ 
    			break;
    		}
    		s.pop();
    	}
    	
    	//如果堆栈为空，则说明栈内所有的字符都被一一匹配了
    	if(s.empty())
    	{ 
    		cout << "YES";
    	}
    	else 
    	{ 
    		cout << "NO";
    	}
    	
    	return 0;
    }

![在这里插入图片描述][20210407185510100.png]  
![在这里插入图片描述][20210407185540937.png]

### 附录：配对括号 ###

现在来解决本文前面所提到的配对括号的问题：输入一行只包含“`()[]{}`”的字符串，请判断形如“`([{}()])`”或者“`{()[]{}}`”的是否可以正确匹配。显然上面两个例子都是可以正确匹配的。“`([)]`”是不能匹配的。

#include <iostream>
    #include <stack> 
    #include <string>
    using namespace std;
    
    //定义括号字典 
    string strbook("(){}[]");
    
    int main()
    { 
    	stack<char> s;		//建立堆栈 
    	string str;			 
    	cin >> str;			//获取输入的字符串 
    	
    	//使用迭代器对输入的字符串遍历 
    	for(string::iterator it=str.begin(); it!=str.end(); it++)	 
    	{ 
    		//如果堆栈不是空的，才可能存在可以配对的括号 
    		if(!s.empty())
    		{ 
    			//查找当前括号在字典中的位置 
    			size_t fpos = strbook.find(*it);
    			
    			//在字典中的位置为奇数代表是右括号，只有当前括号为右括号才能找到先前压入堆栈的左括号 
    			//因此首先判断是否为右括号，若是，则进行下一步判断，不是则将当前括号入栈
    			//如果是右括号，再判断栈顶是否是与其对应的左括号，若是，则找到配对括号，将左括号出栈，进入下一次循环，不是则将当前括号入栈 
    			if(fpos%2==1 && strbook[fpos-1]==s.top())
    			{ 
    				s.pop();
    				continue;
    			}
    		}
    		
    		//否则，入栈 
    		s.push(*it);
    	}
    	
    	//如果最后堆栈是空的，则说明都以找到了与其配对的括号 
    	if(s.empty())
    	{ 
    		cout << "YES";
    	}
    	else 
    	{ 
    		cout << "NO";
    	}
    	
    	return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43964993/article/details/115446128
[20210407184351107.png]: /images/20221022/d7de1375d15e4a72bfb0cbbfc897b341.png
[20210407185510100.png]: /images/20221022/1203a4b2e8364f51b5bad4b10a0d974e.png
[20210407185540937.png]: /images/20221022/40228d394494471e856b0193afc0aef7.png