Java实现四则运算的解析

面试遇到了这个题，里面需要用到根据配置的四则运算式（字符串型），计算公式结果，搜了之后，在网上看到这个

http://www.blogjava.net/luluyanglu/archive/2010/04/21/318964.html

 

 

因为在处理四则运算的时候最麻烦的逻辑主要是对括号内预算的处理，特别是括号的嵌套。

因此该算法主要的逻辑是，通过对括号位置的观察，得出：从左至右的扫描一个字符串，那么每一个右括号将与最近遇到的那个未匹配的左括号相匹配。这和堆栈的后进先出的规则是一样的。因此得到在扫描的过程当中，将每一个遇到的左括号进行压栈，在出现右括号的时候，出栈。

该解法相对于通过递归实现的解法，在时间复杂性上略好，并且实现出来的代码更加清晰。

package com.exam;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 
 * @author l
 *
 */
public class Exam2 {
	private boolean isRightFormat = true;

	public double getResult(String formula) {
		double returnValue = 0;
		try {
			returnValue = doAnalysis(formula);
		} catch (NumberFormatException nfe) {
			System.out.println("公式格式有误，请检查:" + formula);
		} catch (Exception e) {
			e.printStackTrace();
		}
		if (!isRightFormat) {
			System.out.println("公式格式有误，请检查:" + formula);
		}
		return returnValue;
	}

	private double doAnalysis(String formula) {
		double returnValue = 0;
		LinkedList<Integer> stack = new LinkedList<Integer>();

		int curPos = 0;
		String beforePart = "";
		String afterPart = "";
		String calculator = "";
		isRightFormat = true;
		while (isRightFormat
				&& (formula.indexOf('(') >= 0 || formula.indexOf(')') >= 0)) {
			curPos = 0;
			for (char s : formula.toCharArray()) {
				if (s == '(') {
					stack.add(curPos);
				} else if (s == ')') {
					if (stack.size() > 0) {
						beforePart = formula.substring(0, stack.getLast());
						afterPart = formula.substring(curPos + 1);
						calculator = formula.substring(stack.getLast() + 1,
								curPos);
						formula = beforePart + doCalculation(calculator)
								+ afterPart;
						stack.clear();
						break;
					} else {
						System.out.println("有未关闭的右括号！");
						isRightFormat = false;
					}
				}
				curPos++;
			}
			if (stack.size() > 0) {
				System.out.println("有未关闭的左括号！");
				break;
			}
		}
		if (isRightFormat) {
			returnValue = doCalculation(formula);
		}
		return returnValue;
	}

	private double doCalculation(String formula) {
		ArrayList<Double> values = new ArrayList<Double>();
		ArrayList<String> operators = new ArrayList<String>();
		int curPos = 0;
		int prePos = 0;
		for (char s : formula.toCharArray()) {
			if (s == '+' || s == '-' || s == '*' || s == '/') {
				values.add(Double.parseDouble(formula.substring(prePos, curPos)
						.trim()));
				operators.add("" + s);
				prePos = curPos + 1;
			}
			curPos++;
		}
		values.add(Double.parseDouble(formula.substring(prePos).trim()));
		char op;
		for (curPos = operators.size() - 1; curPos >= 0; curPos--) {
			op = operators.get(curPos).charAt(0);
			switch (op) {
			case '*':
				values.add(curPos, values.get(curPos) * values.get(curPos + 1));
				values.remove(curPos + 1);
				values.remove(curPos + 1);
				operators.remove(curPos);
				break;
			case '/':
				values.add(curPos, values.get(curPos) / values.get(curPos + 1));
				values.remove(curPos + 1);
				values.remove(curPos + 1);
				operators.remove(curPos);
				break;
			}
		}
		for (curPos = operators.size() - 1; curPos >= 0; curPos--) {
			op = operators.get(curPos).charAt(0);
			switch (op) {
			case '+':
				values.add(curPos, values.get(curPos) + values.get(curPos + 1));
				values.remove(curPos + 1);
				values.remove(curPos + 1);
				operators.remove(curPos);
				break;
			case '-':
				values.add(curPos, values.get(curPos) - values.get(curPos + 1));
				values.remove(curPos + 1);
				values.remove(curPos + 1);
				operators.remove(curPos);
				break;
			}
		}
		return values.get(0).doubleValue();
	}
}