矩阵乘法计算量估算

思路：构造一颗二叉树，递归计算左右子树的计算量， 再加上左子树矩阵*右子树矩阵的计算量。

坑：测试数据存在右括号多于左括号数量的情况，需要特殊处理一下。

import java.util.*;
public class Main {
    public class Node {
        Node left, right;
        int row, col;//val
        public Node(int x, int y) {
            row = x;
            col = y;
            left = null; 
            right = null;
        }
    }
    public Node creatTree(char[] s, int[][] a, int start, int end) {
        if(start > end || start < 0 || start >= s.length || end < 0 || end >= s.length)
            return null;
        if(start == end) {
            int idx = s[start] - 'A';
            return new Node(a[idx][0], a[idx][1]);
        }
        int l = start + 1, r = end - 1;
        int cnt = 1, mid = l;
        if(s[l] == '(') {
            while(cnt != 0) {
                mid++; 
                if(s[mid] == '(') cnt ++;
                if(s[mid] == ')') cnt --;
            }
        }
        Node root = new Node(-1,-1);
        root.left = creatTree(s, a, l, mid);
        root.right = creatTree(s, a, mid+1, r);
        return root;
    }
    public int[] dfs(Node root) {
        if(root == null) return new int[] {-1,-1, 0};
        if(root.left == null && root.right == null) {
            int[] res = new int[] {root.row, root.col, 0};
            //System.out.println(Arrays.toString(res));
            return res;
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int[] res = new int[] {l[0], r[1], l[2] + r[2] + l[0]*l[1]*r[1]};
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main mn = new Main();
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int[][] a = new int[n][2];
            for(int i=0; i < n; i++) {
                a[i][0] = sc.nextInt();
                a[i][1] = sc.nextInt();
            }
            char[] s = sc.next().toCharArray();
            int cnt = 0;//判断左括号数量是否等于右括号数量
            for(int i=0; i < s.length; i++) {
                if(s[i] == '(') cnt ++;
                if(s[i] == ')') cnt --;
            }
            Node tree = null;
            if(cnt != 0) {
                tree = mn.creatTree(s, a, 0, s.length-2); // 去除多余的一个右括号
            } else {
                tree = mn.creatTree(s, a, 0, s.length-1);
            }
            int[] res = mn.dfs(tree);
            System.out.println(res[2]);
        }
    }
}
/*
1. 构造二叉树，节点信息包括:row(行数),col(列数)
2. 计算子树乘法次数，再加上左子树矩阵*右子树矩阵的计算量。
*/

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    string str;
    
    while(cin>>n) {
        //初始化个矩阵参数
        vector<vector<int>> jzv = vector<vector<int>>(n, vector<int>(2,0));
        for(auto &v:jzv)
            for(auto &i:v)
                cin>>i;
        
        cin>>str;
        
        vector<char> chs;    //字符处理过程
        vector<vector<int>> vb;    //矩阵计算过程
        int cnt=0, idx=0;
        
        for(auto ch:str) {
            //cout<<ch<<" ";
            if(ch == ')') {    //遇到完整括号，计算括号内乘法
                vector<int> last; //保存上次计算结果
                
                if(vb.size()<2)  //防止多右括号
                    continue;
                
                while(chs.back() != '(') {    //从后向前乘
                    //cout<<chs.back()<<" ";
                    if(!last.empty()) {
                        cnt += last[0]*last[1]*vb.back()[0];    //当前矩阵与后一个矩阵相乘
                        //cout<<last[0]<<" "<<last[1]<<" "<<vb.back()[0]<<" "<<cnt<<" ";
                        last[0]=vb.back()[0];    //生成新矩阵，行为前矩阵行，列为后矩阵列
                    } else {
                        last = vb.back();    //取得一个矩阵
                    }
                    vb.pop_back();    //已运算矩阵出栈
                    chs.pop_back();   //已运算矩阵字母出栈
                }
                chs.pop_back();     //弹出左括号
                chs.push_back('X'); //压入计算结果新矩阵字母
                vb.push_back(last); //压入计算结果新矩阵
                
            } else {
                chs.push_back(ch);    //字符入栈
                if(ch>='A' && ch<='Z')
                    vb.push_back(jzv[idx++]);    //矩阵入栈
            }
        }
        
        cout<<cnt<<endl;
    }
}

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int stack1[100][2];
int stack_pointer;

