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;
}
}
}
