Java-利用栈实现括号匹配

古城微笑少年丶 2022-05-28 22:43 161阅读 0赞

SqStack.java

package test;
    
    public class SqStack{
    	private Object[]stackElem;
    	private int top;
    	
    	public SqStack(int maxSize)
    	{
    		top = 0;
    		stackElem = new Object[maxSize];
    	}
    	
    	public void clear() //空栈状态
    	{
    		top = 0;
    	}
    	
    	public int length() //栈中元素个数
    	{
    		return top;
    	}
    	 
    	public boolean isEmpty() //判栈空
    	{
    		if(top == 0)
    			return true;
    		else
    			return false;
    	}
    	
    	public Object peek() //取栈顶元素位置
    	{
    		if(!isEmpty())
    			return stackElem[top-1];
    		else
    			return null;
    	}
    	
    	//将元素x压入栈中
    	public void push(Object x)throws Exception
    	{
    		if(top == stackElem.length)
    			throw new Exception("栈已满");
    		else
    			stackElem[top++]=x;
    	}
    	
    	//删除并返回栈顶元素
    	public Object pop()
    	{
    		if(isEmpty())
    			return null;
    		else
    			return stackElem[--top];
    	}
    	
    }

Demo8.java

package test;
    import java.util.Scanner;
    public class Demo8 {
    	/**
    	 * @lijia
    	 * 括号匹配问题
    	 * 1、输入：含多种括号的表达式
    	 * 2、输出:正确时显示匹配成功，错误显示匹配失败，并指出匹配错误
    	 * 原因和位置
    	 * 3、可以对源文件进行成对出现的符号进行匹配（包括括号，引号）
    	 */
    	private final int left = 0;
    	private final int right = 1;
    	private final int other = 2;
    	
    	//判断为哪种字符串，返回int值
    	public int very1(String str)
    	{
    		if("(".equals(str)||"{".equals(str)||"[".equals(str)||"/*".equals(str))
    			return left;
    		else if(")".equals(str)||"]".equals(str)||"}".equals(str)||"*/".equals(str))
    			return right;
    		else
    			return other;
    	}
    	
    	
    	//判断括号是否匹配，boolean
    	public boolean very2(String str1,String str2)
    	{
    		if("(".equals(str1)&&")".equals(str2)||"[".equals(str1)&&"]".equals(str2)||"{".equals(str1)&&"}".equals(str2)||"/*".equals(str1)&&"*/".equals(str2))
    			return true;
    		else
    			return false;
    	}
    	/*  主要思想：从左向右扫描Java语句，每次需要读取一个字符，
    	 * 1、如果发现其为左分隔符，将其压入栈中；
    	 * 2、当从输入中读到右分隔符时，则弹出栈顶的左分隔符，并且看他是否有右分隔符匹配，如果他们不匹配，则匹配失败，
    	 * 3、若栈空或者栈中存在左分隔符，则匹配失败
    	 * 4、若所有的字符读入结束后，栈为空（所有的左分隔符都被匹配完了），则匹配成功
    	 * */
    	private boolean isLegal(String str) throws Exception
    	{
    		if(!"".equals(str)&&str!=null)
    		{
    			//使用栈解决
    			SqStack s = new SqStack(100); //新建最大空间为100的顺序栈
    			int length = str.length();
    			for(int i = 0;i<length;i++)
    			{
    				char c = str.charAt(i); 
    				String t = String.valueOf(c);  //字符转换成字符串型
    				if(i!=length)  //c不是最后一个字符
    				{
    					if('/'==c&&'*'==str.charAt(i+1)||'*'==c&&'/'==str.charAt(i+1))
    					{	
    						t = t.concat(String.valueOf(str.charAt(i+1)));//将注释符号/*连接成字符串
    						++i;	//跳过一个字符
    					}
    				}
    			
    				if(left == very1(t)) //t为左分隔符
    				{
    					s.push(t);
    				}
    				
    				else if(right == very1(t))
    				{
    					if(s.isEmpty()||!very2(s.pop().toString(),t))
    					{
    						throw new Exception("错误！");
    					}
    				}
    			}
    				if(!s.isEmpty())
    				{
    					System.out.println("错误！Java语句不合法！");				
    					return false;
    				}
    			return true;
    		}else
    			throw new Exception("错误！Java语句为空！无法匹配！");
    	}
    	
    	public static void main(String[] args) throws Exception
    	{
    		// TODO Auto-generated method stub
    		Demo8 d = new Demo8();
    		System.out.println("请输入表达式：");
    		Scanner sc = new Scanner(System.in);
    		if(d.isLegal(sc.nextLine()))
    			System.out.println("匹配成功");
    		else
    			System.out.println("匹配失败");
    	}
    
    }