abstractstructurecheckexpr.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//1 Mar 2008
package cn.edu.whu.iss.algorithm.unit10.expression.structure;

import java.util.HashSet;
import java.util.Set;

import cn.edu.whu.iss.algorithm.unit10.StackLink;
import static cn.edu.whu.iss.algorithm.unit10.expression.structure.AbstractErrorInforInExpr.*;

public abstract class AbstractStructureCheckExpr implements StructureCheckExpr {

	/**
	 * the operator +
	 */
	public static final char OPERATOR_ADD = '+';
	public static final char OPERATOR_MINUS = '-';
	public static final char OPERATOR_MULTI = '*';
	public static final char OPERATOR_DIV = '/';
	public static final char OPERATOR_POW = '^';
	public static final char OPERATOR_LEFT_BRACKET = '(';
	public static final char OPERATOR_RIGHT_BRACKET = ')';
	public static final String EMPTY_STR = "";
	public static final int DEFAULT_SCALE = 10;
	/**
	 * the negative sign -number
	 */
	public static final char NEGATIVE_SIGN = '-';
	public static final char NUMBER_POINT = '.';
	
	public static final char[] CHAR_OPERA ={
		OPERATOR_ADD,OPERATOR_MINUS,OPERATOR_MULTI,OPERATOR_DIV,OPERATOR_POW,NUMBER_POINT,OPERATOR_LEFT_BRACKET,
		OPERATOR_RIGHT_BRACKET
	};
	
	public static final int WITHOUD_BRACKET_END = 6;
	
	protected Set<ErrorInforInExpression> errorSet;

	protected String expression;

	public AbstractStructureCheckExpr() {
		super();
		errorSet = new HashSet<ErrorInforInExpression>();
	}

	public AbstractStructureCheckExpr(String expression) {
		super();
		this.expression = expression;
		errorSet = new HashSet<ErrorInforInExpression>();
	}

	protected void addErrorInfor(int index, int errorId) {
		ErrorInforInExpression e = new SimpleErrorInforInExpr(index, errorId);
		errorSet.add(e);
	}

	public String getErrorMessage(String expr) {
		this.expression = expr;
		clearErrorSet();
		if (!isExpressionStructureRight()) {
			return getErrorMessage();
		}
		return "";
	}

	public boolean isExpressionStructureRight(String expr) {
		this.expression = expr;
		return isExpressionStructureRight();
	}

	abstract protected boolean isExpressionStructureRight();

	protected String getErrorMessage() {
		String res = "";
		int i = 0;
		for (ErrorInforInExpression e : errorSet) {
			i++;
			int l = e.getErrorLocation();
			String eres = i + ":\n" + this.expression+"\n";
			String b = "";
			while (l > 0) {
				b += BLANK_STRING;
				l--;
			}
			eres += b + POINT + "\n";
			eres += b +"At char "+ e.getErrorLocation() + ": " + e.getErrorMessage()+"\n";
			res += eres;
		}
		return res;
	}

	protected boolean checkBracketMatch() {
		StackLink<Bracket> stack = new StackLink<Bracket>();
		stack.setAllowNull(false);
		for (int i = 0; i < expression.length(); i++) {
			Character c = expression.charAt(i);
			if (isBracket(c)) {
				Bracket b = stack.getTop();
				if (b != null) {
					if (isBracketMatch(b.getC(), c)) {
						stack.pop();
					} else {
						b = new Bracket(i, c);
						stack.push(b);
					}
				}
			}
		}
		if (stack.isEmpty()) {
			return true;
		} else {
			while(!stack.isEmpty()){
				Bracket b = stack.pop();
				ErrorInforInExpression e = getErrorInforBeanAboutBracket(b);
				errorSet.add(e);
			}
			return false;
		}
	}

	protected static boolean isBracket(char c) {
		if (isLeftBracket(c) || isRightBracket(c)) {
			return true;
		}
		return false;
	}

	public static boolean isBracketMatch(char cl, char cr) {
		if (isLeftBracket(cl) && isRightBracket(cr)) {
			return true;
		} else {
			return false;
		}
	}
	
	public static boolean isLeftBracket(char c){
		return c=='(';
	}
	public static boolean isRightBracket(char c){
		return c==')';
	}
	
	private boolean isLeftBracket(Bracket b){
		if(b==null){
			return false;
		}
		return isLeftBracket(b.getC());
	}
	private boolean isRightBracket(Bracket b){
		if(b==null){
			return false;
		}
		return isRightBracket(b.getC());
	}

	protected ErrorInforInExpression getErrorInforBeanAboutBracket(Bracket b) {
		ErrorInforInExpression e = null;
		if(isLeftBracket(b)){
			e=(new SimpleErrorInforInExpr(b.getIndex(),LEFT_BRACKET_ERROR));
		}else if(isRightBracket(b)){
			e=(new SimpleErrorInforInExpr(b.getIndex(),RIGHT_BRACKET_ERROR));
		}
		return e;

	}

	private class Bracket {
		private int index;
		private char c;
		public Bracket(int index, char c) {
			super();
			this.index = index;
			this.c = c;
		}

		public int getIndex() {
			return index;
		}

		public void setIndex(int index) {
			this.index = index;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}
	};
	
	public static boolean isCharOperatorWithoutBracket(char c){
		for(int i=0;i<WITHOUD_BRACKET_END;i++){
			if(c==CHAR_OPERA[i]){
				return true;
			}
		}
		return false;
	}
	
	public static boolean isCharOperator(char c){
		for(int i=0;i<CHAR_OPERA.length;i++){
			if(c==CHAR_OPERA[i]){
				return true;
			}
		}
		return false;
	}
	
	public static boolean isNegativeSign(char c){
		return c==NEGATIVE_SIGN;
	}
	
	public void clearErrorSet(){
		this.errorSet.clear();
	}
}