矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数。
数据范围：矩阵个数：
，行列数：
，保证给出的字符串表示的计算顺序唯一。
进阶：时间复杂度：%5C)
，空间复杂度：
[编程题]矩阵乘法计算量估算
- 热度指数：77080 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！
输出描述:
输出需要进行的乘法次数
示例1
输入
3 50 10 10 20 20 5 (A(BC))
输出
3500
思路：构造一颗二叉树，递归计算左右子树的计算量， 再加上左子树矩阵*右子树矩阵的计算量。
坑：测试数据存在右括号多于左括号数量的情况，需要特殊处理一下。
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. 计算子树乘法次数，再加上左子树矩阵*右子树矩阵的计算量。
*/
发表于 2020-07-07 12:28:30
回复(1)
哈哈，***测试集了，有一个多了一个右括号
package com.special.spet;
import java.util.Scanner;
/**
* 矩阵相乘估计乘数次数
* 利用数组代替栈，那你自己就要千万小心入栈出栈了
* 思想：遇到(的时候什么都不做，遇到字母时，矩阵信息变量入数组栈
* 遇到）的时候，弹出2个矩阵信息量，计算完乘法次数**栈
* 此题本来是严格按照(A(BC)) 也就是严格用一个括号扩住2个变量的
* 谁知道有一个测试集多了一个右括号，真变态啊，擦，所以我加了一个判断
* 如果遇到右括号时，若当前栈只有一个操作数，continue,走你，大爷的，出题人太不小心了
* @author special
* @date 2017年12月1日 下午3:01:22
*/
class InformationOfMatrix{
int row;
int col;
public InformationOfMatrix(int row, int col){
this.row = row;
this.col = col;
}
public int getMutipleTimes(InformationOfMatrix B) { return this.row * this.col * B.col; }
}
public class Pro69 {
public static int getCaulateTimes(InformationOfMatrix[] inputMatrixs, String rule){
InformationOfMatrix[] stackMatrix = new InformationOfMatrix[inputMatrixs.length];
int indexOfInputMatrixs = 0;
int sizeOfStack = 0;
int result = 0;
for(int i = 0; i < rule.length(); i++){
char item = rule.charAt(i);
if(item == '(') ; // 遇到(的时候什么都不做
else if(item == ')'){ //遇到）的时候，弹出2个矩阵信息量，计算完乘法次数**栈
if(sizeOfStack == 1) continue; //变态***测试集，有一个多了一个右括号
InformationOfMatrix matrixB = stackMatrix[--sizeOfStack]; //我弹
InformationOfMatrix matrixA = stackMatrix[--sizeOfStack]; //我弹
result += matrixA.getMutipleTimes(matrixB); //计算次数
stackMatrix[sizeOfStack++] = new InformationOfMatrix(matrixA.row,matrixB.col); //我入
}
else stackMatrix[sizeOfStack++] = inputMatrixs[indexOfInputMatrixs++]; //操作数入栈
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
InformationOfMatrix[] inputMatrixs = new InformationOfMatrix[n];
for(int i = 0; i < n; i++){
int row = input.nextInt();
int col = input.nextInt();
inputMatrixs[i] = new InformationOfMatrix(row,col);
}
String rule = input.next();
int result = getCaulateTimes(inputMatrixs,rule);
System.out.println(result);
}
}
}
发表于 2017-12-01 16:04:10
回复(2)
看见很多人说测试用例多了个括号，这个通过判定遇见右括号的时候栈内元素数可以避免溢出问题，大于等于2才弹栈。
利用list实现栈的操作，遇见字符压栈，遇见')'判断栈内元素个数，大于等于2弹栈两次，分别赋值jz2和jz1,计算jz1*jz2要做的乘法次数。计算完乘法次数后，将jz1*jz2的矩阵的行数和列数组成的list压栈,再循环就好了。
def cal_mul(m_list, law):
stack = []
jz1 = ''
jz2 = ''
cal_all = 0
for i in law:
if (i != '(') and (i != ')'):
stack.append(i)
elif len(stack) >= 2 and i == ')':
jz2 = stack.pop(-1)
jz1 = stack.pop(-1)
if (isinstance(jz2, list)) and (isinstance(jz1, list)):
cal_all += jz1[1] * jz2[1] * jz1[0]
stack.append([jz1[0], jz2[1]])
elif (isinstance(jz2, list)) and (isinstance(jz1, str)):
cal_all += m_list[ord(jz1) - ord('A')][1] * jz2[1] * m_list[ord(jz1) - ord('A')][0]
stack.append([m_list[ord(jz1) - ord('A')][0], jz2[1]])
elif (isinstance(jz2, str)) and (isinstance(jz1, list)):
cal_all += jz1[1] * m_list[ord(jz2) - ord('A')][1] * jz1[0]
stack.append([jz1[0], m_list[ord(jz2) - ord('A')][1]])
elif (isinstance(jz2, str)) and (isinstance(jz1, str)):
cal_all += m_list[ord(jz1) - ord('A')][1] * m_list[ord(jz2) - ord('A')][1] * m_list[ord(jz1) - ord('A')][0]
stack.append([m_list[ord(jz1) - ord('A')][0], m_list[ord(jz2) - ord('A')][1]])
elif len(stack) < 2 and i == ')':
return cal_all
return cal_all
while True:
try:
n = int(input())
m_list = []
for i in range(n):
m_list.append([int(x) for x in input().split()])
law = input()
print(cal_mul(m_list, law))
except:
break
发表于 2020-02-25 21:50:55
回复(0)
#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;
}
}
发表于 2019-08-10 18:21:19
回复(0)
栈里面保存数组下标。偷个懒，每次计算新值后，将下标99(每次递减)加入栈中。
碰到左括号入栈，字符化为下标入栈。碰到右括号，将数字出栈。然后弹出左括号。计算这些值，然后在入栈。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] fax=new int[100][2];
for (int i = 0; i <n; i++) {
fax[i][0]=scanner.nextInt();
fax[i][1]=scanner.nextInt();
}
String rex = scanner.next();
Stack<Integer> stack= new Stack<>();
int ans=0;
int ttt=99;
for (int i = 0; i <rex.length(); i++) {
char c=rex.charAt(i);
if(rex.charAt(i)=='('){
stack.push(-1);
}else if(c>='A'&&c<='Z'){
stack.push(c-65);
}else if(c==')'){
ArrayList<Integer> list = new ArrayList<>();
while(stack.peek()!=-1){
list.add(stack.pop());
}
stack.pop();//弹出 (
if(list.size()==1) {
stack.push(list.get(0));
continue;
}
ArrayList<Integer> list1 = new ArrayList<>();
for (int j =list.size()-1; j>=0; j--) {
list1.add(list.get(j));
}
int nn,mm;
nn=fax[list1.get(0)][0];
mm=fax[list1.get(1)][1];
ans+=nn*mm*fax[list1.get(0)][1];
for (int j = 2; j <list1.size(); j++) {
mm=fax[list1.get(j)][1];
ans+=nn*mm*fax[list1.get(j)][0];
}
fax[ttt][0]=nn;
fax[ttt][1]=mm;
stack.push(ttt);ttt--;
}
}
System.out.println(ans);
}
}
发表于 2022-05-28 15:25:14
回复(0)
#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--;
}
发表于 2021-09-05 17:57:19
回复(0)
#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;
}
发表于 2021-08-22 18:18:13
回复(0)
用栈求解，思路和字符串表达式计算类似，但除了表达式字符栈之外，还需要一个size栈来记录矩阵的尺寸。对于一个中间计算得到的矩阵，我们还需要把它的尺寸压入size栈中。与此同时，这个中间矩阵随便用一个非字母字符来代替，压入表达式字符栈中。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
import java.util.HashMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line = br.readLine()) != null) {
Stack<Character> stack = new Stack<>();
Stack<int[]> size = new Stack<>(); // 存储矩阵的尺寸
HashMap<Character, int[]> map = new HashMap<>();
int n = Integer.parseInt(line.trim());
String[] params;
for(int i = 0; i < n; i++){
params = br.readLine().trim().split(" ");
int row = Integer.parseInt(params[0]);
int col = Integer.parseInt(params[1]);
map.put((char)(65 + i), new int[]{row, col});
}
int res = 0;
char[] expr = br.readLine().trim().toCharArray();
for(int i = 0; i < expr.length; i++){
if(stack.isEmpty() || expr[i] != ')'){
stack.push(expr[i]);
if(expr[i] != '(') size.push(map.get(expr[i]));
}else{
while(!stack.isEmpty() && stack.peek() != '('){
int[] params2 = size.pop();
stack.pop();
if(!stack.isEmpty() && stack.peek() == '(') break;
if(!size.isEmpty()){
int[] params1 = size.pop();
stack.pop();
res += params1[0]*params1[1]*params2[1]; // 增加计算量
size.push(new int[]{params1[0], params2[1]});
}else
break;
}
if(!stack.isEmpty()) stack.pop();
stack.push('#'); // 中间结果矩阵
}
}
System.out.println(res);
}
}
}
编辑于 2021-04-01 17:14:25
回复(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;
}
发表于 2020-08-31 17:33:01
回复(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
编辑于 2020-08-31 16:16:06
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[][] arr = new int[n][2];
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[0].length;j++){
arr[i][j] = sc.nextInt();
}
}
String s = sc.next();
System.out.println(returnTimes(arr,s));
}
}
public static int returnTimes(int[][] arr, String s){
Stack<Integer> stack = new Stack<>();
int sum = 0;
int n=arr.length-1;
for(int i=s.length()-1;i>=0;i--){
char ch = s.charAt(i);
if(ch==')'){
stack.push(-1);
}else{
if(ch=='('){
int b = stack.pop();
int c = stack.pop();
sum+=arr[b][0]*arr[b][1]*arr[c][1];
arr[b][1] = arr[c][1];
stack.pop();
stack.push(b);
}else{
stack.push(n);
n--;
}
}
}
return sum;
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[][] arr = new int[n][2];
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[0].length;j++){
arr[i][j] = sc.nextInt();
}
}
String s = sc.next();
System.out.println(returnTimes(arr,s));
}
}
public static int returnTimes(int[][] arr, String s){
Stack<Integer> stack = new Stack<>();
int sum = 0;
int n=arr.length-1;
for(int i=s.length()-1;i>=0;i--){
char ch = s.charAt(i);
if(ch==')'){
stack.push(-1);
}else{
if(ch=='('){
int b = stack.pop();
int c = stack.pop();
sum+=arr[b][0]*arr[b][1]*arr[c][1];
arr[b][1] = arr[c][1];
stack.pop();
stack.push(b);
}else{
stack.push(n);
n--;
}
}
}
return sum;
}
}
发表于 2020-07-13 10:24:48
回复(0)
# 吐了测试样例有错误
'''
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
发表于 2020-04-13 14:07:49
回复(2)
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
发表于 2020-04-12 12:51:58
回复(0)
#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;
}
发表于 2018-06-10 01:24:33
回复(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);
}
}
发表于 2017-07-04 15:08:47
回复(0)
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
发表于 2017-03-23 00:07:49
回复(0)
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);
}
}
}
编辑于 2018-03-26 13:11:45
回复(0)
#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;
}
发表于 2017-05-05 11:13:58
回复(5)
#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;
}
编辑于 2016-08-27 19:14:18
回复(17)
问题信息
难度：
336条回答
2195收藏
34548浏览
通过挑战的用户
查看代码-
2022-09-20 10:34:20 -
2022-09-19 13:21:16
-
2022-09-16 10:49:21
-
2022-09-16 10:05:16
-
2022-09-16 08:49:35
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
