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

时间:2020-12-04 阿飞Sirx 人气:0

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

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

算法思路

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;
}

加载全部内容