welcome to xlongwei.com

欢迎大家一起学习、交流、分享


QQ:9167702333 邮箱:admin@xlongwei.com

Exp 数学表达式计算器算法分享


分类 Algorithm   关键字 分享   标签 java   algorithm   发布 hongwei  1428072033339
注意 转载须保留原文链接,译文链接,作者译者等信息。  
Exp类提供了计算器的核心运算代码,Calc类提供了swing界面。
支持进制转换,常用函数,数学常量等功能。

Exp的init初始化时准备好运算符(符号+优先级)、函数(参数个数)、常量(+值)、进制等
// 添加运算符,(符号,优先级,类型)
addOperator("+", 1, OperatorTypes.ADD);

// 添加函数,(函数名,参数个数,类型)
addFunction("abs", 1, FunctionTypes.ABS);

// 添加常量,(常量名,数值)
addConstants("pi", Math.PI);

// 设置进制radix
radix.put(Carriage.HEX, 16);

parse是Exp的核心算法,逐个解析exp表达式的字符,识别并加入堆栈operators和operands,并在合适的时候弹出值执行计算。
public Exp parse() throws ExpException {
	if (exp == null) { throw new ExpException("No Expression"); }
	operators.clear();
	operands.clear();
	TokenTypes lastTokenType = null;
	for (int i = 0; i < exp.length(); i++) {
		if (exp.charAt(i) == '(') {// 左括号
			if ((lastTokenType != null)// (1+1)
					&& (lastTokenType != TokenTypes.OPERATOR)// 3-(1+1)
					&& (lastTokenType != TokenTypes.FUNCTION)) {// sin(1)
				throw new ExpException(
						"Left parenthese should follow an operator");
			} else {
				operators.push(String.valueOf('('));
				lastTokenType = TokenTypes.LEFTP;
			}
		} else if (exp.charAt(i) == ')') {// 右括号
			if (!operators.contains("(")) {// 没有左括号则异常
				throw new ExpException("Miss left parenthese");
			} else {
				if (lastTokenType == TokenTypes.LEFTP) {// ()
					throw new ExpException("Empty parentheses");
				} else {
					while ((operators.size() > 0)// [(,+] <=> (1+1)
							&& (operators.peek().charAt(0) != '(')) {
						computeOperator();// compute '+'
					}
					operators.pop();// pop '('
					lastTokenType = TokenTypes.RIGHTP;
				}
			}
		} else if (Character.isDigit(exp.charAt(i))// 数字
				|| (exp.charAt(i) == '.')) {
			StringBuilder sb = new StringBuilder();
			boolean isDouble = false;
			do {
				if (exp.charAt(i) == '.') {
					if (isDouble == false) {
						isDouble = true;
					} else {
						throw new ExpException("Invalid Dot");// 小数点太多
					}
				}
				sb.append(exp.charAt(i));
				i++;
			} while ((i < exp.length())
					&& ((exp.charAt(i) == '.')
							|| Character.isDigit(exp.charAt(i)) || ("abcdef"
							.indexOf(exp.charAt(i)) > -1)));
			if (isDouble == true) {// 小数
				try {
					operands.push(Double.parseDouble(sb.toString()));
				} catch (NumberFormatException e) {
					throw new ExpException(
							"a dot is not allowed in radix: "
									+ radix.get(carriage));
				}
			} else {// 整数
				try {
					operands.push(Integer.parseInt(sb.toString(), radix
							.get(carriage)));
				} catch (NumberFormatException e) {
					throw new ExpException("illegal character for radix: "
							+ radix.get(carriage));
				}
			}
			i--;
			lastTokenType = TokenTypes.NUMBER;
		} else if (operatorTypes.keySet().contains(// 运算符
			String.valueOf(exp.charAt(i)))) {
			String operator = String.valueOf(exp.charAt(i));
			if (operator.equals("-")
					&& ((lastTokenType == null) || (lastTokenType == TokenTypes.LEFTP))) {
				operators.push("N");// 处理负号
			} else if (operator.equals("+")
					&& ((lastTokenType == null) || (lastTokenType == TokenTypes.LEFTP))) {
				continue;// 正号跳过
			} else {
				if ((lastTokenType != TokenTypes.NUMBER)// 2+1
						&& (lastTokenType != TokenTypes.RIGHTP)) {// (2)+1
					throw new ExpException("Miss operands");
				} else {
					if ((operators.size() > 0)
							&& !operators.peek().equals("(")
							&& (priority(operator, operators.peek()) <= 0)) {// [*]
						// <=>
						// +
						computeOperator();// compute '*'
					}
					operators.push(operator);// push '+'
					lastTokenType = TokenTypes.OPERATOR;
				}
			}
		} else if (Character.isLetter(exp.charAt(i))) {// 函数或常量
			StringBuilder operator = new StringBuilder();
			while ((i < exp.length())
					&& ((Character.isLetter(exp.charAt(i))) || (Character
							.isDigit(exp.charAt(i))))) {
				operator.append(exp.charAt(i));
				i++;
			}
			String function = operator.toString();
			if (functionParams.containsKey(operator.toString())) {// 函数
				if ((lastTokenType != null)// sin(1)
						&& (lastTokenType != TokenTypes.OPERATOR)// 1+sin(1)
						&& (lastTokenType != TokenTypes.LEFTP)) {// 1+(sin(1))
					throw new ExpException(
							"Function should follow an operator");
				} else {
					operators.push(function);
					lastTokenType = TokenTypes.FUNCTION;
					if (exp.charAt(i) != '(') {// sin(1)
						throw new ExpException(
								"function should followed by a (");
					} else {
						i++;
						int params = functionParams.get(function);// 参数个数
						for (int j = 1; j < params; j++) {// 用表达式递归提取params-1个参数
							int paramIdx = findParam(exp, ',', i);// 处理括号层次查找参数界限
							if (paramIdx != -1) {
								operands
										.push(new Exp().parse(
											exp.substring(i, paramIdx))
												.getResult());// 每个参数都是表达式,其中仍然可以嵌套函数
								i = paramIdx + 1;
							} else {// 缺少参数
								throw new ExpException(
										"Miss function params");
							}
						}
						int rpIdx = findParam(exp, ')', i);// 以右括号结束函数式
						if (rpIdx != -1) {// 最后一个参数
							operands.push(new Exp().parse(
								exp.substring(i, rpIdx)).getResult());
							i = rpIdx;
						} else {
							throw new ExpException("Miss function params");
						}
						computeFunction();// 计算函数
						lastTokenType = TokenTypes.RIGHTP;
					}
				}
			} else if (constants.containsKey(function)
					&& (!function.equals("e") ? true
							: carriage != Carriage.HEX)) {// 常量,非十六进制的e
				i--;
				operands.push(constants.get(function));
				lastTokenType = TokenTypes.NUMBER;
			} else if ((carriage == Carriage.HEX) && isHexNumber(function)) {// 十六进制数
				i--;
				operands.push(Integer.parseInt(function, radix
						.get(carriage)));
				lastTokenType = TokenTypes.NUMBER;
			} else {// 不支持函数或常量
				throw new ExpException("Unsupported function:" + function);
			}
		} else {// 非法字符
			throw new ExpException("Unknown Character:" + exp.charAt(i));
		}
	}
	while (operators.size() > 0) {
		if (operators.peek().charAt(0) != '(') {
			computeOperator();
		} else {
			throw new ExpException("Wrong Parentheses");
		}
	}
	if ((operands.size() != 1)) {
		throw new ExpException("Wrong Expression");
	} else {
		result = operands.pop();
	}
	return this;
}

解析出表达式之后,在computeOperator和computeFunction就非常自然了,代码见末尾Calc-sources.jar。

效果图


Calc.jarCalc-sources.jar