【讨论】一个很考验逻辑的java技能鉴定题目...

所谓的高手总喜欢把问题搞大了来证明自己的存在

我说的是我当时的情况，需求与这个不同，比较复杂，构建表达式树是我当时的一个思路。构建一个简单的表达式树只是有过编译器经验比较熟罢了，完全谈不上一个编译器。利用表达式树进行表达式求值本来就是一个很正常的做法，也没有你说的那么复杂。

情景需求不同，解决问题的方法自然会不一样。集思广益才是一个正确的讨论态度，每个人说说自己遇到的情况，自己的解决办法，能给别人提供思路，借鉴或者反思都可以。冷嘲热讽就是你讨论的态度么，至少也请看清我在说什么再给出你的结论行么？如果你有好的想法，说出来，大家一起讨论，如果你觉得没有意思大可一笑而过。

至于刚才发牢骚的确是我的不对，只不过被iteye现在的诸多隐藏弄的恼火了，说实话iteye的确越来越浮躁了。

这种数学表达式求值应该属于比较基础的工具吧，个人不太建议自己写
自己写的话还需要比较完善的测试，而且还要做好后续代码维护的打算，比较麻烦
可以试试JEP（其他开源的也有），10分钟就能用上

如果要写的话可以考虑后缀表达式（逆波兰表达式）
http://baike.baidu.com/view/552648.htm

如果是研究的话很不错，不过有个别人研究好的，就是bsh。

中缀表达式转后缀表达式，然后计算

10年以前上学时候帮一个mm写过的作业题，当时用c++写的，囧
我还记得当时忘记了字符串\0结尾，结果搞到半夜才调试出来
由于想表现一下当时的代码写的特标准，后来找工作凭着这个代码直接进了一家大公司，囧

楼主没错，楼主很倒霉，所以不发帖是王道  15个隐藏伤不起啊。。。。

这个确实是个很基础的问题，学校学数据结构的时候书上都有用栈来做这个的。蛮简单的！

我记得在腾讯笔试时做过这道题啊
贴一下自己的代码，请各位请拍（不懂编译原理，随手写的）

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package expression;

/**
 *
 * @author kk
 */
public class Expression {

	private static int PLUS = 1;
	private static int MINOR = 2;
	private static int MULTIPLY = 3;
	private static int DIVIDE = 4;
	private int value;
	private boolean isOperator;
	private Expression left;
	private Expression right;

	public Expression() {
		this.value = 0;
		this.isOperator = false;
		this.left = null;
		this.right = null;
	}

	public float compute() {
		float result = 0;
		if (!isOperator) {
			result = (float) value;
		} else {
			switch (value) {
				case 1:
					result = left.compute() + right.compute();
					break;
				case 2:
					result = left.compute() - right.compute();
					break;
				case 3:
					result = left.compute() * right.compute();
					break;
				case 4:
					result = left.compute() / right.compute();
					break;
			}
		}
		return result;
	}

