找不到原题了，在leetcode找到类似的题目，不过leetcode的题目上没有括号的要求，代码实现中是有括号的。
题目：https://leetcode.cn/problems/basic-calculator-ii/
代码：
public class Solution {
private static final Character add = '+';
private static final Character sub = '-';
private static final Character mult = '*';
private static final Character divi = '/';
private static final Character parenthesesLeft = '(';
private static final Character parenthesesRight = ')';
/**
* 符号map key为计算符号 value为优先级
*/
private static final Map<Character, Integer> symbolMap = new HashMap<>();
static {
symbolMap.put(add, 0);
symbolMap.put(sub, 0);
symbolMap.put(mult, 1);
symbolMap.put(divi, 1);
symbolMap.put(parenthesesLeft, 2);
symbolMap.put(parenthesesRight, 2);
}
public int calculate(String s) {
List<Object> expressionList = this.parseExpression(s);
System.out.println("解析后：" + expressionList);
expressionList = this.toReversePolishNotation(expressionList);
System.out.println("逆波兰式：" + expressionList);
return this.calculate(expressionList).intValue();
}
/**
* 解析表达式
*
* @param expression
* @return
*/
public List<Object> parseExpression(String expression) {
List<Object> list = new ArrayList<>();
StringBuilder numStr = new StringBuilder();
//去空格
expression = expression.replaceAll(" ", "");
//遍历字符串，提取数字和计算符号
for (Character c : expression.toCharArray()) {
if (symbolMap.containsKey(c)) {
//计算符号
if (numStr.length() > 0) {
//数字转Long类型
list.add(Long.valueOf(numStr.toString()));
numStr = new StringBuilder();
}
list.add(c);
} else {
//数字
numStr.append(c);
}
}
if (numStr.length() > 0) {
//数字转Long类型
list.add(Long.valueOf(numStr.toString()));
}
return list;
}
/**
* 转成逆波兰式（后缀表达式）
*
* @param expressionList
* @return
*/
public List<Object> toReversePolishNotation(List<Object> expressionList) {
List<Object> list = new ArrayList<>();
Stack<Character> stack = new Stack<>();
//遍历表达式并转换
for (Object item : expressionList) {
if (symbolMap.containsKey(item)) {
//计算符号
if (parenthesesLeft.equals(item)) {
//左括号入栈
stack.push((Character) item);
} else if (parenthesesRight.equals(item)) {
//右括号，出栈直到碰到左括号
while (!stack.isEmpty() && !parenthesesLeft.equals(stack.peek())) {
list.add(stack.pop());
}
//将左括号弹出丢弃
if (!stack.isEmpty()) {
stack.pop();
}
} else {
//其他符号，当前符号的优先等级小于栈内的，将栈内的全部出栈
while (!stack.isEmpty() && !parenthesesLeft.equals(stack.peek()) && symbolMap.get(item) <= symbolMap.get(stack.peek())) {
list.add(stack.pop());
}
//将当前符号入栈
stack.push((Character) item);
}
} else {
//数字
list.add(item);
}
}
//清空栈
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
/**
* 通过逆波兰式进行计算
*
* @param expressionList
* @return
*/
public Long calculate(List<Object> expressionList) {
Stack<Long> stack = new Stack<>();
for (Object item : expressionList) {
if (symbolMap.containsKey(item)) {
//计算符号
Long num2 = stack.pop();
Long num1 = stack.pop();
if (add.equals(item)) {
stack.push(num1 + num2);
} else if (sub.equals(item)) {
stack.push(num1 - num2);
} else if (mult.equals(item)) {
stack.push(num1 * num2);
} else if (divi.equals(item)) {
stack.push(num1 / num2);
}
} else {
//数字
stack.push((Long) item);
}
}
return stack.pop();
}
}
思路：分三步走
1、先解析整个字符串，主要是拆出数字和计算符号，因为数字是Long类型，符号是String类型，简单操作就直接用一个List<Object>类型的list接数据。
实现上比较简单，提前将计算符号用一个Map存起来（Set也可以，不过后续有需要用到计算符号的优先级，所以用Map），使用StringBuilder拼接数字，如果遇到计算符号或者字符串都读完了，就把StringBuilder的值转成Long类型数字。
2、使用逆波兰式（后缀表达式）的方法来做计算，逆波兰式相关的资料见：https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437 。
这是整个题目实现上最复杂的部分，主要是用到了Stack栈，通过符号的一个优先级（括号由于比较特殊，优先级最高，所以直接if中特殊处理的），来判断出栈或者清空Stack的时机，具体请看代码注释。
3、通过逆波兰式进行计算。
这个比较简单，还是使用到Stack栈，如果是数字就入栈，碰到计算符号就弹出前2个值，也就是出栈。然后根据计算符号的规则（加减乘除）计算后将结果再次入栈。最终栈内有且只会有一个数字，也就是答案。
