simpleexpevaluate.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
 */
//25 Feb 2008
package cn.edu.whu.iss.algorithm.unit10.expression.evaluation;

import java.math.BigDecimal;

import cn.edu.whu.iss.algorithm.unit10.StackLink;

/**
 * Use the stack to evaluate the expression.
 * In this class it can only evaluate the expression using the operator(+,-,*,/)
 *  and the BRACKET("(",")").And it support the decimal. And it support the pow("^") but it
 *  only evaluate the number^n ,n is the integer. And you should use the BRACKET to adorn the 
 * expression such as a*b^n you should write like this a*(b^n),a^b^c-->(a^(b^c)) or ((a^b)^c)
 * .If the divide has the remainder, it will scale to the integer of "scale" 
 * @author wpc
 * @version 0.0.1
 */
public class SimpleExpEvaluate extends AbstractExpressionEvaluation {

	/**
	 * the stack saving the factor
	 */
	private StackLink<String> stack;
	
	/**
	 * The scale of the BigDecimal quotient to be returned.
	 */
	private int scale;

	/**
	 * Get the scale of this class
	 * @return the scale
	 */
	public int getScale() {
		return scale;
	}

	/**
	 * Set scale of the BigDecimal quotient to be returned.
	 * @param scale
	 */
	public void setScale(int scale) {
		this.scale = scale;
	}

	/**
	 * the default constructor
	 */
	public SimpleExpEvaluate() {
		stack = new StackLink<String>();
		stack.clear();
		stack.setAllowNull(false);
		this.expression = null;
		this.scale = DEFAULT_SCALE;
	}

	/**
	 * The constructor need the expression
	 * @param expression the expression
	 */
	public SimpleExpEvaluate(String expression) {
		stack = new StackLink<String>();
		stack.clear();
		stack.setAllowNull(false);
		this.expression = expression;
		this.scale = DEFAULT_SCALE;
	}

	public String getResult(String expression) {
		this.expression = expression;
		return getResult();
	}

	/**
	 * Evaluate the expression in the instance.
	 * @return the result
	 */
	private String getResult() {
		String p = "", q;
		int n = expression.length();
		int i = 0;
		while (i < n) {
			char expr = expression.charAt(i);
			if (isCharOpera(expr)) {
				if (!p.equals(EMPTY_STR)) {
					pushExprWithNoEmpty(p);
					
					if (expr == OPERATOR_RIGHT_BRACKET) {
						computeStackBorder();
					} else {
						stack.push(expr + "");
					}
					p = "";
				} else if (expr == OPERATOR_MINUS) {
					String s = expression.charAt(i) + "";
					q = stack.pop();
					if (isBorder(q)) {
						s = NEGATIVE_SIGN;
					}
					stack.push(q);
					stack.push(s);
				} else if (expr == OPERATOR_RIGHT_BRACKET) {
					computeStackBorder();
				} else {
					stack.push(expr + "");
				}
			} else {
				p += expression.charAt(i);
			}
			i++;
		}
		if (!p.equals(EMPTY_STR)) {
			pushExprWithNoEmpty(p);
		}
		computeStackBorder();
		return computeFinish(stack.pop());
	}
	
	/**
	 * Push the number or factor to the stack
	 * @param p the factor
	 */
	private void pushExprWithNoEmpty(String p){
		String q,q1;
		q = stack.pop();
		if (isOperaDivOrMULTI(q)) {
			q1 = stack.pop();
			p = compute(q1, q, p);
			stack.push(p);
		} else if (isNegativeSign(q)) {
			p = computePow(p);
			p = OPERATOR_MINUS + p;
			stack.push(p);
		} else if (isExprBeginWithPow(p)){
			p=q+p;
			p = computePow(p);
			stack.push(p);
		} else if(isOnlyPow(p)){
			p=q+p;
			stack.push(p);
		} else if(isExprEndWithPow(q)){
			p=q+p;
			stack.push(p);
		} else {
			stack.push(q);
			p = computePow(p);
			stack.push(p);
		}
	}

	/**
	 * Compute the expression expr1<operator>expr2
	 * @param expr1 the first operator number
	 * @param oper the operator
	 * @param expr2 the second operator number
	 * @return the result
	 */
	private String compute(String expr1, String oper, String expr2) {
		return compute(expr1, oper.charAt(0), expr2);
	}

