面向3-8岁的幼儿儿童
免费编程入门启蒙网站

全国编程竞赛NOIP试题分析(二)

Part 2

试题二分析

自从小编上次将试题一分析发给大家后,得到各位家长和同学的热情的回馈。小伙伴都催着小编赶紧把第二题的分析发给大家分享。

对于有求必应的小编,当然是满足大家啦。一起来看第二题的分析 。

试题分析(二)
第二题:括号匹配

假设一个表达式有英文字母(小写) 、运算符(+,—,*,/)和左右小(圆)括号构成,以“#”作为表达式的结束符。编写一个程序检查表达式中的左右小圆括号是否匹配,若匹配,则输出“Yes”,否则输出“No” 。表达式长度小于 255 个字符。

【输入格式】

包括一行字符,即表达式。

【输出格式】

一行,即“Yes” 或“No” 。

【输入输出样例】

输入:

a*(x+y)/(x-y)#

输出:

Yes

题目网站链接:

http://go.helloworldroom.com:8072/problem/2491

试题分析(二)
样/例/说/明

最后的#作为表达式的结束符。(x+y)左右小圆括号匹配,(x-y)括号也匹配,所以输出为Yes

试题分析(二)
试题分析(二)
很多同学都说第二题在网站提交时一直得不到满分,自己也知道算法不够完美,对于有些输入数据输出结果不正确是意料之中的事。但如何解决却也一头雾水。

再分析第二题之前,我们先了解一个概念——堆栈!

计算机领域,堆栈是一个不容忽视的概念。堆栈是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。

判断括号使用是否符合规范是非常经典的利用堆栈算法的相关应用。

试题分析(二)
对应第二题,由于题目已知输入是一串字符串。所有,我们首先定义一个字符串变量,将包含括号的字符串存入到该变量中。

string s;

cin>>s;

我们都知道括号是成双成对的,不可能有单个的括号。所以,要判断它是否匹配,是否符合条件,只需要判断有没有和它相对应的符号即可。例如:

3*(x+y)中'(‘ 对应 ‘)’,此时需要程序输出”Yes”

x*(x/(a+b) 中外层'(‘ 没有 ‘)’对应,此时需要程序输出”No”

由于输入的字符串表达式已经存放到字符串变量中了。因此,我们可以使用循环遍历字符串,如果出现了 ‘(‘ ,可以让它进栈(用一个变量记录'(‘的个数);若是出现相对应的’)’符号,则让它出栈(将变量的数值减一)。

在该题中,以“#”作为表达式的结束符。

for(int i=0; i<s.length(); i++){

if(s[i]=='(‘)

j++;

else if(s[i]==’)’)

j–;

else if(s[i]==’#’)

break;

}

最后,我们判断括号匹配与否只需要判断变量j是否为数值0即可。

if(j==0)

cout<<“Yes”;

else

cout<<“No”;

试题分析(二)
怎么样?同学们是不是都已经有了编程思路了呢?小编这里也特别贴心的为大家写出完整的程序。如果还有疑问,可以留言咨询哦。

试题分析(二)
我们少儿编程的冬令营C++入门班正在招生哦!想让你的假期更有意义更充实吗?想更多了解C++这门语言吗?快来报名参加吧!还有更多冬令营课程等你来体验哦。

每周六,周日上午10:00都有冬令营相关课程的免费试听课!快来预约报名吧!

试题分析(二)
helloworld少儿编程

电话:17361882359

地址:南京市玄武区仙鹤新天地广场2栋-302

欢迎来电咨询,还可以预约试听噢!

分享到: 更多 (0)