括号匹配问题源代码(C语言)
- 格式:docx
- 大小:40.48 KB
- 文档页数:4
先按顺序取出所有的括号.然后循环删除_相邻的_差为一或二的_点.最后如果表空则匹配.单向链表:#include <stdio.h>#include <string.h>#include <stdlib.h>#define LEN 80typedef struct list{char node;struct list* next;}list,*plist;void iniList(plist);int isEmpty(plist);int listAppend(plist,char);int delBracketsFormList(plist);int main(int argc,char* argv[]){char test[LEN];int i;list a;plist p;p=&a;iniList(p);scanf("%80s",test);for (i=0;i<LEN;i++){switch(test[i]){case '[': case']': case'{': case'}': case'(': case')':listAppend(p,test[i]);break;default:continue;}}delBracketsFormList(p);if (isEmpty(p)){printf("括号匹配!\n");}elseprintf("括号不配对!\n");return 0;}void iniList(plist aplist){aplist->next=NULL;aplist->node='\0';}int isEmpty(plist aplist){return aplist->next==NULL?1:0; }int listAppend(plist aplist,char a){ plist bplist=aplist,anode;while (bplist->next){bplist=bplist->next;}anode=(plist)malloc(sizeof(list));if (!anode)exit(-1);anode->node=a;anode->next=NULL;bplist->next=anode;return 0;}int delBracketsFormList(plist aplist){plist temp;int has=1;if (isEmpty(aplist))return 0;while(has){has=0;temp=aplist;while (temp->next){if(temp->next->next){if((temp->next->next->node - temp->next->node == 1)||(temp->next->next->node - temp->next->node == 2)){temp->next = temp->next->next->next;has=1;}elsetemp = temp->next;}elsetemp =temp->next;if(!has)break;}}return 0; }。
括号匹配性检测C语⾔实现#include <stdio.h>#define SIMPLE_KUOHAO "(()1231qeqw)(@#$)"#define COMPLEX_KUOHAO "{(()[asd])}{{{{(((())))}}}}"int main(int argc, const char * argv[]){/*问题描述:假设⼀个算术表达式中可以包含三种括号:圆括号"(" 和")",⽅括号"["和"]"和花括号"{"和"}",且这三种括号可按任意的次序嵌套使⽤(如:…[…{…}…[…]…]…[…]…(…)…)。
编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存⼊数据元素为字符的顺序表中)。
思路分析:检验括号是否匹配的⽅法可以⽤“期待的急迫程度”这个概念来描述。
例如,考虑下列括号序列: [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 当计算机接受了第⼀个括号后,它期待着与其匹配的第⼋个括号的出现,然⽽等来的却是第⼆个括号,此时第⼀个括号“[”只能暂时靠边,⽽迫切等待与第⼆个括号相匹配的、第七个括号“)”的出现,类似地,因等来的是第三个括号“[”,其期待匹配的程度较第⼆个括号更急迫,则第⼆个括号也只能靠边,让位于第三个括号,显然第⼆个括号的期待急迫性⾼于第⼀个括号;在接受了第四个括号之后,第三个括号的期待得到满⾜,消解之后,第⼆个括号的期待匹配就成为当前最急迫的任务了,……依此类推。
很显然,这样的⼀个处理过程和栈的特点⾮常吻合,因此,这个问题可以⽤栈来解决。
解决思路: 1.在算法中设置⼀个栈,每次读⼊⼀个括号; 2.若是右括号,则或者使置于栈顶的最急迫的期待得以消解,此时将栈顶的左括号弹出;或者是不合法的情况,此时将右括号压⼊; 3.若是左括号,则作为⼀个新的更急迫的期待压⼊栈中,⾃然使原有的在栈中的所有未消解的期待的急迫性都降低⼀级; 4.在算法的开始和结束时,栈应该为空。
#include<stdio.h>#include<stdlib.h>typedef struct SNode{char data;struct SNode *next;}SNode,*Stack;typedef struct{Stack top;int length;}SqStack;//定义链式栈的结构体char InitStack(SqStack &S){S.top=NULL;S.length=0;return 0;}//初始化链式栈char Push(SqStack &S,char e) {Stack p;p=(Stack)malloc(sizeof(SNode)); if(!p)exit(0); p->data=e;p->next=S.top;S.top=p;S.length++;return 0;}//插入元素echar Pop(SqStack &S){if(!S.top)return 0;else{Stack q;q=S.top;S.top=S.top->next; --S.length;free(q);}return 0;}//删除栈顶元素echar main(){SqStack S;char w,e;InitStack(S);//初始化链式栈printf("提示:输入“ = ”表示输入表达式结束,程序将自动检查括号是否匹配\n\n\n");printf("请输入表达式:\n\n\n");scanf("%c",&w);printf("\n");printf("\n");while(w!='='){switch(w){case '(': Push(S,w);break;case '[': Push(S,w);break;case ')': if(!S.top)return 0;elsee=S.top->data; if(e=='(')Pop(S); break;case ']': if(!S.top)return 0;elsee=S.top->data; if(e=='[')Pop(S); break;default: break;}scanf("%c",&w);}if(S.top==NULL)printf("输入括号匹配\n");else printf("输入括号不匹配,请检查后重新输入\n");return 0;}。
数据结构括号匹配问题#include<stdio.h>#include<stdlib.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INEEASLIBE -1#define OVERFLOW -2typedef int status;typedef char elemtype;typedef struct{elemtype *data;int length;elemtype *top;}list;status creat(list &L){L.data=(elemtype*)malloc(2*sizeof(elemtype));if(!L.data){return ERROR;}L.top=L.data;L.length=1;return OK;}status push(list &L,elemtype e){elemtype *dat;dat=(elemtype*)realloc(L.data,(L.length+1)*sizeof(elemtype));if(!dat){return ERROR;}L.data=dat;L.length++;*(L.top)=e;L.top++;return OK;}status pop(list &L,elemtype &e){if(L.top==L.data){printf("\n已是堆低无数据元素\n");return ERROR;}L.top--;e=*(L.top);return OK;}main(){list L;creat(L);char a[20],b;int i=0,m=0;while(i<20){printf("请输入括号序列:('#'表示输入结束)\n");scanf("%c",&a[i]);getchar();if(a[i]=='#'){break;}if(a[i]=='('||a[i]==')'||a[i]=='['||a[i]==']'||a[i]=='{'||a[i]=='}'||a[i]== '<'||a[i]=='>'){i++;}else{printf("输入的不是括号字符\n请重新输入\n");}}m=i;i=0;while(i<m){if(a[i]==']'||a[i]==')'||a[i]=='}'){if(L.top==L.data){printf("括号匹配出错\n");exit(0);}else{pop(L,b);if((a[i]-b)!=2&&(a[i]-b)!=1){printf("括号匹配出错\n");exit(0);}}}elsepush(L,a[i]);i++;}if(L.data!=L.top)printf("括号匹配出错\n");elseprintf("\n\n括号匹配成功\n");}THANKS !!!致力为企业和个人提供合同协议,策划案计划书,学习课件等等打造全网一站式需求欢迎您的下载,资料仅供参考。
●实验内容:利用栈的基本操作,写一个C程序实现检测表达式“@{(a+b)*[c-d]+e}+f”中的括号是否匹配。
●实验目的:掌握栈的操作●提交内容:C语言源代码:#include <stdio.h>#include <string.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType data[MaxSize];int top;}SeqStack;int InitStack(SeqStack *s){s->top=-1;return 1;}int Push(SeqStack *s,ElemType x){if (s->top == MaxSize -1 ){printf("栈已满,不能入栈.\n");return 0;}else{s->top++;s->data[s->top] = x;}return 1;}int Pop(SeqStack *s,ElemType *x) {if (s->top == -1){printf("栈为空,不能出栈.\n");return 0;}else{*x=s->data[s->top];s->top--;}return 1;}int GetTop(SeqStack *s,ElemType *x) {if (s->top == -1){printf("栈为空,不能取值.\n");return 0;}else{*x=s->data[s->top];}return 1;}int IsEmpty(SeqStack *s) {if(s->top==-1)return 1;return 0;}int Check(char str[],int len) {int i;int a=1,b=0;ElemType x;SeqStack s;InitStack(&s);for(i=0;i<len;i++){if(str[i]=='{'){if(IsEmpty(&s)){if(Push(&s,str[i])!=1){a=0;break;}}else{if(GetTop(&s,&x)!=1){a=0;break;}if(x=='{' || x=='[' || x== '('){a=0;break;}else{if(Push(&s,str[i])!=1){a=0;break;}}}}else if(str[i]=='['){if(IsEmpty(&s)){if(Push(&s,str[i])!=1){a=0;break;}}else{if(GetTop(&s,&x)!=1){a=0;break;}if(x=='[' || x== '('){a=0;break;}else{if(Push(&s,str[i])!=1){a=0;break;}}}}else if(str[i]=='('){if(Push(&s,str[i])!=1){a=0;break;}b=1;}else if(str[i]==')'){if(Pop(&s,&x)!=1){a=0;break;}if(x!='('){a=0;break;}}else if(str[i]==']'){if(Pop(&s,&x)!=1){a=0;break;}if(x!='['){a=0;break;}if(b==0){a=0;break;}}else if(str[i]=='}'){if(Pop(&s,&x)!=1){a=0;break;}if(x!='{'){a=0;break;}if(b==0){a=0;break;}}elsecontinue;}if(!IsEmpty(&s))a=0;return a;}int main(){char str[MaxSize];int i,len;printf("输入字符串:\n");gets(str);len=strlen(str);if(Check(str,len)==0)printf("匹配合法\n");elseprintf("匹配不合法\n");。
括号匹配问题就是给定任意判别式,然后检验括号的配对出现的情况。
可见输入的表达式有四种可能性:右括号配对次序不正确、右括号多于左括号、左括号多于右括号、左右括号匹配正确。
可以先检测表达式中的字符,若是左括号就入栈,如果是右括号就出栈一个元素与其配对,配对成功则继续访问下一个字符,否则退出。
出现非括号字符则跳过。
程序流程图如下:
程序代码如下:
#include<iostream>
#include<string>
#include<process.h>
#include<stdlib.h>
#define MaxSize 50
using namespace std;
/*------------主要的数据结构类型 --------------*/
struct Text
{
int top;
char Szstack[MaxSize];
};
/*-------------程序功能模块函数-------------*/
//检验栈是否为空
bool IsEmpty(Text G)
{
if(G.top==-1)
return true;
else
return false;
}
//检验栈是否为满
bool IsFull(Text G)
{
if(G.top==MaxSize-1)
return true;
else
return false;
}
//弹出栈顶元素
char Pop(Text G)
{
char n=G.Szstack[G.top];
return n;
}
//检验括号是否配对
int Check(char *A)
{
int i;
Text G;
G.top=-1;
int L=strlen(A);
char c;
for(i=0;i<L;i++)
{
c=A[i];
switch(c)
{
case'(':
G.Szstack[++(G.top)]=c;
cout<<" 压入 ( top="<<G.top<<endl;
break;
case'[':
G.Szstack[++(G.top)]=c;
cout<<" 压入 [ top="<<G.top<<endl;
break;
case'{':
G.Szstack[++(G.top)]=c;
cout<<" 压入 { top="<<G.top<<endl;
break;
case')':
if(Pop(G)!='(')
{
return 0;
}
else
{
G.Szstack[G.top--];
cout<<" 当遇 ) 出栈 ( top="<<G.top<<endl; break;
}
case']':
if(Pop(G)!='[')
return 0;
else
{
G.Szstack[G.top--];
cout<<" 当遇 ] 出栈 [ top="<<G.top<<endl; break;
}
case'}':
if(Pop(G)!='{')
return 0;
else
{
G.Szstack[G.top--];
cout<<" 当遇 } 出栈 { top="<<G.top<<endl;
break;
}
default:break;
}
}
if(!IsEmpty(G))
return 0;
return 1;
}
/*-------------主函数-------------*/
int main()
{
system("color 75"); //设置颜色以美观
Text G;
char A[MaxSize];
cout<<"请输入需要检验的括号(括号数小于50):"<<endl;
cin>>A;
if(Check(A)==1)
{
cout<<" -----括号匹配-----"<<endl;
}
else
{
cout<<endl<<endl<<" -----括号不匹配-----"<<endl<<endl<<endl;
}
return 0;
}
以下分别是括号匹配与不匹配时的程序运行结果图:。