rambless
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case int n = in.nextInt(); List<Point> list = new ArrayList<>(n); Point p; for (int i = 0; i < n; i++) { p = new Point(in.nextInt(), in.nextInt()); list.add(p); } in.nextLine(); String str = in.nextLine(); String s = str.replace("(", "").replace(")", ""); Point temp = cal(str, s, list); System.out.println(temp.z); } } //利用栈的特性实现运算顺序 private static Point cal(String str, String s, List<Point> list) { Point p; Deque<Point> stack = new LinkedList<>(); for (int i = 0; i < str.length(); i++) { //如果是括号则递归算括号里边的 if (str.charAt(i) == '(') { int count = 1; int j = i + 1; while (count > 0 && j < str.length()) { if (str.charAt(j) == ')') { count--; } else if (str.charAt(j) == '(') { count++; } j++; } stack.push(cal(str.substring(i + 1, j - 1), s, list)); //回溯 i = j; } if (i < str.length()) { //由于括号后边可能还有括号,需继续括号逻辑 if (str.charAt(i) == '(') { int num = 1; int m = i + 1; while (num > 0 && m < str.length()) { if (str.charAt(m) == ')') { num--; } else if (str.charAt(m) == '(') { num++; } m++; } stack.push(cal(str.substring(i + 1, m - 1), s, list)); //回溯 i = m; } else if (str.charAt(i) == ')') { //输入合法时不存在此情况 } else { //矩阵时直接压栈 p = list.get(s.indexOf(str.substring(i, i + 1))); stack.push(p); } } } Point pre = stack.pop(); Point temp; while (!stack.isEmpty()) { temp = stack.pop(); int num = temp.x * temp.y * pre.y + pre.z + temp.z; pre = new Point(temp.x, pre.y, num); } return pre; } static class Point { int x; int y; int z = 0; public Point(int x, int y) { this.x = x; this.y = y; } public Point(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } } }