人民日报客户端是什么级别的媒体_湛江seo咨询_seo网站推广是什么意思_怎么做网站链接

头歌实训：括号是否匹配

任务描述

本关任务：给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。

相关知识

为了完成本关任务，你需要掌握：1.栈的基本特性和操作，2.C++ 标准模板库（STL）中的容器栈（stack）的基本操作。

1. 栈的基本特性和操作

本关提供一个顺序栈SqStack的基本运算及其实现，你可以调用其有关函数完成指定操作。各函数详细功能请参见代码目录中的sqstack.h头文件，基本操作如下：

//初始化顺序栈
void InitStack(SqStack *&s);
//判断栈空否
bool StackEmpty(SqStack *s);
//进栈
bool Push(SqStack *&s, ElemType e);
//出栈
bool Pop(SqStack *&s, ElemType &e);
//取栈顶元素
bool GetTop(SqStack *s, ElemType &e);

2. C++ STL中的栈（stack）

stack翻译为栈，是STL中一个后进先出（Last In First Out，LIFO）的一个容器。
如果要使用stack，需要添加stack头文件，#include 。除此之外，还需要在头文件下面加上一句：“using namespace std;”，这样就可以在代码中使用stack了。下面来看stack 的一些常用用法。

2.1 stack的定义

定义一个stack的语法如下，其中typename可以是任意基本数据类型或容器，stack_name为容器对象名称:

stack stack_name;
//例如：
stack st1; //定义一个名称为st1存放int型数据的栈
stack st2; //定义一个名称为st2存放char型数据的栈
stack st3; //定义一个名称为st3存放string型数据的栈

2.2 stack容器内元素的访问

由于栈（stack）本身就是一种后进先出的数据结构，因此在STL中只能通过pop()来访问栈顶元素。
示例如下：

#include <stdio.h>
#include
using namespace std;
int main() {
stack st;
for (int i = 1; i <= 5; i++) {
st.push(i); //push(i)将元素入栈,因此1 2 3 4 5依次入栈
}
printf(“%d\n”, st.top()); //访问栈顶元素
return 0;
}
程序运行后，栈中元素如下图所示：

程序输出结果：
5

2.3. stack常用函数实例解析

(1) push()
push(x)将x入栈，时间复杂度为O(1)。
(2) top()
top()获取栈顶元素，时间复杂度O(1)。
(3) pop()
pop()弹出栈顶元素，时间复杂度为O(1)。
示例如下：

#include <stdio.h>
#include
using namespace std;
int main() {
stack st;
for (int i = 1; i <= 5; i++) {
st.push(i); //将1 2 3 4 5依次入栈
}
for (int i = 1; i <= 3; i++) {
st.pop(); //连续三次将栈顶元素出栈,即5 4 3依次出栈
}
printf(“%d\n”, st.top()); //访问栈顶元素
return 0;
}
输出结果：
2
(4) empty()
empty()检测stack是否为空，为空则返回true，非空则返回false。复杂度为O(1)。
示例如下：

#include <stdio.h>
#include
using namespace std;
int main() {
stack st;
if (st.empty() == true) { //一开始栈内没有元素,所以是空
printf(“Empty\n”);
} else {
printf(“Not empty\n”);
}
st.push(1);
if (st.empty() == true) { //入栈“1”后,栈非空
printf(“Empty\n”);
} else {
printf(“Not empty\n”);
}
return 0;
}
输出结果：
Empty
Not empty

(5) size()
size()返回stack内元素的个数，复杂度为O(1)。
示例如下：

#include <stdio.h>
#include
using namespace std;
int main() {
stack q;
for (int i = 1; i <= 5; i++) {
q.push(i); //push(i)用来将i入栈
}
printf(“%d\n”, q.size()); //栈中有5个元素
return 0;
}
输出结果：
5

2.4 stack的常见用途

栈用来模拟实现一些递归，防止程序对栈内存的限制而导致程序出错。一般来说，程序的栈内存空间很小，对有些题目来说，如果用普通的函数来进行递归，一旦递归层数过深（不同的机器不同，一般约几千至几万层），则会导致程序运行崩溃。如果用栈来模拟递归算法的实现，则可以避免这一方面的问题（不过这种应用较少出现）。

2.5 一个完整的stack程序示例

#include
#include
using namespace std;
int main() {
stack st; //定义栈对象st
for (int i = 1; i <= 10; i++) {
st.push(i); //1 2 3 4 5 6 7 8 9 10依次入栈
}
//输出栈的元素个数
cout << st.size() << endl; //10
//输出栈顶元素
cout << st.top() << endl; //10
//输出栈的所有元素
while (!st.empty()) {
int tmp = st.top(); //取栈顶元素
cout << tmp << " "; //输出栈顶元素
st.pop(); //删除栈顶元素
}
cout << endl;
return 0;
}
输出结果：
10
10
10 9 8 7 6 5 4 3 2 1

编程要求

根据提示，在右侧编辑器补充完成函数bool is_valid(char* str)的代码，该函数的功能为判断传入的字符串str中包含的括号是否匹配，如果匹配函数返回true，否则返回false。

测试说明

平台会对你编写的代码进行测试：

测试输入：
sin(10+20)
预期输出：
yes

测试输入：
{}{
预期输出：
no

测试输入：
[ , { ( , . ) [,] } , , ]
预期输出：
yes

开始你的任务吧，祝你成功！

源代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <stack>
using namespace std;#include "sqstack.h" //包含顺序栈基本运算bool is_valid(char* str)
{//请在下面编写代码/*************************Begin*********************/stack<char> st;         //使用c++中的栈定义一个stint i = 0;              //计数器iwhile(str[i] != '\0')   //遍历数组str{if(str[i] == '(' || str[i] == '[' || str[i] == '{') st.push(str[i]); //当字符数组为'('或'['或'{'时入栈if(str[i] == ')')   //当为')'时{if(st.empty()) return false;    //如果栈空返回falseif(st.top() != '(') return false;   //如果栈顶元素不匹配返回falsest.pop();       //将栈顶元素弹出}if(str[i] == ']')       //当为']',同上{if(st.empty()) return false;if(st.top() != '[') return false;st.pop();}if(str[i] == '}')   //当为'}',一样同上{if(st.empty()) return false;if(st.top() != '{') return false;st.pop();}i++;    //计数器向后移}if(st.empty()) return true;         //当遍历完栈空说明匹配返回truereturn false;                       //不返回true那就返回false/**************************End**********************/
}int main(int argc, char const *argv[])
{char exp[1000];fgets(exp, 1000, stdin);bool flag = is_valid(exp);if (flag)printf("yes\n");else printf("no\n");return 0;
}