void push(int a, int b);
void pop(int *a, int *b);

int main()
{
    int num,len;
    int a,b,c,d, sum;    //计算乘法次数用
    
    while(scanf("%d", &num) != EOF)
    {
        int k=0;
        int matrix[100][2] = {0};
        char str1[100] = {0};
        
        /*初始化*/
        sum = 0;
        stack_pointer = -1;//栈指针复位到-1位置。
        memset(stack1,0,200*sizeof(int));
        for(int i=0; i<num; i++)
        {
            for(int j=0; j<2; j++)
            {
                scanf("%d", &matrix[i][j]);
            }
        }
        scanf("%s", str1);
        len = strlen(str1);
        
        for(int i=0; i<len; i++)
        {
            if(str1[i] >= 'A' && str1[i] <= 'Z')
            {
                push(matrix[k][0], matrix[k][1]);
                k++;
            }
            else if(str1[i] == ')')
            {
                pop(&c,&d);
                pop(&a,&b);
                if(c == b)
                {
                    sum += a*b*d;//求乘法次数
                    push(a,d);//把相乘形成的新数组压入栈
                }
                else
                {
                    printf("error\n");
                }
            }
            else ;
            
        }
        
        printf("%d\n", sum);
    }
    return 0;
}

void push(int a, int b)
{
    stack_pointer++;
    stack1[stack_pointer][0] = a;
    stack1[stack_pointer][1] = b;
    
}

void pop(int *a, int *b)
{
    *a = stack1[stack_pointer][0];
    *b = stack1[stack_pointer][1];
    stack1[stack_pointer][0] = 0;
    stack1[stack_pointer][1] = 0;
    stack_pointer--;
}

#include<stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        int juzhen[100][2];
        int b[100][2];
        char a[100] = {0};
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&juzhen[i][0]);
            scanf("%d",&juzhen[i][1]);
        }
        scanf("%s",&a);
        int len = strlen(a);
        int sum = 0;
        int i = 0;
        int j = 0;
        int count = 0;
       
        while(i < len)
        {
            if(a[i] == '(')
            {
                i++;
            }
            if(a[i] >= 'A' && a[i] <= 'Z')
            {
                b[j][0] = juzhen[a[i] - 'A'][0];
                b[j][1] = juzhen[a[i] - 'A'][1];
                i++;
                j++;
                if(a[i] >= 'A' && a[i] <= 'Z')
                {
                b[j][0] = juzhen[a[i] - 'A'][0];
                b[j][1] = juzhen[a[i] - 'A'][1];
                    i++;
                j++;
                }
                if(a[i] == '(')
                {
                    i++;
                }
                if(a[i] == ')')
                {
                    j--;
                    sum += b[j - 1][0] * b[j - 1][1] * b[j][1];
                    b[j - 1][1] = b[j][1];
                    i++;
                }
            }
            if(a[i] == ')')
                {
                    j--;
                    sum += b[j - 1][0] * b[j - 1][1] * b[j][1];
                    b[j - 1][1] = b[j][1];
                    i++;
                }
        }
        printf("%d\n",sum);
    }
    return 0;
}

#include<stdio.h>
int a[20],b[20];            //分别存每组行列
int pos;                //指向字符串当前位置
int top;                //指向最新参与计算的一组行列
int calcu(char s[]){                 //计算括号内的全部
    int num=0,len=strlen(s),row=0,col=0;     //row，col存入完成连乘后的行列，其实每次只会改变列值
    while(pos<len&&s[pos]!=')'){
        if(s[pos]=='('){       //遇到正括号，再次调用calcu
            pos++;
            num+=calcu(s);
        }
        else top++;            //遇到字符，top后移指向当前要参与计算的行列
        if(row){              //已有行列值，可计算
            num+=row*col*b[top];    //top指向最新行列，出括号后也恰好指向括号内最后一个行列，只需用到其列值
            col=b[top];         //更新连乘后新矩阵的列，行不变只会是该括号内数据的第一个行
        }
        else{                 //该括号内还一组行列都没处理
            row=a[top];
            col=b[top];
        }
        pos++;
    }
    return num;   //返回该括号内计算值，或字符串遍历完成返回最终计算值
}
int main(int argc,char *argv[]){
    int n;
    while(scanf("%d",&n)!=EOF){
        top=-1;
        for(int i=0;i<n;i++)
            scanf("%d%d",&a[i],&b[i]);
        char str[40];
        scanf("%s",str);
        pos=0;
        printf("%d\n",calcu(str));
    }
    return 0;
}

