中缀表达式计算器
一、实现思路
1.双栈,一个操作符栈,一个操作数栈,从左到右扫描所有的字符
2.如果是操作数,直接入操作数栈;如果是操作符,比较栈顶操作符和新操作符优先级
如果新的操作符是左括号或优先级高于栈顶元素时 新的操作符入栈;
如果新的操作符优先级不高于栈顶元素的 ,就先出栈一个操作符(如果新操作符是右括号要循环弹出操符直到碰到左括号结 束和两个操作数计算并将结果入操作数栈 ,新操作符再入栈;
3.直到所有的字符都扫描完毕,然后不断弹出操作符栈计算,直到栈为空.弹出并返回操作符栈中仅有的元素
二、具体实现
1.定义一个操作符优先级枚举
/**
* @ClassName: OperatorEnum
* @description: 操作符枚举
* @author: leijing
* @Date: 2019/4/13 下午10:13
* @Version: 1.0
*/
public enum OperatorEnum {
RB(')',0),LB('(',1),ADD('+',2),SUB('-',2),MUL('*',3),DIV('/',3);
private int priority;
private char name;
OperatorEnum(char name , int priority){
this.name = name;
this.priority = priority;
}
public static OperatorEnum getOp(char ch){
OperatorEnum[] values = OperatorEnum.values();
for (OperatorEnum op : values){
if (op.name == ch){
return op;
}
}
return null;
}
public int getPriority() {
return priority;
}
public char getName() {
return name;
}
}
2.定义一个表达式计算器
import java.util.Stack;
/**
* @ClassName: ExpressCalculator
* @description: 中缀表达式计算器
* @author: leijing
* @Date: 2019/4/13 下午10:12
* @Version: 1.0
*/
public class ExpressCalculator {
public int calculateExpress(String express) {
Stack<Integer> numStack = new Stack<>();
Stack<OperatorEnum> opStack = new Stack<>();
for (int i = 0; i < express.length(); i++) {
char ch = express.charAt(i);
OperatorEnum op = OperatorEnum.getOp(ch);
if (op != null) {//是操作符
if (opStack.empty() || op.equals(OperatorEnum.LB)
|| opStack.peek().getPriority() < op.getPriority()) {//如果操作符栈为空或者新的操作符优先级大于栈顶元素的 入操作符栈
opStack.push(op);
} else {
if (OperatorEnum.RB.equals(op)) {//新操作符如果是')' 需要再弹出一个操作符
while (!opStack.empty() && !opStack.peek().equals(OperatorEnum.LB)) {
int result = calculate(opStack.pop().getName(), numStack.pop(), numStack.pop());
numStack.push(result);//新的结果入操作符栈
}
opStack.pop();//弹出左括号
} else {
int result = calculate(opStack.pop().getName(), numStack.pop(), numStack.pop());
numStack.push(result);//新的结果入操作符栈
opStack.push(op);//新的操作符入栈
}
}
} else {//是数字
int num = ch - '0';
numStack.push(num);
}
}
while (!opStack.empty()) {
OperatorEnum top = opStack.pop();
int result = calculate(top.getName(), numStack.pop(), numStack.pop());
numStack.push(result);
}
return numStack.pop();
}
private int calculate(char ch, int num2, int num1) {
int result = 0;
switch (ch) {
case '+': {
result = num1 + num2;
break;
}
case '-': {
result = num1 - num2;
break;
}
case '*': {
result = num1 * num2;
break;
}
case '/': {
result = num1 / num2;
break;
}
}
return result;
}
}
3.写一个单元测试类
import org.junit.Assert;
import org.junit.Test;
import org.express.ExpressCalculator;
/**
* Unit test for ExpressCalculator.
*/
public class ExpressCalculatorTest
{
@Test
public void calculateExpress() {
ExpressCalculator calculator = new ExpressCalculator();
String express = "1+2+3*4*5";
int result = calculator.calculateExpress(express);
System.out.println(express+"="+result);
Assert.assertEquals(63 , result);
}
@Test
public void calculateExpress2() {
ExpressCalculator calculator = new ExpressCalculator();
String express = "(8-1)*(5+5)/7";
int result = calculator.calculateExpress(express);
System.out.println(express + "=" + result);
Assert.assertEquals(10 , result);
}
@Test
public void calculateExpress4() {
ExpressCalculator calculator = new ExpressCalculator();
String express = "5+(4*(3+2))";
int result = calculator.calculateExpress(express);
System.out.println(express + "=" + result);
Assert.assertEquals(25 , result);
}
}