表达式求值的java实现

[例子和习题出自数据结构(严蔚敏版), 本人使用java进行实现.  转载请注明作者和出处,  如有谬误, 欢迎在评论中指正. ]

对整数表达式求值. 表达式中可能包含+-*/四则运算, 以及括号, 比如:4 + 2 * 3 - 10 / 5, (1+2) * (4 + 5) - (9 / 7)等.

思路: 将括号之间的内容当做子表达式求值, 得出子表达式的结果后就可以去掉括号了.

使用optr栈存储运算符, opnd栈存储操作数. 解析表达式, 如果得到操作数就存入opnd栈中, 如果得到运算符, 就根据所得的运算符和optr栈顶运算符的优先级比较结果, 进行相应的操作.

 

1. 定义优先级和优先级表

/**
 * 运算符优先权
 */
public enum Precede {
	/**
	 * 优先权高
	 */
	LARGER,
	/**
	 * 优先权低
	 */
	LESS;

	/**
	 * 优先级表
	 * 		+	-	*	/
	 * 	+	>	>	<	<
	 * 	-	>	>	<	<
	 * 	*	>	>	>	>
	 * 	/	>	>	>	>
	 */
	private static Precede[][] precedes = new Precede[4][4];

	static {
		// 根据优先级表初始化precedes数组
		for (int i = 0; i < precedes.length; i++) {
			for (int j = 0; j < precedes[i].length; j++) {
				if ((i == 0 || i == 1) && j > 1) {
					precedes[i][j] = LESS;
				} else {
					precedes[i][j] = LARGER;
				}
			}
		}
	}

	/**
	 * 判断2个运算符的优先级
	 */
	public static Precede judgePrecede(char operand1, char operand2) {
		int left = getIndex(operand1);
		int right = getIndex(operand2);
		return precedes[left][right];
	}

	/**
	 * 获取运算符对应的数组索引
	 */
	private static int getIndex(char operand) {
		switch (operand) {
		case '+':
			return 0;
		case '-':
			return 1;
		case '*':
			return 2;
		case '/':
			return 3;
		default:
			throw new IllegalArgumentException();
		}
	}
}

 

2. 表达式求值

/**
 * 整数表达式运算
 */
public class EvaluateExpression {
	/**
	 * 表达式
	 */
	private String expression;
	/**
	 * 最初的表达式
	 */
	private String initExpression;
	/**
	 * 运算符栈
	 */
	private MyStack<Character> optr = new MyArrayStack<Character>();
	/**
	 * 操作数栈
	 */
	private MyStack<Integer> opnd = new MyArrayStack<Integer>();
	/**
	 * 表明下一个是否应该是数字 
	 */
	private boolean numberNext;

	public EvaluateExpression(String expression) {
		this.expression = expression;
		this.initExpression = expression;
		numberNext = true;
	}

	/**
	 * 求值
	 */
	public Integer evaluate() {
		delBlank();
		handleParentheses();

		while (true) {
			if ("".equals(expression)) {
				break;
			}
			
			if (expression.matches("^-?\\d+.*$") && numberNext) {
				opnd.push(getInteger());
				continue;
			} else {
				Character operand = expression.charAt(0);
				numberNext = true;
				expression = expression.substring(1);
				Character pop = optr.pop();

				if (pop == null) {
					optr.push(operand);
					continue;
				} else {
					Precede precede = Precede.judgePrecede(pop, operand);
					switch (precede) {
					// 优先级高时运算前2个操作数
					case LARGER: {
						optr.push(operand);
						Integer next = opnd.pop();
						Integer last = opnd.pop();
						evaluateNow(last, pop, next);
						break;
					}
					// 优先级低时运算前一个操作数和后一个操作数
					case LESS: {
						optr.push(pop);
						Integer last = opnd.pop();
						Integer next = getInteger();
						evaluateNow(last, operand, next);
						break;
					}
					}
				}
			}
		}

		// 运算结果
		Integer result = null;
		if (optr.length() == 0 && opnd.length() == 1) {
			result = opnd.pop();
		} else if (optr.length() == 1 && opnd.length() == 2) {
			Integer next = opnd.pop();
			Integer last = opnd.pop();
			evaluateNow(last, optr.pop(), next);
			result = opnd.pop();
		} else {
			throw new RuntimeException();
		}
		return result;
	}