def get_sum(s, m, r):
    if s[0] == '(' and s[3] == ')':  # 推出条件 (AZ)
        return r + m[0][0] * m[0][1] * m[1][1]  # [[1,2],[2,3]] 1*2*3
    for index, item in enumerate(s):
        if s[index] == '(' and s[index + 3] == ')':  # 题目隐含条件，一对最近的括号中有且仅有两个字母 eg: (A(BC))
            mi = index // 2  # 找到'('对应矩阵的matrix index
            s1 = s[:index] + 'Z' + s[index + 4:]  # (A(BC)) => (AZ)
            m1 = m[:mi] + [[m[mi][0], m[mi + 1][1]]]  # [[1,2],[2,3],[3,4]] => [[1,2],[2,4]]
            r1 = r + m[mi][0] * m[mi][1] * m[mi + 1][1]  # r + 2*3*4
            return get_sum(s1, m1, r1)


while True:
    try:
        n = int(input())
        m = [[int(_) for _ in input().split()] for _ in range(n)]  # 生成记录矩阵 [[1,2],[2,3]]
        s = input()  # 计算法则 (A(BC))
        print(get_sum(s, m, 0))
    except:
        break

# 吐了测试样例有错误
'''
8
61 4
4 43
43 52
52 24
24 29
29 37
37 23
23 16
(A(B(C(D(E(F(GH)))))))) 左右括号数量不一致
'''
def mul(L):
    if len(L) < 2:
        return 0
    elif len(L) == 2:
        return L[0][0] * L[0][1] * L[1][1]
    else:
        twosum = L[0][0] * L[0][1] * L[1][1]
        newL = L[2:].insert(0, [L[0][0], L[1][1]])
        return twosum + mul(newL)


while True:
    try:
        n = int(input())
        x = []
        c = []
        stack = []
        tmp = []
        res = 0
        for i in range(n):
            x.append([int(t) for t in input().split()])
        rule = input()
        for ch in rule:
            if ch.isalpha():
                c.append(ch)
        d = dict(zip(c, x))
        for i in range(len(rule)):
            if rule[i] == ')':
                while stack and stack[-1] != '(':
                    tmp.append(stack.pop())
                stack.pop()
                L = tmp[::-1]
                stack.append([L[0][0], L[-1][1]])
                res += mul(L)
                tmp = []
            elif rule[i] == '(':
                stack.append('(')
            else:
                stack.append(d[rule[i]])
        res += mul(stack)
        print(res)
    except:
        break

