爪哇国新游记之十九----使用Stack检查数字表达式中括号的匹配性

/**
 * 辅助类
 * 用于记载字符和位置
 *
 */
class CharPos{
    char c;
    int pos;

    public CharPos(char c,int pos){
        this.c=c;
        this.pos=pos;
    }
}

/**
 * 括号检查类
 *
 */
public class BracketChecker{
    /**
     * 检查函数
     * @param str
     * @return
     * @throws Exception
     */
    public static boolean check(String str) throws Exception{
        int length=str.length();
        Stack<CharPos> stack=new Stack<CharPos>(CharPos.class,length);

        for(int i=0;i<length;i++){
            char ch=str.charAt(i);

            if(ch=='{' || ch=='[' || ch=='('){
                stack.push(new CharPos(ch,i));
            }else if(ch==')' || ch==']' || ch=='}'){
                try{
                    CharPos poped=stack.pop();

                    if( (ch==')' && poped.c !='(') || (ch==']' && poped.c !='[') || (ch=='}' && poped.c !='{')){
                        throw new Exception("位于第"+(i+1)+"位的字符"+ch+"没有对应的匹配项");
                    }
                }catch(java.lang.ArrayIndexOutOfBoundsException e){
                    throw new Exception("位于第"+(i+1)+"位的字符"+ch+"没有对应的匹配项");
                }
            }
        }

        StringBuilder sb=new StringBuilder();
        while(stack.isEmpty()==false){
            CharPos poped=stack.pop();
            sb.append("位于第"+(poped.pos+1)+"位的字符"+poped.c+"没有对应的匹配项,");
        }
        if(sb.length()>0){
            throw new Exception(sb.toString());
        }

        return true;
    }

    public static void main(String[] args) throws Exception{
        String[] arr={"5+2*(3+3)","{[(2+4)*8]/6}","[()]}","{[(]}","{[](","(((((())))))","((([((())))))","[[[[[]]]]]"};

        for(String str:arr){
            try{
                boolean isOk=BracketChecker.check(str);
                if(isOk){
                    System.out.println("在字符串"+str+"中大中小括号都是匹配的.");
                }
            }catch(Exception e){
                System.out.println("在字符串"+str+"中,"+e.getMessage());
            }
        }
    }
}

输出:

在字符串5+2*(3+3)中大中小括号都是匹配的.
在字符串{[(2+4)*8]/6}中大中小括号都是匹配的.
在字符串[()]}中,位于第5位的字符}没有对应的匹配项
在字符串{[(]}中,位于第4位的字符]没有对应的匹配项
在字符串{[](中,位于第4位的字符(没有对应的匹配项,位于第1位的字符{没有对应的匹配项,
在字符串(((((())))))中大中小括号都是匹配的.
在字符串((([((())))))中,位于第11位的字符)没有对应的匹配项
在字符串[[[[[]]]]]中大中小括号都是匹配的.
上一篇:Log4net使用(一)


下一篇:爪哇国新游记之二十二----排序判断重复时间复杂度为2n的位图法