PROBLEM STATEMENT
You are given a 2-dimensional matrix consisting of digits ('0' to '9'
inclusive) and mathematical operators ('+','-','*','/'). The matrix is
represented as a String[], with the first character of the first element in the
String[] representing the leftmost element of the topmost row in the matrix.
A path is defined as a sequence of one or more locations in the matrix where:
1. The first location can be any location in the matrix.
2. Each subsequent location (if any) in the path is either one cell below or
one cell to the right of the previous location in sequence.
3. The end location can be any reachable location from the first location.
If the sequence of symbols encountered on a path form a valid expression, you
evaluate the expression and assign this value to the path you traversed. If the
symbols do not form a valid expression you assign a value of -1 to the path.
A valid expression either consists of the single digit or a valid expression
followed by an operator followed by another valid expression,etc.
i.e.
<expression> ::= <digit> | <expression><operator><expression>
<digit> ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
<operator> ::= '+'|'-'|'*'|'/'
Thus "4+3*2-1" and "4" are valid expressions , whereas "+","43+2" are not valid.
These expressions are evaluated left to right ignoring any operator precedence.
Thus "4+3*2-1" is evaluated as ((4+3)*2)-1 = 13 not as (4+(3*2))-1, as we
ignore operator precedence.
The maximum path value is the highest possible value(result after evaluting the
corresponding expression) of a path in the matrix.
Create a class MathWalk that contains a method maxPath, which takes a String[]
matrix as input and returns the String representation of the maximum path value
in this matrix.
DEFINITION
Class: MathWalk
Parameters: String[]
Returns: String
Method signature (be sure your method is public): String maxPath(String[]
matrix)
NOTES
- The return String representation of the maximum path value should be the
smallest possible decimal String representation of the value, i.e. the only
valid String representation of value 12 is "12". "012" and "+12" are invalid
representations of value 12.
- For the division('/') operator truncate the fraction part of the result if it
exists. For example, while evaluating "5/3*6", 5/3 is 1, hence "5/3*6" => "6".
- If a path is represented by an expression that involves division by zero,
assign a value of '-1' to that path.
- If there are no paths with corresponding valid expressions, return "-1".
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- Input parameter matrix contains 1 to 18 (inclusive) Strings.
- Each String in matrix contains 1 to 18 (inclusive) characters.
- All Strings in matrix are of equal length.
- All Strings in matrix consist only of digits('0'-'9' inclusive) and
operators('+','-','*','/').
EXAMPLES
matrix =
{"5+2+3",
"*2/1*",
"8+9+3"}
The path with the highest value is represented by expression "5*8+9+3", your
method should return "52".
matrix =
{"5+2+2",
"*2/1/",
"1+9-3"}
The path with the highest value is represented by expression "5*2+9", your
method should return "19".
matrix =
{"3-5*2/8"}
The path with the highest value is represented by expression "5*2", your method
should return "10".
matrix =
{"1+2/3",
"456--",
"7*8/9",
"+++00"} your method should return "56"
matrix =
{"12345",
"+-/*/",
"67890"} your method should return "36"
matrix =
{"/*-+-*"} your method should return "-1"
matrix =
{"5"} your method should return "5"