	/**
	 * 进行实际的运算，并将结果入栈
	 */
	private void evaluateNow(Integer last, Character operand, Integer next) {
		switch (operand) {
		case '+':
			opnd.push(last + next);
			break;
		case '-':
			opnd.push(last - next);
			break;
		case '*':
			opnd.push(last * next);
			break;
		case '/':
			opnd.push(last / next);
			break;
		}
	}

	/**
	 * 获得表达式开头部分的整数
	 */
	private Integer getInteger() {
		StringBuilder sb = new StringBuilder();
		int count = 0; // 整数位
		boolean lessZero = false; // 是否是负数
		
		if (expression.startsWith("-")) {
			sb.append("-");
			count++;
			lessZero = true;
		}
		
		int i = (lessZero ? 1 : 0);
		for (; i < expression.length(); i++) {
			char c = expression.charAt(i);
			if (c >= '0' && c <= '9') {
				sb.append(c);
				count++;
			} else {
				break;
			}
		}
		expression = expression.substring(count);
		numberNext = false;
		return Integer.valueOf(sb.toString());
	}

	/**
	 * 处理括号. 将括号内的字符串作为子表达式计算.
	 */
	private void handleParentheses() {
		while (expression.contains("(")) {
			// 左括号的索引
			int left = 0;
			// 右括号的索引
			int right = 0;
			// 左括号的数量
			int count = 0;

			// 求出左括号索引
			left = expression.indexOf('(');

			// 求出对应的右括号索引
			for (int i = left; i < expression.length(); i++) {
				char c = expression.charAt(i);
				if (c == ')') {
					count--;
					// count为0时才是对应的右括号
					if (count == 0) {
						right = i;
						break;
					}
				} else if (c == '(') {
					count++;
				} else {
					continue;
				}
			}
			// 左右括号之间是一个子表达式, 计算子表达式的值，并根据结果构造出新的表达式
			EvaluateExpression evaluateExpression = new EvaluateExpression(expression.substring(left + 1, right));
			expression = expression.substring(0, left) + evaluateExpression.evaluate()
					+ expression.substring(right + 1);
		}
	}

	/**
	 * 删除表达式中的空白字符
	 */
	private void delBlank() {
		expression = expression.replaceAll("\\s", "");
	}
	
	@Override
	public String toString() {
		return initExpression;
	}
}

 

3. 进行测试

@Test
public void testEvaluate() {
	EvaluateExpression expression = new EvaluateExpression("1 + 2 ");
	System.out.println(expression + " = " + expression.evaluate());
	
	expression = new EvaluateExpression("4 + 2 * 3 - 10 / 5");
	System.out.println(expression + " = " + expression.evaluate());
	
	expression = new EvaluateExpression("(1+2) * (4 + 5) - (9 / 7)");
	System.out.println(expression + " = " + expression.evaluate());
	
	expression = new EvaluateExpression("(1 + (3 * (4 - 9)))");
	System.out.println(expression + " = " + expression.evaluate());
	
	expression = new EvaluateExpression("(1 + (3 * (4 - 9))) + (3 * (2 + 3))");
	System.out.println(expression + " = " + expression.evaluate());
}

测试的结果为:

1 + 2  = 3

4 + 2 * 3 - 10 / 5 = 8

(1+2) * (4 + 5) - (9 / 7) = 26

(1 + (3 * (4 - 9))) = -14

(1 + (3 * (4 - 9))) + (3 * (2 + 3)) = 1

 

可见结果是正确的.