亲宝软件园·资讯

展开

java括号匹配算法求解(用栈实现)

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

加载全部内容

相关教程
猜你喜欢
用户评论