java括号匹配算法求解（用栈实现）
如何使用栈来判定括号是否匹配
对于给定的表达式，可以使用栈来实现括号匹配判定，这个算法在编译器中非常重要，解析器每次读入
一个字符，如果字符是一个开分隔符，如（，【，{，入栈，若读入的是闭分隔符），】，},出栈，如果两者匹配，继续解析字符串，如果不匹配，解析器错误
算法思路
1.创建一个栈
2.当（当前字符不等于输入的结束字符）
（1）如果当前字符不是匹配的字符，判断栈内是否为空，如果栈为空，括号必然不完整
（2）如果字符是一个开分隔符，那么将其入栈
（3）如果字符是一个闭分隔符，，且栈不为空，则判断是否匹配
（4）栈结束后判断是否为空，不为空则括号匹配错误
代码示例
classSolution{
publicbooleanisValid(Strings){
//声明匹配词典
Mapmap=newHashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
//创建栈
Stackstack=newStack<>();
for(charch:s.toCharArray()){
//开分隔符入栈
if(ch=='('||ch=='['||ch=='{'){
stack.push(ch);
}
//出栈并且栈非空进行匹配
elseif(stack.isEmpty()||stack.pop()!=map.get(ch)){
returnfalse;
}
}
//如果栈非空则括号匹配错误
returnstack.isEmpty();
}
}
下面是其他同学的补充
1.括号匹配算法
//括号匹配算法
publicvoidpipei()throwsException{
chartemp,ch;
intmatch;//记录匹配结果
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
ch=(char)br.read();//输入一个字符
while(ch!='0'){
if(getTop()==-1){
push(ch);
}else{
temp=pop();//取出栈顶元素
match=0;//判断是否匹配（默认不匹配）
if(temp=='('&&ch==')')
match=1;
if(temp=='['&&ch==']')
match=1;
if(temp=='{'&&ch=='}')
match=1;
if(temp=='<'&&ch=='>')
match=1;
if(match==0){//如果不匹配
push(temp);//将原栈顶元素重新入栈
push(ch);//将输入的括号字符入栈
}
}
ch=(char)br.read();//输入下一个字符
}
if(isEmpty()){
System.out.println("输入的括号完全匹配！");
}else{
System.out.println("输入的括号不匹配，请检查！");
}
}
2.括号匹配求解示例
packagecom.cn.datastruct;
importjava.io.BufferedReader;
importjava.io.InputStreamReader;
importjava.util.Scanner;
publicclassKuoHaoPiPei{
staticclassStack{
char[]data;//存放数据
intMaxSize;//最大容量
inttop;//栈顶指针
//构造方法
publicStack(intMaxSize){
this.MaxSize=MaxSize;
data=newchar[MaxSize];
top=-1;
}
publicintgetMaxSize(){
returnMaxSize;
}
publicintgetTop(){
returntop;
}
publicbooleanisEmpty(){
returntop==-1;
}
publicbooleanisFull(){
returntop+1==MaxSize;
}
//入栈
publicbooleanpush(chardata){
if(isFull()){
System.out.println("栈已满!");
returnfalse;
}
this.data[++top]=data;
returntrue;
}
//出栈
publiccharpop()throwsException{
if(isEmpty()){
thrownewException("栈已空！");
}
returnthis.data[top--];
}
//获得栈顶元素
publiccharpeek(){
returnthis.data[getTop()];
}
//括号匹配算法
publicvoidpipei()throwsException{
chartemp,ch;
intmatch;//记录匹配结果
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
ch=(char)br.read();//输入一个字符
while(ch!='0'){
if(getTop()==-1){
push(ch);
}else{
temp=pop();//取出栈顶元素
match=0;//判断是否匹配（默认不匹配）
if(temp=='('&&ch==')')
match=1;
if(temp=='['&&ch==']')
match=1;
if(temp=='{'&&ch=='}')
match=1;
if(temp=='<'&&ch=='>')
match=1;
if(match==0){//如果不匹配
push(temp);//将原栈顶元素重新入栈
push(ch);//将输入的括号字符入栈
}
}
ch=(char)br.read();//输入下一个字符
}
if(isEmpty()){
System.out.println("输入的括号完全匹配！");
}else{
System.out.println("输入的括号不匹配，请检查！");
}
}
}
publicstaticvoidmain(String[]args)throwsException{
Stringgo;
Scannerinput=newScanner(System.in);
Stackstack=newStack(20);
System.out.println("括号匹配问题！");
do{
System.out.println("请输入一组括号的组合，以0表示结束。支持的括号包括：{},(),[],<>。");
stack.pipei();//匹配算法
System.out.print("\n继续匹配吗（y/n）?");
go=input.next();
}while(go.equalsIgnoreCase("y"));
System.out.println("匹配结束！");
}
}
程序运行结果如下：
括号匹配问题！
请输入一组括号的组合，以0表示结束。支持的括号包括：{},(),[],<>。
({[]})<>0
输入的括号完全匹配！继续匹配吗（y/n）?y
请输入一组括号的组合，以0表示结束。支持的括号包括：{},(),[],<>。
({])0
输入的括号不匹配，请检查！继续匹配吗（y/n）?n
匹配结束！
补充2
#include#include usingnamespacestd; #defineMAXSIZE20 typedefstruct{ char*base; char*top; intstacksize; }SqStack; voidInitStack(SqStack&S) { S.base=(char*)malloc(MAXSIZE*sizeof(char)); if(S.base==NULL) exit(-2); S.top=S.base; S.stacksize=MAXSIZE; } voidGetTop(SqStackS,char&e) { if(S.top==S.base) return; e=*(S.top-1); } voidPush(SqStack&S,chare) // 不考虑栈满 { *S.top++=e; } voidPop(SqStack&S,char&e) { if(S.top==S.base) return; S.top--; e=*S.top; } boolMatch(charc,SqStack&my_stack,bool&tag) { chare; Pop(my_stack,e); if(c!=e){ tag=false; free(my_stack.base); returnfalse; // matchfail } returntrue; // matchsuccess } voidCorrect(char*expr,bool&tag) { tag=true; SqStackmy_stack; InitStack(my_stack); for(inti=0;expr[i]!='\0';i++){ charc=expr[i]; switch(c){ case'{':case'[':case'(': Push(my_stack,c);break; case'}': if(Match('{',my_stack,tag)==false) // matchfail return; break; case']': if(Match('[',my_stack,tag)==false) // matchfail return; break; case')': if(Match('(',my_stack,tag)==false) // matchfail return; break; default: break; // 其它字符 } } if(my_stack.top!=my_stack.base) //e.g.:"[r" tag=false; free(my_stack.base); } intmain(void) { // freopen("cin.txt","r",stdin); charmy_expr[MAXSIZE]; while(cin>>my_expr){ booltag=true; Correct(my_expr,tag); tag?printf("匹配成功\n"):printf("匹配失败\n"); } return0; }
到此这篇关于java括号匹配算法求解（用栈实现）的文章就介绍到这了,更多相关java括号匹配算法内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！