题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
http://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
不想整理了,先说下思路。主要是用栈来保存计算规则,对计算规则进行char数组化,然后遍历,遇到‘(’就压栈,遇到非‘(’ 非 ‘)’就看栈最后一个元素,如果是字母就执行计算,累加次数,然后把最后一个元素弹出来,再弹一次是把最近的‘(’给弹出来,同时把计算后的矩阵行列值作为新值再压栈。遍历遇到‘)’则再执行一次计算,和上面基本一样。这样就能计算结果了。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int count =Integer.parseInt(s.nextLine());
String[] arr = new String[count];
for (int i =0;i<count;i++){
arr[i]=s.nextLine();
}
String express = s.nextLine();
Map<String,String> map = new HashMap<>();
char[] exs =express.toCharArray();
Stack<String> stack = new Stack<>();// (AB)(CD)E
String tmp="";
int j =0;
int k=0;//计算结果作为新值压栈,起名为k
int multifyTime=0;
for (int i = 0;i<exs.length;i++){
char c = exs[i];
if(c=='('){
stack.add(c+"");
}else if (c==')'){
String l = stack.pop();//l是上一次的计算结果
String n = stack.pop();//是l前面的(
if (stack.isEmpty()){
continue;
}
String lo = stack.lastElement();
if (lo.equals("(")){//这里意思是遇到多个(相连,此时要把l重新入栈,用来下次的规则计算
stack.add(l);
continue;
}
//和下方是重复代码,都是为了计算
stack.pop();
String mn1 = map.get(lo);
int m1 = Integer.parseInt(mn1.split(" ")[0]);
int n1 = Integer.parseInt(mn1.split(" ")[1]);
String mn2= map.get(l+"");
int m2 =Integer.parseInt(mn2.split(" ")[0]);
int n2 =Integer.parseInt(mn2.split(" ")[1]);
multifyTime += (m1*n1*n2);
String name = k+"";
map.put(name,m1+" "+n2);
stack.add(name);
k++;
}else{
if (!map.containsKey(c+"")){
map.put(c+"",arr[j]);
j++;
}
String lastOne = stack.lastElement();
if (lastOne.equals("(")){
stack.add(c+"");
}else if (lastOne.equals(")")){
//不会走到这里的,所有的)都不入栈
//System.out.print(lastOne+" last one");
}else{
stack.pop();
String mn1 = map.get(lastOne);
int m1 = Integer.parseInt(mn1.split(" ")[0]);
int n1 = Integer.parseInt(mn1.split(" ")[1]);
String mn2= map.get(c+"");
int m2 =Integer.parseInt(mn2.split(" ")[0]);
int n2 =Integer.parseInt(mn2.split(" ")[1]);
multifyTime += (m1*n1*n2);
String name = k+"";
map.put(name,m1+" "+n2);
stack.add(name);
k++;
}
}
}
System.out.println(multifyTime);
}
}