开发者社区> 华山青竹> 正文

OpenJudge计算概论-扩号匹配问题【这个用到了栈的思想】

简介: /*====================================================================== 扩号匹配问题 总时间限制: 1000ms 内存限制: 65536kB 描述 在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。
+关注继续查看
/*======================================================================
扩号匹配问题
总时间限制: 1000ms 内存限制: 65536kB
描述
在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
输入
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100
注意:cin.getline(str,100)最多只能输入99个字符!
输出
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。
样例输入
((ABCD(x)
)(rttyy())sss)(
样例输出
((ABCD(x)
$$
)(rttyy())sss)(
?            ?$

思路:
输入一组数据后(一个字符串,这里输入到数组a),先输出数组a
统计数组a的长度len,设置数组b代表的栈的栈顶end指向0. (注意把end清零) 
然后扫描检测数组a,遇到左括号之间进栈(数组b代表的栈的元素存储进栈的
那个字符以及该字符在字符串a中的下标。)遇到右括号则按下面法则处理:
假如数组b代表的栈是空的(即end为0),则右括号进栈。
假如b不是空的(end大于0),则检测栈顶元素(下标是end-1)
是否是左括号,如果刚好是左括号则该栈顶元素出栈(end自己减1),
假如栈顶元素(下标是end-1)不是左括号,则该右括号进栈。

注意:这里end是指向栈顶元素的下一个位置。也就是说某一次进栈后end自己加1,
而栈顶元素下标是end-1。

另外:扫描完后,b数组的下标应该是0到end-1.扫描该数组,
按b的每一个元素的num值所指向的a数组的下标对应的元素设置为$或?
然后扫描a数组,假如不是$或?则输出空格,否则输出对应元素的值

 然后处理下一组数据(但是要注意处理下一组数据前要把end清零。) 
========================================================================*/
#include<stdio.h>
#include<string.h>
struct s
{
    char ch;
    int num;
};
int main()
{
    char a[105];
    struct s b[105];
    int i,len;
    int end=0;//指向b数组代表的栈的栈顶 
    freopen("5.in","r",stdin);
    while(scanf("%s",a)!=EOF)
    {
        printf("%s\n",a);
        len=strlen(a);
        end=0;
        for(i=0;i<len;i++)
        {
            if(a[i]=='(')//左括号直接进栈(因为它不可能使栈顶元素出栈的。) 
            {
                b[end].ch=a[i];
                b[end].num=i;
                end++;
            }
            else if(a[i]==')')
            {
                if(end==0)//b数组代表的栈是空的 
                {
                    b[end].ch=a[i];
                    b[end].num=i;
                    end++;
                }
                else
                {
                    if(b[end-1].ch=='(')
                    {
                        end--;
                    }
                    else
                    {
                        b[end].ch=a[i];
                        b[end].num=i;
                        end++;
                    }
                }
            }
        }
        for(i=0;i<end;i++)
        {
            if(b[i].ch=='(')
            {
                a[b[i].num]='$';
            }
            else
            {
                a[b[i].num]='?';
            }
        }
        for(i=0;i<len;i++)
        {
            if(a[i]!='$'&&a[i]!='?')
            {
                printf(" ");
            }
            else printf("%c",a[i]);
        }
        printf("\n");
        /*for(i=0;i<end;i++)
        {
            printf("%c ",b[i].ch);
        }
        printf("\n");
        for(i=0;i<end;i++)
        {
            printf("%d ",b[i].num);
        }
        printf("\n");*/
    }
    return 0;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
C#正则表达式的完全匹配、部分匹配及忽略大小写的问题
原文:C#正则表达式的完全匹配、部分匹配及忽略大小写的问题 问题的提出 根据用户给定表达式,里面含有各种数学函数,如求绝对值,三角函数,平方、开方等,分别以类似ABS(表达式),Sin(表达式),ASin(表达式),POW(表达式)等形式表述。
1616 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28212 0
带你读《OpenCV 4计算机视觉项目实战 (原书第2版)》之二:OpenCV基础知识导论
本书首先介绍OpenCV的入门知识及安装,然后介绍OpenCV的基础知识,包括用户界面、矩阵运算、滤波器和直方图等,之后介绍复杂的计算机视觉算法,包括对象分割和分类、视频监控、对象跟踪等,后探讨对象跟踪、文本识别、机器学习和人脸检测等高级技术。阅读本书之后,你将掌握常用和新的计算机视觉技术,并学会从零开始构建各类OpenCV项目。
4259 0
带你读《OpenCV 4计算机视觉项目实战 (原书第2版)》之三:学习图形用户界面
本书首先介绍OpenCV的入门知识及安装,然后介绍OpenCV的基础知识,包括用户界面、矩阵运算、滤波器和直方图等,之后介绍复杂的计算机视觉算法,包括对象分割和分类、视频监控、对象跟踪等,后探讨对象跟踪、文本识别、机器学习和人脸检测等高级技术。阅读本书之后,你将掌握常用和新的计算机视觉技术,并学会从零开始构建各类OpenCV项目。
2288 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20233 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23540 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载