	public static Expression compile(String str) throws IncorrectFormulationFormatException {

		str = str.replaceAll("\\s*", "");

		validateFormulation(str);

		int start = 0;
		int pos = 0;
		int length = str.length();

		Expression root = null;
		Expression latestOperator = null;

		while (pos < length) {
			char c = str.charAt(pos);

			if (Character.isDigit(c)) {
				boolean isSingleNum = false;
				do {
					pos++;
					if (pos == length) {
						isSingleNum = true;
						break;
					}
				} while (Character.isDigit(str.charAt(pos)));

				root = new Expression();
				String leftOperand = str.substring(start, pos);
				root.value = Integer.parseInt(leftOperand);
				root.isOperator = false;

				if (isSingleNum) {
					break;
				}
				start = pos;
			} else if (c == '(') {
				pos = findBracket(str, start);
				String subExp = str.substring(start + 1, pos);

				root = Expression.compile(subExp);
				pos++;
				start = pos;
			} else {
				char op = c;
				pos++;
				start = pos;

				Expression right = null;

				c = str.charAt(pos);
				if (c == '(') {
//                    pos = str.indexOf(')', start);


					pos = findBracket(str, start);

					String subExp = str.substring(start + 1, pos);
					right = Expression.compile(subExp);
					pos++;

				} else if (Character.isDigit(c)) {
					pos++;

					while (pos < length && Character.isDigit(str.charAt(pos))) {
						pos++;
					}

					String rightOperand = str.substring(start, pos);
					right = new Expression();
					right.value = Integer.parseInt(rightOperand);
					right.isOperator = false;
				}

				Expression operator = new Expression();
				operator.isOperator = true;
				if (op == '+') {
					operator.value = Expression.PLUS;
				} else if (op == '-') {
					operator.value = Expression.MINOR;
				} else if (op == '*') {
					operator.value = Expression.MULTIPLY;
				} else if (op == '/') {
					operator.value = Expression.DIVIDE;
				}

				switch (operator.value) {
					case 1:
					case 2:
						operator.left = root;
						operator.right = right;
						latestOperator = operator;

						root = operator;
						break;
					case 3:
					case 4:
						if (latestOperator != null) {
							operator.left = latestOperator.right;
							operator.right = right;

							latestOperator.right = operator;
							latestOperator = operator;
						} else {
							operator.left = root;
							operator.right = right;
							root = operator;
							latestOperator = operator;
						}
						break;
				}

				start = pos;
			}
		}
		return root;
	}

	private static int findBracket(String str, int index) {
		int amount = 0;
		int length = str.length();

		while (index < length) {
			if (str.charAt(index) == '(') {
				amount++;
			}

			if (str.charAt(index) == ')') {
				amount--;

				if (amount == 0) {
					return index;
				}
			}

			index++;
		}

		return -1;
	}

	private static void validateFormulation(String str) throws IncorrectFormulationFormatException {
		char c = '\0';
		char prevChar = '\0';
		int bracketAmount = 0;

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

			if (i == 0) {
				if (c == '(') {
					bracketAmount++;
				} else if (!Character.isDigit(c)) {
					throw new IncorrectFormulationFormatException(c, prevChar);
				}
			} else {
				if (c == '(') {
					if (prevChar != '+' && prevChar != '-' && prevChar != '*' && prevChar != '/' && prevChar != '(') {
						throw new IncorrectFormulationFormatException(c, prevChar);
					} else {
						bracketAmount++;
					}
				} else if (c == ')') {
					if (!Character.isDigit(prevChar) && prevChar != ')') {
						throw new IncorrectFormulationFormatException(c, prevChar);
					} else {
						if (bracketAmount < 0) {
							throw new IncorrectFormulationFormatException(c, prevChar);
						} else {
							bracketAmount--;
						}
					}
				} else if (Character.isDigit(c)) {
					if (!Character.isDigit(prevChar) && prevChar != '+' && prevChar != '-' && prevChar != '*' && prevChar != '/' && prevChar != '(') {
						throw new IncorrectFormulationFormatException(c, prevChar);
					}
				} else if (c == '+' || c == '-' || c == '*' || c == '/') {
					if (!Character.isDigit(prevChar) && prevChar != ')') {
						throw new IncorrectFormulationFormatException(c, prevChar);
					}
				} else {
					throw new IncorrectFormulationFormatException(c, prevChar);
				}
			}

			prevChar = c;
		}

		if (bracketAmount != 0) {
			throw new IncorrectFormulationFormatException(c, prevChar);
		}
	}

	public static void main(String args[]) {
		String s = "(3*4+(5))*((3*((8+99)*7-6)))";

		try {
			validateFormulation(s);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

class IncorrectFormulationFormatException extends Exception {

	public IncorrectFormulationFormatException(char currentChar, char prevChar) {
		super("current char: " + currentChar + ", prev char: " + prevChar);
	}
}

参考：http://code.google.com/p/nutz/wiki/el_overview