java括号匹配算法求解（用栈实现）

如何使用栈来判定括号是否匹配

对于给定的表达式，可以使用栈来实现括号匹配判定，这个算法在编译器中非常重要，解析器每次读入
一个字符，如果字符是一个开分隔符，如（，【，{，入栈，若读入的是闭分隔符），】，},出栈，如果两者匹配，继续解析字符串，如果不匹配，解析器错误

算法思路

1.创建一个栈
2.当（当前字符不等于输入的结束字符）
（1）如果当前字符不是匹配的字符，判断栈内是否为空，如果栈为空，括号必然不完整
（2）如果字符是一个开分隔符，那么将其入栈
（3）如果字符是一个闭分隔符，，且栈不为空，则判断是否匹配
（4）栈结束后判断是否为空，不为空则括号匹配错误

代码示例

class Solution {
  public boolean isValid(String s) {
    //声明匹配词典
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');
    //创建栈
    Stack<Character> stack = new Stack<>();
    for (char ch : s.toCharArray()) {
      //开分隔符入栈
      if (ch == '(' || ch == '[' || ch == '{') {
        stack.push(ch);
      }
      //出栈并且栈非空进行匹配
      else if (stack.isEmpty() || stack.pop() != map.get(ch)){
        return false;
      }
    }
    //如果栈非空则括号匹配错误
    return stack.isEmpty();
  }
}

下面是其他同学的补充

1.括号匹配算法

//括号匹配算法
    public void pipei()throws Exception{
      char temp,ch;
      int match;  //记录匹配结果
      BufferedReader br = new BufferedReader(new InputStreamReader(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.括号匹配求解示例

package com.cn.datastruct;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class KuoHaoPiPei {
  static class Stack{
    char[] data; //存放数据
    int MaxSize;  //最大容量
    int top;    //栈顶指针
    //构造方法
    public Stack(int MaxSize){
      this.MaxSize=MaxSize;
      data = new char[MaxSize];
      top = -1;
    }

    public int getMaxSize() {
      return MaxSize;
    }

    public int getTop() {
      return top;
    }

    public boolean isEmpty(){
      return top==-1;
    }
    
    public boolean isFull(){
      return top+1==MaxSize;
    }
    //入栈
    public boolean push(char data){
      if(isFull()){
        System.out.println("栈已满!");
        return false;
      }
      this.data[++top]=data;
      return true;
    }
    //出栈
    public char pop() throws Exception{
      if(isEmpty()){
        throw new Exception("栈已空！");
      }
      return this.data[top--];
    }    
    //获得栈顶元素
    public char peek(){
      return this.data[getTop()];
    }
    
    //括号匹配算法
    public void pipei()throws Exception{
      char temp,ch;
      int match;  //记录匹配结果
      BufferedReader br = new BufferedReader(new InputStreamReader(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("输入的括号不匹配，请检查！");
      }
    }
  }
  
  public static void main(String[] args) throws Exception {
    String go;
    Scanner input = new Scanner(System.in);
    Stack stack = new Stack(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 <cstdio>
#include <iostream>
using namespace std;
 
#define MAXSIZE 20
 
typedef struct {
	char *base;
	char *top;
	int stacksize;
}SqStack;
 
void InitStack(SqStack &S)
{
	S.base = (char *)malloc( MAXSIZE * sizeof(char) );
	if(S.base == NULL)	exit(-2);
	S.top = S.base;
	S.stacksize = MAXSIZE;
}
 
void GetTop(SqStack S, char &e)
{
	if(S.top == S.base)
		return;
	e = *(S.top - 1);
}
 
void Push(SqStack &S, char e)							//	不考虑栈满
{
	*S.top++ = e;
}
 
void Pop(SqStack &S, char &e)
{
	if(S.top == S.base)
		return;
	S.top--;
	e = *S.top;
}
 
bool Match(char c, SqStack &my_stack, bool &tag)
{
	char e;
	Pop(my_stack, e);
	if ( c != e ) {
		tag = false;
		free(my_stack.base);
		return false;									//	match fail
	}
	return true;										//	match success
}
 
void Correct(char *expr, bool &tag)
{
	tag = true;	
	SqStack my_stack;
	InitStack (my_stack);
	for( int i = 0; expr[i] != '\0'; i++ ) {
		char c = expr[i];
		switch(c) {
			
		case '{' : case '[' : case '(' :
			Push (my_stack, c); break;
			
		case '}' : 
			if( Match('{', my_stack, tag) == false )	//	match fail
				return;
			break;
			
		case ']' : 
			if( Match('[', my_stack, tag) == false )	//	match fail
				return;
			break;
			
		case ')' : 
			if( Match('(', my_stack, tag) == false )	//	match fail
				return;
			break;
			
		default :
			break;										//	其它字符
		}
	}
	if(my_stack.top != my_stack.base)					// e.g.: "[r"
		tag = false;
	free(my_stack.base);
}
 
int main(void)
{
	//	freopen("cin.txt", "r", stdin);
	char my_expr[MAXSIZE];
	while(cin >> my_expr) {
		bool tag = true;
		Correct( my_expr, tag);
		tag ? printf("匹配成功\n") : printf("匹配失败\n");
	}
	
	return 0;
}

到此这篇关于java括号匹配算法求解（用栈实现）的文章就介绍到这了,更多相关java括号匹配算法内容请搜索易盾网络以前的文章或继续浏览下面的相关文章希望大家以后多多支持易盾网络！