Description
Determine whether a matrix contains at least a legal infix expression from the top-left corner to the bottom-right corner. If yes, convert it based on the postfix notation.
- Each cell can be reached by up to four directions (up, down, right, left)
- No cycles in the infix expression
- The priority directions are: down>right>left>up
- Matrices are consisted of 1~9, +,-,*,/, (, )
- The consecutive numbers are considered as one operand
- There is no negative number (e.g., -5 is illegal)
- Use a space to separate operands and operators
- Matrix width and height < 100
Some valid expression examples
- 12345
- ( ( 12345 ) )
- 1 + ( ( 2 ) )
Some illegal expression examples
- ( ) + ( 3 )
- - 4 + 3
- 3 + ( - 4 )
- + 5 + 5
- 3 ( 1 + 2 )
Input
The first number is the total number of matrices.
The second and third numbers are the width and height of the first matrix.
Then the first matrix is listed.
So on and so forth.
Output
Repeat all inputs.
Find the first valid infix expression in the matrix.
If the matrix is found, print "Yes" then the expression, then the postfix format of the expression.
If there is no valid infix expression in the matrix, print "No"