	/**
	 * Compute the expression in the stack in the border( "null--last" or "(......)")
	 * @param stack the stack
	 * @return the result
	 */
	private String computeStackBorder(StackLink<String> stack){
		String q, q1, q2;
		do {
			q = stack.pop();

			q1 = stack.pop();
			if (isBorder(q1)) {
				stack.push(q);
				return stack.pop();
			} else {
				q2 = stack.pop();
				q2 = compute(q, q1, q2);
				stack.push(q2);
			}
		} while (true);
	}
	
	/**
	 * Compute the class's stack
	 */
	private void computeStackBorder() {
		String q,q1;
		StackLink<String> st = new StackLink<String>();
		
		q = stack.pop();
		while(!isBorder(q)){
			if(isExprBeginWithPow(q)){
				q1 = stack.pop();
				q=q1+q;
				q = computePow(q);
			}
			st.push(q);
			q = stack.pop();
		}
		q = computeStackBorder(st);
//		q1=stack.pop();
//		if(isOperaDivOrMULTI(q1)){
//			q2 = stack.pop();
//			q = compute(q2, q1, q);
//		}else{
//			stack.push(q1);
//			//pushExprWithNoEmpty(q1);
//		}
		pushExprWithNoEmpty(q);
		//stack.push(q);
		//pushExprWithNoEmpty(q);
	}

	/**
	 * Compute the expression expr1<operator>expr2
	 * @param expr1 the first operator number
	 * @param oper the operator
	 * @param expr2 the second operator number
	 * @return the result
	 */
	private String compute(String expr1, char oper, String expr2) {
		
		expr1 = computePow(expr1);
		expr2 = computePow(expr2);
		
		BigDecimal bd1 = new BigDecimal(expr1);
		BigDecimal bd2 = new BigDecimal(expr2);
		String res = null;
		switch (oper) {
		case OPERATOR_ADD:
			res = bd1.add(bd2).toString();
			break;
		case OPERATOR_DIV:
			try {
				res = bd1.divide(bd2).toString();
			} catch (ArithmeticException e) {
				res = bd1.divide(bd2, scale, BigDecimal.ROUND_FLOOR).toString();
			}
			break;
		case OPERATOR_MINUS:
			res = bd1.subtract(bd2).toString();
			break;
		case OPERATOR_MULTI:
			res = bd1.multiply(bd2).toString();
			break;
		}
		return res;
	}
	
	/**
	 * Compute the pow (a^b)
	 * @param expr the expression with the operator ^
	 * @return the result
	 */
	private String computePow(String expr){
		if(expr==null){
			return null;
		}
		if(expr.contains(OPERATOR_POW+"")){
			int i = expr.indexOf(OPERATOR_POW);
			String s = expr.substring(0, i);
			int n = Integer.parseInt(expr.substring(i+1));
			expr = (new BigDecimal(s)).pow(n).toString();
		}
		return expr;
	}
	
	/**
	 * Check the expression only has the pow in the begin.Such as ^number
	 * @param expr the expression
	 * @return true is the format likes "^number"
	 */
	private boolean isExprBeginWithPow(String expr){
		if(expr!=null&&expr.contains(OPERATOR_POW+"")){
			int i = expr.indexOf(OPERATOR_POW);
			if(i==0&&expr.length()>1){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Check the expression only has the pow in the end.Such as number^
	 * @param expr the expression
	 * @return true is the format likes "number^"
	 */
	private boolean isExprEndWithPow(String expr){
		if(expr!=null&&expr.contains(OPERATOR_POW+"")){
			int i = expr.lastIndexOf(OPERATOR_POW);
			if(i==expr.length()-1&&expr.length()>1){
				return true;
			}
		}
		return false;
	}
	
	
	/**
	 * Check the expression equals the pow "^"
	 * @param expr the expression
	 * @return true
	 */
	private boolean isOnlyPow(String expr){
		if(expr!=null){
			if(expr.equals(OPERATOR_POW+"")){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Finish the compute.
	 * @param expr the expression
	 * @return the result
	 */
	private String computeFinish(String expr){
		return computePow(expr);
	}

}