利用栈进行计算,先将矩阵入栈,遇到右括号时出栈两个矩阵,计算乘法次数,然后将两个矩阵相乘得到的矩阵入栈。
#include <iostream> #include <vector> #include <sstream> using namespace std; string cal_multime(string &m1, string &m2, int ×) { int m1_row, m1_col, m2_col; stringstream ss(m1); ss >> m1_row >> m1_col; ss.clear(); ss.str(m2); ss >> m1_col >> m2_col; times = m1_row * m1_col * m2_col; ss.clear(); ss.str(""); ss << m1_row << ' ' << m2_col; return ss.str(); } int pop_and_cal(vector<string> &values) { string m1, m2, m3; int ret; m2 = values.back(); values.pop_back(); m1 = values.back(); values.pop_back(); m3 = cal_multime(m1, m2, ret); values.push_back(m3); return ret; } int solve(vector<string> &inputs, string &rules) { vector<string> values; int result = 0; int i=0; for(char c : rules) { if (c == ')') { result += pop_and_cal(values); } else if (c >= 'A' && c <= 'Z') { values.push_back(inputs[i]); i++; } } while(values.size() > 1) result += pop_and_cal(values); return result; } int main() { int total; while(cin >> total) { vector<string> inputs; string ops; string line; getchar(); for(int i=0; i<total; i++) { getline(cin, line); inputs.push_back(line); } getline(cin, ops); cout << solve(inputs, ops) << endl; } return 0; }