步骤: (左括号"("默认优先级是最低的, 右括号")"默认优先级是最高的) 1.初始化两个栈,运算符栈s1和数字栈s2; 2.从左向右扫描中缀表达式; 3.遇到数字时,入数字栈s2; 4.遇到运算符时,比较其与s1栈顶元素的优先级; 4.1. 如果s1为空,或者栈顶运算符为"(",则直接将次运算符加入到s1栈; 4.2. 否则,若优先级比栈顶元素的优先级高,则直接加入到s1栈中; 4.3. 否则,将s1栈顶的运算符弹出加入到s2中; 5. 遇到括号时: 5.1. 如果是左括号"(",直接加入到s1栈中 5.2. 如果是右括号")",则以次弹出s1栈顶的运算符,并加入到s2中,直到遇到左括号为止,此时将这一对括号丢弃 6. 重复步骤2到步骤5,直到遍历完中缀表达式 7, 将s1中剩余的运算符弹出加入到s2中。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ public int solve(String s) { List<String> centerList = AnalyticExpression(s); List<String> postfixList = toPostfixExpression(centerList); int res = calculator(postfixList); return res; } private int calculator(List<String> postfixList) { Stack<String> stack = new Stack<>(); for (String s : postfixList) { if (s.matches("\\d+")) { stack.push(s); } else { int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int result = 0; switch (s) { case "+": result = num1 + num2; break; case "-": result = num1 - num2; break; case "*": result = num1 * num2; break; case "/": result = num1 / num2; break; default: throw new RuntimeException("运算符不在 + - * / 内"); } stack.push(String.valueOf(result)); } } return Integer.parseInt(stack.peek()); } private List<String> toPostfixExpression(List<String> centerList) { List<String> list = new ArrayList<>(); Stack<String> s1 = new Stack<>(); Stack<String> s2 = new Stack<>(); for (int i = 0; i < centerList.size(); i++) { if (centerList.get(i).matches("\\d+")) { s2.push(centerList.get(i)); } else if ("*".equals(centerList.get(i)) || "/".equals(centerList.get(i)) || "+".equals(centerList.get(i)) || "-".equals(centerList.get(i))) { if (s1.isEmpty() || s1.peek().equals("(")) { s1.push(centerList.get(i)); } else if (getLevel(centerList.get(i)) > getLevel(s1.peek())) { s1.push(centerList.get(i)); } else { s2.push(s1.pop()); s1.push(centerList.get(i)); } } else { if ("(".equals(centerList.get(i))) { s1.push(centerList.get(i)); } else if (")".equals(centerList.get(i))) { while (!"(".equals(s1.peek())) { s2.push(s1.pop()); } s1.pop(); // 弹出左括号"(" } } } while (!s1.isEmpty()) { s2.push(s1.pop()); } while (!s2.isEmpty()) { s1.push(s2.pop()); } while (!s1.isEmpty()) { list.add(s1.pop()); } return list; } private static int getLevel(String str) { int level = 0; if ("*".equals(str) || "/".equals(str)) { level = 1; } return level; } private List<String> AnalyticExpression(String s) { List<String> list = new ArrayList<>(); char c; String str = ""; //用于拼接多位数 int i = 0; while (i < s.length()) { if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) { list.add(c + ""); i++; } else { str = ""; while (i < s.length() && ((c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57)) { str += c; i++; } list.add(str); } } return list; } }