We want to write a program to evaluate sparse matrix expressions. Data structure techniques including Infix to postfix conversion, sparse matrix operations (addition, multiplication, and transposition) and expression evaluation are needed by this program.
The first integer indicates how many sparse matriics are defined (i.e., are assigned values).
This integer can take value between zero and 26 (including zero and 26).
Please note that this integer is unrelated to the number of distict operands (i.e., matrix names) appeared in the arithmetic expressions that the program needs to handle.
For each defined matrix, firstly, a character (capitalized A~Z) indicates the name of the matrix.
Following the name, the first line comprises three integers indicating the number of rows, columns, and nonzero terms of the matrix, respectively.
For example, a line of "100 20 30" indicates that the matrix has 100 rows, 20 columns, and 30 nonzero terms.
For simplicity, we can assume the dimension is at most 100 * 100.
Next, there are multiple lines corresponding to said number of nonzero terms, each line corresponding to a nonzero term.
For example, a line of "5 3 -4" denotes that the entry with the row index equal to 5 and the column index equl to 3 of the matrix is -4.
Please note that row and column indices are zero-based, and the value of matrix entry is of the (signed) integer type.
After the said number of matrics are defined, an integer describes the number of expressions the program needs to handle.
Next, there are multiple lines, and each line comprises an arithmetic expression.
Arithmetic expressions can comprise the following components:
Operands:
Captalized character A to Z
Please note that even if the number of sparse matrics defined (the first integer of the inputs) is zero, an arithmetic expression still comprises operands.
In this case, the program only performs infix to postfix conversion but does not perform expresion evaluation.
As long as the number of sparse matrics defined (the first integer of the inputs) is nonzero, it is guaranteed that in the test cases, all operands in the expressions have their values defined.
Operators:
+ : add
- : subtract
* : multiply
' : transpose
Delimeters:
( : left parenthesis
) : right parenthesis
The inputs end here. The inputs comprise only one group of matrix definitions and expressions as described above.
For each expression:
First, the program is required to output the expression using post-fix notatoins.
Second, if the number of defined matrics is not zero, the program is required to evaluate the expression and output the evaluation results.
The format of the evaluation results is the same as the sparse matrix representation used in the inputs:
A line indicates the number of rows, columns, and non-zero terms of the resulting matrix.
For each nonzero terms, a line indicates its row index, column index, and value.
Please note that zero terms are required to be eliminated.
Please also note that there is no space characters at the end of each output line, and the last output line comprises a newline character.