中缀表达式就是我们所熟悉的数学算式。如：3 + 6 - 18 / 2或3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20。
我们的目标是要实现一个计算器，来根据中缀表达式计算表达式的值。表达式由数字和+ - * / ()组成。使用两个栈来实现，一个数值栈，一个符号栈。
在这里我们假设表达式都是正确的，并且数值与符号之间由空格隔开。在代码中不再判断表达式的格式是否正确。
实现思路
首先要确定的是，运算符是有优先级的。先来考虑没有括号的情况。
我们约定+ -运算符的优先级为1，* /运算符的优先级为2，
无括号情况
在没有括号时，我们只需要先计算优先级高的式子，再回过头来计算优先级低的式子即可。入下图所示
2efde3947d764494a0e71a1246c94a9epng
流程如下：
- 先分割表达式
- 依次遍历表达式
- 如果是运算符，直接入栈
- 如果是数字，先判断数值栈是否为空，如果为空，则直接入栈；若数值栈不为空，查看符号栈栈顶的符号的优先级，如果是2（
* /），则取出数值栈栈顶元素和符号栈栈顶元素然后进行计算，并将计算结果重新入数值栈，如果优先级是1（+ -）则直接入栈。
- 遍历结束后，符号栈中就只剩下了
+ -。 - 遍历符号栈，从栈顶取出运算符，然后从数值栈中取出两个数值，然后进行运算，并将运算结果重新入栈。重复此操作，直到符号栈为空。
有括号的情况
有括号的情况会比无括号的情况复杂一些，我们需要将括号内的表达式看成一个完整的子表达式。遇到前括号就算是一个分界点，括号内的运算依然遵循，优先级高的先运算的原则，只是不再等待最后计算优先级低的运算。而是遇到后括号后就要开始符号栈的自顶而下的遍历。只到遇到前括号遍历结束。
遍历结束后还不能继续做表达式的遍历，而是应该查看符号栈栈顶的符号优先级是否为2。如果为2，则取出栈顶运算符，再从数值栈中取两个数值，然后进行运算，并将运算结果重新入数值栈。
重复以上步骤，直到符号栈栈顶运算符有限级为1或栈顶符号为(。
代码实现
package com.codestd.study.stack;
import org.apache.commons.lang3.StringUtils;
import java.util.Stack;
/**
* 中缀表达式
*
* @author jaune
* @since 1.0.0
*/
public class InfixExpression {
/**
* 计算表达式的值
* @param expression 表达式，数值与符号之间必须用空格隔开。
*/
public int calculate(String expression) {
String[] strings = StringUtils.split(expression, ' ');
// 数值栈
Stack<Integer> numStack = new Stack<>();
// 符号栈
Stack<String> operStack = new Stack<>();
for (String s : strings) {
if (isNumber(s)) { // 数值处理
if (numStack.isEmpty()) {
// 如果数值栈为空，直接入栈
numStack.push(Integer.parseInt(s));
} else if (isOpeningBracket(operStack.peek())) {
// 如果符号栈栈顶是前括号，直接入栈
numStack.push(Integer.parseInt(s));
} else if (getPriority(operStack.peek()) == 2) {
// 如果符号栈栈顶的运算符优先级高，则取出符号栈栈顶元素，取出数值栈栈顶元素然后进行计算
// 并将计算结果重新入数值栈
int num1 = numStack.pop();
int num2 = Integer.parseInt(s);
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
} else {
// 其他情况直接入数值栈
numStack.push(Integer.parseInt(s));
}
} else if (isBracket(s)) { // 括号处理
if (isOpeningBracket(s)) {
// 如果是前括号直接入符号栈
operStack.push(s);
} else {
// 如果是后括号则完成括号内子式的计算
this.calcBracket(numStack, operStack);
}
} else if (isOperator(s)) { // 运算符处理
operStack.push(s);
}
}
// 依次取出符号栈和数值栈内的运算符和数值进行计算
while (!operStack.isEmpty()) {
int num2 = numStack.pop();
int num1 = numStack.pop();
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
}
return numStack.pop();
}
/**
* 计算括号内的表达式
*/
private void calcBracket(Stack<Integer> numStack, Stack<String> operStack) {
// (12)
if (isOpeningBracket(operStack.peek())) {
operStack.pop();
highPriorityCalc(numStack, operStack);
} else {
// 经过优先级高先计算的规则，括号内不会出现乘法和除法，所以顺序计算即可。
int num2 = numStack.pop();
int num1 = numStack.pop();
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
calcBracket(numStack, operStack);
}
}
/**
* 高优先级运算符的运算
*/
private void highPriorityCalc(Stack<Integer> numStack, Stack<String> operStack) {
if (this.isOperator(operStack.peek()) && this.getPriority(operStack.peek()) == 2) {
int num2 = numStack.pop();
int num1 = numStack.pop();
int res = this.calc(num1, num2, operStack.pop());
numStack.push(res);
highPriorityCalc(numStack, operStack);
}
}
private int calc(int num1, int num2, String s) {
int res;
switch (s) {
case "+":
res = num1 + num2;
break;
case "-":
res = num1 - num2;
break;
case "/":
res = num1 / num2;
break;
case "*":
res = num1 * num2;
break;
default:
throw new RuntimeException("不能识别的符号");
}
return res;
}
private boolean isNumber(String s) {
return s.matches("\\d+");
}
private boolean isOperator(String s) {
return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s);
}
private boolean isBracket(String s) {
return "(".equals(s) || ")".equals(s);
}
private boolean isOpeningBracket(String s) {
return "(".equals(s);
}
private int getPriority(String s) {
if ("+".equals(s) || "-".equals(s)) {
return 1;
} else if ("*".equals(s) || "/".equals(s)) {
return 2;
} else {
throw new RuntimeException("不识别此符号");
}
}
}
测试代码如下
public class InfixExpressionTest {
@Test
public void test() {
String expression = "3 + 6 - 18 / 2";
InfixExpression ie = new InfixExpression();
int res = ie.calculate(expression);
assertThat(res).isEqualTo(0);
}
@Test
public void test2() {
String expression = "3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20"; // 3+3*18/2-18=3+27-18=12
InfixExpression ie = new InfixExpression();
int res = ie.calculate(expression);
assertThat(res).isEqualTo(12);
}
}
以上代码已通过此测试代码。
