输入一串数学表达式，包含加减乘除基本四则远算，表达式中可能有括号，设计一个简易计算器，计算表达式的值。
注：表达式中仅由以下字符构成：+、-、*、/、(、)
输入、输出描述
输入：
字符串表达式，如： (1-2*(3+4))/5
输出：
表达式的计算结果值，按四舍五入结果保留2位小数
Example
输入：
(1+2)*3-4/5
输出：
8.2
题目给定的算术表达式是中缀表达式，可以把它转换成后缀表达式，然后根据后缀表达式就可以进行计算了。需要注意的是，可能会出现多位数的计算，所以可以用一个ArrayList对象来包装一下待转换的中缀表达式和转换之后的后缀表达式，该对象的每个元素代表一个操作数或是一个运算符。
中缀表达式转后缀表达式以及后缀表达式做数学运算可以用栈来做，具体思路如下：
1、中缀表达式转为后缀表达式
（1）将输入的算术表达式（中缀表达式）的字符串包装成合理的ArrayList对象；
（2）初始化一个空栈和一个用于保存结果的空ArrayList对象；
（3）从左到右依次读入中缀表达式的ArrayList对象的每一个元素；
（4）如果该元素是数字，将其添加至结果ArrayList对象；
（5）如果是运算符，则将栈中所有优先级高于或等于该运算符的运算符弹出并添加至结果ArrayList对象中，然后将该运算符入栈；
（6）如果是左括号，入栈；
（7）如果是右括号，在遇见左括号之前，弹出所有运算符并添加至结果ArrayList对象中，然后丢弃左括号；
（8）如果到达中缀表达式的ArrayList对象的末尾，则弹出所有运算符并添加至结果ArrayList对象中。
2、对后缀表达式进行计算（1）从左到右读取后缀表达式，如果读取的元素是数字，则将其入栈；
（2）如果读取的元素是运算符，则弹出两个数字，根据该运算符进行运算，然后把结果入栈；
（3）如果到达后缀表达式的末尾，从栈中弹出结果。
代码：
import java.util.*;
import java.math.BigDecimal;
import java.util.regex.Pattern;
public class Main {
//判断字符串是否是数字
public boolean isNum(String string) {
Pattern pattern = Pattern.compile("\\d+||(\\d+\\.\\d+)");
return pattern.matcher(string).matches();
}
// 将中缀表达式转换成后缀表达式
public ArrayList<String> midToEnd(String input) {
//考虑可能有多位数的运算，先将输入的表达式按照合理的顺序放入一个ArrayList中
ArrayList<String> inputList = new ArrayList<>();
StringBuffer sb = new StringBuffer("");// 缓存数字
int index = 0;
String currentChar = "";
while (index < input.length()) {
currentChar = String.valueOf(input.charAt(index++));
if (isNum(currentChar)) {// 如果当前字符是数字的话，将其添加至sb
sb.append(currentChar);
//如果表达式是以数字结尾的话，将sb存储的数字插入到inputList，然后再清空sb
if (index == input.length()) {
inputList.add(sb.toString());
sb = null;//释放对象
}
} else {// 如果当前字符是运算符或括号时，将sb存储的数字插入到inputList，然后再清空sb
if (sb.length() != 0) {
inputList.add(sb.toString());
sb.replace(0, sb.length(), "");
}
inputList.add(currentChar);
}
}
Stack<String> stack = new Stack<>();// 创建操作符栈
ArrayList<String> endList = new ArrayList<>();// 保存后缀表达式的结果
for (String childString : inputList) {//逐次取出表达式中的操作数或操作符
String temp;
switch (childString) {
case " ":
break;// 忽略空格
case "(":
stack.push(childString);// 左括号直接入栈
break;
// "+" "-":将栈中的所有运算符全部弹出，直至碰到左括号为止
case "+":
case "-":
while (stack.size() != 0) {
temp = stack.pop();
if (temp.equals("(")) {
stack.push("(");
break;
}
endList.add(temp);// 将弹出的运算符添加至endList
}
stack.push(childString);
break;
// "*" "/":弹出所有运算符，直到碰到加号、减号、左括号为止，最后将该操作符压入堆栈
case "*":
case "/":
while (stack.size() != 0) {
temp = stack.pop();
if (temp.equals("+") || temp.equals("-") || temp.equals("(")) {
stack.push(temp);
break;
} else {
endList.add(temp);// 将弹出的运算符添加至endList
}
}
stack.push(childString);
break;
case ")":
while (!stack.isEmpty()) {
temp = stack.pop();
if (temp.equals("(")) {
break;
} else {
endList.add(temp);// 将弹出的运算符添加至endList
}
}
break;
default:// 如果读取到的是数字，则直接添加至endList
endList.add(childString);
break;
}
}
while (stack.size() != 0) {
endList.add(stack.pop());// 堆栈不为空时把剩余运算符一次弹出并添加至endList
}
return endList;
}
// 实现两个数字的数学运算
public Double cal(double x, double y, String operation) {
if (operation.equals("+")) {
return x + y;
}
if (operation.equals("-")) {
return x - y;
}
if (operation.equals("*")) {
return x * y;
}
if (operation.equals("/")) {
return x / y;
}
return (double) 0;
}
public double solution(String input) {
ArrayList<String> endList = midToEnd(input);// 将中缀表达式转成后缀表达式
Stack<Double> stack = new Stack<>();
for (String string : endList) {
if (isNum(string)) {
stack.push(Double.parseDouble(string));// 数字直接进栈
} else {// 如果是运算符，则弹出栈顶的两个数进行计算
double y = stack.pop();
double x = stack.pop();
stack.push(cal(x, y, string));
}
}
double aa = stack.pop();
BigDecimal res = new BigDecimal(Double.toString(aa));
BigDecimal one = new BigDecimal("1");
// 四舍五入保留两位小数
double result = res.divide(one, 2, BigDecimal.ROUND_HALF_UP).doubleValue();
return result;
}
}
评论专区
