字符串括号匹配(创新工场)
参考网址:http://cnlox.is-programmer.com/posts/21860.html
给定一个字符串,字符串中可能含有包含'(', ')', '[', ']',判定条件如下:
- '('和')'、'['和']'个数相等
- '('和')','['和']'完全配对,不能出现嵌套情况。
如符合以上两条,则返回True,否则返回False。
Example:
a(ab)[aa(ba)[aa]b]为True,而a((a)、ab(a[bbb)]c为False。
思路:
设定两个计数器m和n,m记录'('和')'的个数的差值,'n'记录'['和']'个数的差值,再设定stack。每当读到'('或'[',就执行push操作push('('),push('['),同时m++, n++;每当读到')'或']',就判断下栈顶元素和当前元素是否配对,如果配对,则pop(),否则直接返回False,同时m--,n--。最后判断m和n是否为零即可。
涉及的函数包括初始化栈、判断栈空、入栈、出栈、求栈顶元素
首先定义栈结构体
typedef struct stackqueue
{
char sign[maxsize];
int top;
}queue;
初始化栈
int InitStack(stackqueue &ss)
{
ss.top = -1;
return 1;
}
判栈空
int IsEmptyStack(stackqueue &ss)
{
if(ss.top == -1)
return 1;
return 0;
}
入栈
int Push(stackqueue &ss,char c)
{
ss.sign[++ss.top]=c;
return 1;
}
出栈
int Pop(stackqueue &ss)
{
if(IsEmptyStack(ss)){cout<<"栈空"<<endl;return 0;}
ss.top--;
return 1;
}
返回栈顶
char TopsStack(stackqueue &ss)
{
if(IsEmptyStack (ss)){cout <<"栈空"<<endl;return 0;}
return ss.sign[ss.top];
}
主函数int _tmain(int argc, _TCHAR* argv[])
{
/*char a[] = "a(ab)[aa(ba)[aa]b]";
char b[] = "ab(a[bbb)]c";
int length = strlen(a);
char s[100] = "0";
strcpy(s,b);*/
char s[100] = "0";
cout<<"输入表达式"<<endl;
cin.getline(s,100);
int length = strlen(s);
int m = 0, n = 0;
stackqueue ss;
InitStack(ss);
for(int i=0;i<length;i++)
{
if(s[i]=='(')
{
Push(ss,s[i]);
m++;
}
else if(s[i]=='[')
{
Push(ss,s[i]);
n++;
}
else if(s[i]==')'&&!IsEmptyStack(ss)&&TopsStack(ss)=='(')
{
Pop(ss);
m--;
}
else if(s[i]==')'&&!IsEmptyStack(ss)&&TopsStack(ss)!='(')
{
cout<<"()括号匹配次序不正确"<<endl;
}
else if(s[i]==']'&&!IsEmptyStack(ss)&&TopsStack(ss)=='[')
{
Pop(ss);
n--;
}
else if(s[i]==']'&&!IsEmptyStack(ss)&&TopsStack(ss)!='[')
{
cout<<"[]括号匹配次序不正确"<<endl;
}
else if((s[i]==')'||s[i]==']')&&IsEmptyStack(ss))
cout<<"右括号多于左括号"<<endl;
}
if(m!= 0 || n!= 0)
cout<<"不匹配";
else
cout<<"匹配"<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
本程序时对一个字符串,判断其中括号(小,中,大括号)是否匹配
字符串处理 时间限制 2S 内存限制 1000Kb 问题描述 表达式中的合法括号为“(”、“)”、“[”、“]”、“{”、“}”,这三种括号可以按照任意的次序嵌套使用。 请写一个程序,判断给定表达式中的括号...
自己做的,能用栈实现括号匹配,程序很简单实用
给定一个字符串,其中的字符只包含三种...括号匹配要求括号必须以正确的顺序配对,如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式,而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。
数据结构括号匹配程序c语言试验程序,实现括号自动匹配,支持文件操作20字符以内文件名。
1.(),[]是括号匹配的字符串 2.若A是括号匹配的串,则(A),[A]是括号匹配的字符串 3.若A,B是括号匹配的字符串,则AB也是括号匹配的字符串
栈判断 括号是否匹配栈判断 括号是否匹配栈判断 括号是否匹配
括号匹配问题
要求查找string_in中和短字符串的所有匹配,输入行号、匹配字段到string_out中。匹配不区分大小写,并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”,就是说aa1bb、aa2bb、aa3bb都算匹配。
C#版的检测括号是否匹配的问题,可以检测出从键盘输入的一串字符,其中有字母、数字和其它一些特殊符号,这一串字符中有小括号,中括号,通过本程序,可以判断出输入入的字符串中的小、中括号是否匹配,是缺少左小、...
输入一包含(和)的字符串,检测括号是否匹配(其中括号能嵌套括号),并输出括号是否匹配的信息(匹配,缺少左括号,缺少右括号)。
对输入的带括号的字符串进行括号匹配,能匹配()【】{},输出是否匹配
字符串工具箱、文本分析、标签提取、括号匹配、自定义字符匹配、大括号匹配、花括号匹配、方括号匹配、自定义配对符、语法检测、代码解析、脚本解析、公式解析、Json解码、xml解码
假设一个算术表达式中包括圆括号、方括号和花括号三种形式的括号,判别表达式中括号是否正确配对。 ...1、左右括号匹配正确 2、左右括号配对次序不正确; 3、右括号多于左括号 4、左括号多于右括号
任意输入一个由若干个圆括号、方括号和花括号组成字符串,设计一个算法判断该串中的括号是否配对。
小括号():匹配小括号内的字符串,可以是一个,也可以是多个,常跟“|”(或)符号搭配使用,是多选结构的 示例1:string name = “way2014”; regex:(way|zgw) result:结果是可以匹配出way的,因为是多选结构...
括号匹配:判断一段字符串括号是否匹配,就是左括号是否与右括号搭配,且括号类型要相同,且有空字符串,括号套括号等特殊情况。
本文实例讲述了Python实现求解括号匹配问题的方法。分享给大家供大家参考,具体如下: 这个在本科学习数据结构的时候已经接触很多了,主流的思想是借助栈的压入、弹出来进行匹配,至于python的话可以使用列表来完成...
C语言括号匹配问题解决方法,给定一个输入的字符串,包含括号(和),能够找出(和)的个数,并指出(或者)不正确的位置。
数据结构 c++ 链接栈+顺序对:括号匹配 数据结构 c++ 链接栈+顺序对:括号匹配