给定一个字符串str,设计一个算法,采用顺序栈判断str是否为形如“序列1@序列2”的合法字符串,其中序列2是序列1的逆序,在str中恰好只有一个@字符。求完整c++代码
时间: 2024-10-20 21:16:00 浏览: 35
为了判断给定的字符串 `str` 是否满足题目描述的要求,你可以编写一个 C++ 程序,使用栈的数据结构来处理这个问题。以下是完整的代码实现:
```cpp
#include <iostream>
#include <string>
#include <stack>
bool isValidString(const std::string& str) {
std::stack<int> sequence;
int prev_char = -1;
for (char c : str) {
if (c == '@') { // 找到 '@' 符号,检查前一字符是否为 '>'
if (!sequence.empty() && sequence.top() != prev_char + 1) {
return false; // 如果不是连续的递增序列,返回 false
}
if (sequence.size() > 1) {
return false; // 如果序列超过两个元素,说明这不是逆序对
}
prev_char = -1; // 清空当前序列并更新上一个字符为 -1
} else if (c >= '0' && c <= '9') { // 字符是数字,加入序列
sequence.push(c - '0');
prev_char = c; // 更新上一个字符
} else {
return false; // 非数字字符,直接返回错误
}
}
// 判断最后一个字符是否形成逆序对
if (!sequence.empty()) {
return sequence.top() == prev_char + 1;
}
return true; // 如果循环结束,表示字符串符合规则
}
int main() {
std::string test_str1 = "12@34";
std::string test_str2 = "1@234";
std::string test_str3 = "123@456";
std::cout << "Test string 1 is valid? " << (isValidString(test_str1) ? "Yes" : "No") << std::endl;
std::cout << "Test string 2 is valid? " << (isValidString(test_str2) ? "Yes" : "No") << std::endl;
std::cout << "Test string 3 is valid? " << (isValidString(test_str3) ? "Yes" : "No") << std::endl;
return 0;
}
```
这个程序首先初始化一个栈,然后遍历输入字符串的每个字符。当遇到数字字符时,将其转换为整数并推入栈。如果遇到 "@" 符号,检查栈顶元素与上一个非 "@”字符的关系。最后,检查是否仅有一个 "@" 符号,并且栈中最后一个数字字符的值是其对应位置的倒数。
阅读全文