数据结构代码集训day14（适合考研、自学、期末和专升本）
题目均来自b站up：白话拆解数据结构！
今日题目如下：
（1）试写一个算法判断给定字符序列是否是回文。
（2）给定一个算法判断输入的表达式中括号是否匹配。假设只有花、中、尖三种括号。
题1
回文序列即正着读反着读，都是一样的。比如abba就是回文序列，abab就不是。
由于要反着读，能够很容易想到一种线性结构——栈。栈后进先出，很容易实现输入序列的反序，其实将字符串存进数组或者链表里面反转一下也能做。这里扩充一下用栈的做法。
我们将字符序列用字符数组存起来，然后将数组的前半部分入栈，然后依次出栈和数组的后半部分依次比较，全部相等就是回文序列，否则就不是。
此处偷懒，不定义栈的结构体了，直接调用库<stack>就行了。注意如果字符串是奇数，就跳过这个，因为ababa中间的a正反着读都在原位置，这个元素就没用。
bool huiwen(char s[]) {
if (s[0] == '\0') {
cout << "false" << endl;
return false;
}
stack<char> t; // 初始化一个栈
int len = strlen(s);
// 将前半部分字符压入栈中
for (int i = 0; i < len / 2; ++i) {
t.push(s[i]); // 入栈
}
// 如果字符串长度为奇数，跳过中间的字符
int start = (len % 2 == 0) ? len / 2 : len / 2 + 1;
// 比较后半部分字符和栈顶字符
for (int i = start; i < len; ++i) {
if (t.top() != s[i]) {
cout << "wu huiwen" << endl;
return false;
}
t.pop(); // 出栈
}
cout << "have huiwen" << endl;
return true;
}
实践一下：
输入aabaa
输入aabaac
完整代码如下：
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
// 判断给定字符序列是否是回文
bool huiwen(char s[]) {
if (s[0] == '\0') {
cout << "false" << endl;
return false;
}
stack<char> t;
int len = strlen(s);
// 将前半部分字符压入栈中
for (int i = 0; i < len / 2; ++i) {
t.push(s[i]);
}
// 如果字符串长度为奇数，跳过中间的字符
int start = (len % 2 == 0) ? len / 2 : len / 2 + 1;
// 比较后半部分字符和栈顶字符
for (int i = start; i < len; ++i) {
if (t.top() != s[i]) {
cout << "wu huiwen" << endl;
return false;
}
t.pop();
}
cout << "have huiwen" << endl;
return true;
}
int main(){
char s[]="aabaac";
huiwen(s);
return 0;
}题2
就是括号匹配，遇到左括号就入栈，在左括号入栈后继续判断右括号是否匹配，如果匹配就全部出栈。
bool pipei(char s[]){
stack<char> t;
int len = strlen(s);
for (int i = 0; i < len ; i++) {
if(s[i]=='{'||s[i]=='('||s[i]=='<'){ // 入栈左括号
t.push(s[i]);
}
else if (s[i] == '}' || s[i] == ')' || s[i] == '>') {
if (t.empty()) {
// 栈为空，说明没有匹配的左括号
cout << "bu pi pei\n";
return false;
}
char top = t.top(); // 暂存栈顶元素，用来匹配
t.pop();
// 检查是否匹配
if ((s[i] == '}' && top != '{') ||(s[i] == ')' && top != '(') ||(s[i] == '>' && top != '<')) {
cout << "bu pi pei\n";
return false;
}
}
}
if (t.empty()){ // 栈空了，意味着全部匹配出栈了
printf("pi pei\n");
}
else printf("bu pi pei\n");
return true;
}
实践：
(ab<cd>{<ed>()})
(ab<cd>{<ed>(})
完整代码如下：
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
// 判断括号匹配
bool pipei(char s[]){
stack<char> t;
int len = strlen(s);
for (int i = 0; i < len ; i++) {
if(s[i]=='{'||s[i]=='('||s[i]=='<'){
t.push(s[i]);
}
else if (s[i] == '}' || s[i] == ')' || s[i] == '>') {
if (t.empty()) {
// 栈为空，说明没有匹配的左括号
cout << "bu pi pei\n";
return false;
}
char top = t.top();
t.pop();
// 检查是否匹配
if ((s[i] == '}' && top != '{') ||(s[i] == ')' && top != '(') ||(s[i] == '>' && top != '<')) {
cout << "bu pi pei\n";
return false;
}
}
}
if (t.empty()){
printf("pi pei\n");
}
else printf("bu pi pei\n");
return true;
}
int main(){
char s[]="(ab<cd>{<ed>(})";
pipei(s);
return 0;
}