62 lines
2.0 KiB
C++
62 lines
2.0 KiB
C++
|
// 【场景】栈应用
|
|||
|
|
// 编写一个程序，判断给定的字符串是否是有效的括号序列。例如，对于字符串 "{[()]}"，应返回 true；对于字符串 "{[(])}"，应返回 false。
|
|||
|
|
// 【提示】华为OD的机试题
|
|||
|
|
#include <iostream>
|
|||
|
|
#include <stack>
|
|||
|
|
#include <string>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
bool judge(const string &str)
|
|||
|
|
{
|
|||
|
|
stack<char> stk;
|
|||
|
|
int max_depth = 0;
|
|||
|
|
|
|||
|
|
for (char c : str) // 增强型 for 循环，用于遍历字符串
|
|||
|
|
{
|
|||
|
|
if (c == '(' || c == '[' || c == '{')
|
|||
|
|
{
|
|||
|
|
stk.push(c); // 当左括号出现时，入栈
|
|||
|
|
}
|
|||
|
|
else if (c == ')' || c == ']' || c == '}') // 当碰到右括号时，开始匹配
|
|||
|
|
{
|
|||
|
|
if (stk.empty()) // 如果栈已经为空，说明没有左括号与之匹配
|
|||
|
|
{
|
|||
|
|
return false; // 返回无法匹配
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
char top = stk.top(); // 拿出栈顶元素
|
|||
|
|
|
|||
|
|
if (max_depth < stk.size())
|
|||
|
|
max_depth = stk.size();
|
|||
|
|
|
|||
|
|
stk.pop(); // 弹出栈顶元素
|
|||
|
|
|
|||
|
|
// 判断本次取出的字符与栈顶元素是否匹配，即左右括号是否匹配，不匹配则返回无效，匹配则继续进行下一轮遍历循环
|
|||
|
|
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{'))
|
|||
|
|
{
|
|||
|
|
return false; // 括号不匹配
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
cout << "括号栈的最大深度为: " << max_depth << endl;
|
|||
|
|
return stk.empty(); // 栈为空表示括号完全匹配 = 有效 = true = 1，反之，如果栈非空，说明还有未匹配的左括号，返回无效 = false = 0
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
string print(bool flag)
|
|||
|
|
{
|
|||
|
|
if (flag) // flag 为 true = 1
|
|||
|
|
return "有效";
|
|||
|
|
else
|
|||
|
|
return "无效";
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main()
|
|||
|
|
{
|
|||
|
|
// string str1 = "{[(])}";
|
|||
|
|
// string str1 = "{(])}";
|
|||
|
|
string str1 = "{[(s[s])s]}[][[[[()]]]]";
|
|||
|
|
cout << "括号序列 " << str1 << " 是否有效: " << print(judge(str1)) << endl; // 1
|
|||
|
|
return 0;
|
|||
|
|
}
|