表达式求值的java实现

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

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

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