题解 | #矩阵乘法计算量估算#

矩阵乘法计算量估算

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);
}
}
全部评论

相关推荐

10-25 02:13
门头沟学院 C++
_凡_:8.27笔试10.22评估
投递小米集团等公司10个岗位
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务