while True:
    try:
        n = int(input())
        arr = []
        for i in range(n):
            arr.append(list(map(int,input().split())))
        s = input().replace('(', '')
        count = 0
        add_count = 0
        for i in range(len(s)):
            if s[i] == ')' and len(arr) > 1:
                index = len(s[:i].replace(')', '')) - add_count
                count += arr[index-2][0] * arr[index-2][1] * arr[index-1][1]
                add_count += 1
                arr.insert(index-2,[arr[index-2][0], arr[index-1][1]])
                arr.pop(index-1)
                arr.pop(index-1)
        print(count)
    except:
        break

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main()
{     int n;     while(cin>>n)     {         vector<vector<int> > Mat(n, vector<int> (2,0));         for(int i=0;i<n;i++)             for(int j=0;j<2;j++)                 cin>>Mat[i][j];         string s;         stack<char> st;         int cnt = 0;         cin>>s;         for(int i=0;i<s.length();i++)         {             if(s[i]==')')             {                 if(st.size()!=1)                 {                     vector<int> b = Mat[st.top()-'A'];                     st.pop();                     vector<int> &a = Mat[st.top()-'A'];                     cnt += a[1]*a[0]*b[1];                     a[1] = b[1];                 }             }else if(s[i]!='(')                 st.push(s[i]);         }         cout<<cnt<<endl;     }     return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int n=in.nextInt();
            in.nextLine();
            String[] matrix=new String[n];
            for(int i=0;i<n;i++){
                matrix[i]=in.nextLine();
            }
            String rule=in.nextLine();
            Main.multiCount(n,matrix,rule);
        }
    }
    public static void multiCount(int n,String[] matrix,String rule){
        Stack<Character> sign=new Stack<Character>();
        Stack<String> letter=new Stack<String>();
        char[] ch=rule.toCharArray();
        int index=0;
        int result=0;
        for(int i=0;i<ch.length;i++){
            if(ch[i]=='('){
                 sign.push(ch[i]);
            }else if(ch[i]>='A'&&ch[i]<='Z'){
                letter.push(matrix[index++]);
            }else if(ch[i]==')'){
                if(!sign.isEmpty())
                    sign.pop();
                if(!letter.isEmpty()){
                    String[] up=letter.pop().split(" ");
                    if(letter.isEmpty())
                        break;
                    String[] down=letter.pop().split(" ");
                    result+=(Integer.parseInt(down[0]))*(Integer.parseInt(down[1]))*(Integer.parseInt(up[1]));
                    letter.push(down[0]+" "+up[1]);
                }
            }
        }
        System.out.println(result);
    }
}

import re
try:
    while 1:
        table = []
        n = input()
        for i in xrange(n):
            a, b = map(int, raw_input().split())
            table.append(['', a, b])
            
        expr = raw_input()
        pos = 0
        for i in expr:
            if i != '(' and i != ')':
                table[pos][0] = i
                pos += 1
                
        flop = 0
        result = re.findall(r'\(\w+\)', expr)
        while result != []:
            for j in result:
                length = len(table)
                pos1 = -1
                pos2 = -1
                for k in xrange(length):
                    if table[k][0] == j[1]:
                        pos1 = k
                    if table[k][0] == j[2]:
                        pos2 = k
                    if pos1 != -1 and pos2 != -1:
                        break
                flop += table[pos1][1] * table[pos1][2] * table[pos2][2]
                table[pos1][2] = table[pos2][2]
                expr = expr.replace(j, table[pos1][0])
                result = re.findall(r'\(\w+\)', expr)
      
        print flop
except:
    pass

    import java.util.*;

    public class Main {

        public static void main(String[] args) {
            @SuppressWarnings("resource")
            Scanner scan=new Scanner(System.in);
            while(scan.hasNext()){
                int n=scan.nextInt();
                int[][] m=new int[n][2];
                for(int i=0; i<n; i++){
                    for(int j=0; j<2; j++){
                        m[i][j]=scan.nextInt();
                    }
                }
                scan.nextLine();
                char[] c=scan.nextLine().toCharArray();
                HashMap<Character, int[]> h=new HashMap<>();
                for(int i=0; i<n; i++){
                    h.put((char) (i+'A'), m[i]);
                }
                Stack<Character> s=new Stack<>();
                int i=0;
                int count=0;
                //-------------------------------------------------该部分针对(ABC(DE))、ABCD这两种情况进行了处理
                        //去掉后也可以通过，因为题目测试用例只有这一种情况：(A(B(CD)))
                ArrayList<Character> list=new ArrayList<>();
                for(int j=0; j<c.length; j++){
                    list.add(c[j]);
                }
                if(list.get(0)!='('){
                    list.add(0, '(');
                }
                if(list.get(list.size()-1)!=')'){
                    list.add(list.size(), ')');
                }
                for(int j=0; j<list.size()-2; j++){
                    if(list.get(j)!='(' && list.get(j)!=')' && list.get(j+1)!='(' && list.get(j+1)!=')'){
                        if(list.get(j+2)!=')'){              
                           count+=h.get(list.get(j))[0]*h.get(list.get(j))[1]*h.get(list.get(j+1))[1];
                            int[] temp=new int[]{h.get(list.get(j))[0], h.get(list.get(j+1))[1]};
                            h.put(list.get(j), temp);
                            list.remove(j+1);
                            j--;
                        }
                    }
                }
                c=new char[list.size()];
                for(int j=0; j<c.length; j++){
                    c[j]=list.get(j);
                }
                //-----------------------------------------------------------
                while(!s.isEmpty() || i<c.length){
                    boolean b=false;
                    if(i<c.length && c[i]!=')'){
                        s.add(c[i]);
                        i++;
                    }
                    else{
                        i++;
                        char c1=s.pop();
                        char c2=s.pop();
                        s.pop();
                        if(s.isEmpty()){
                            b=true;
                        }
                        count+=h.get(c2)[0]*h.get(c2)[1]*h.get(c1)[1];
                        int[] temp=new int[]{h.get(c2)[0], h.get(c1)[1]};
                        h.put(c2, temp);
                        s.add(c2);
                    }
                    if(b){
                        break;
                    }
                }
                System.out.println(count);
            }

        }

    }

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>

struct matrix {
	int x;
	int y;
};
int main()
{
	using namespace std;
	int n;
	while (cin >> n) {
		vector<matrix> input(n + 1);
		for (int i = 0; i < n; i++) {
			cin >> input[i].x >> input[i].y;
		}
		string str;
		cin >> str;
		matrix temp;
		temp.x = 0;
		temp.y = 0;
		input[n] = temp;
		int ans = 0;
		stack<char> rules;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] != ')') {
				rules.push(str[i]);
			}
			else {
				vector<char> index;
				while (!rules.empty()) {
					if (rules.top() == '(') {
						rules.pop();
						break;
					}
					index.insert(index.begin(), rules.top());
					rules.pop();
				}
				if (index.size() == 1) {
					continue;
				}
				else {
					temp.x = input[index[0] - 'A'].x;
					temp.y = input[index[index.size() - 1] - 'A'].y;
					for (int j = 0; j < index.size() - 1; j++) {
						ans += input[index[0] - 'A'].x * input[index[j] - 'A'].y * input[index[j + 1] - 'A'].y;
					}
					rules.push('A' + n);
					input[n] = temp;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
    int n;
    string s;
    while(cin>>n){
        int a[n][2];
        for(int i=0;i<n;++i)
            cin>>a[i][0]>>a[i][1];
        int k=0,sum=0;
        int p=0,q=0;
        vector<int> vec;
        cin>>s;
        for(int i=0;i<s.length();++i){
            if(s[i]!=')'){
                if(s[i]=='(')
                    p++;
                else
                    vec.push_back(k++);
            }
            else{
                if(++q>p)break;  //测试用例中有‘)’个数多于‘(’个数的情况，故加入该判断语句。
                int y=vec.back();
                vec.pop_back();
                int x=vec.back();
                vec.pop_back();
                sum+=a[x][0]*a[x][1]*a[y][1];
                a[x][1]=a[y][1];
                vec.push_back(x);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n=in.nextInt();
            int[][] a=new int[n][2];
            for(int i=0;i<a.length;i++){
                for(int j=0;j<a[0].length;j++){
                    a[i][j]=in.nextInt();
                }
            }
            String str=in.next();
            System.out.println(getTimes(a,str));
        }
    }
    
    public static int getTimes(int [][] a,String str){
        int sum=0;
        int n=a.length-1;
        Stack<Integer> stack =new Stack<Integer>();
        for(int i=str.length()-1;i>=0;i--){
            char s=str.charAt(i);
            if(s==')'){
                stack.push(-1);
            }
            else{
                if(s=='('){
                    int b=stack.pop();
                    int c=stack.pop();
                    sum+=a[b][0]*a[c][0]*a[c][1];
                    a[b][1]=a[c][1];
                    stack.pop();
                    stack.push(b);
                }
                else{
                    stack.push(n);
                    n--;
                }
            } 
        }
        return sum;