TopCoder problem "Untypeset" used in SRM 206 (Division II Level Three)



Problem Statement

    

There are several software packages that typeset mathematical expressions. For example, the expression "(31+24/12)/(5+6) + 16" might be typeset like this: 


    "       24       "
    " 31 + ----      "
    "       12   + 16"
    "-----------     "
    "   5 + 6        "

Write a method that takes such a typeset mathematical expression and evaluates it, returning the numerical value of the expression. If given the expression above, your method should return 19.

The input expression will be a two-dimensional array of characters, given as a String[]. Expressions will be built out of other expressions, rectangular portions of the given array. Every expression will be in one of three forms:

  • integer constant: The expression will be exactly one character high, will consist solely of digits, and will not contain any leading zeros.

  • addition: The expression will be constructed out of left and right subexpressions. Zero or more rows of spaces will be added above and below each subexpression and will give them the same height. Three columns of that height will be placed between them, containing all spaces, except for a single '+' character anywhere in the middle column.

  • division: The expression will be constructed out of top and bottom subexpressions. One or more columns of spaces will be added to the left and right of each subexpression to give them the same width. One row consisting entirely of '-' characters will be placed between them.

Example:

The expression above has one column (column 12) with all spaces except for a single '+' character. Therefore, this expression is built by adding two subexpressions together. If we take the regions to the left and right of column 12, and remove all rows and columns on the edges containing only spaces, we get the following two subexpressions: 


    "       24  "
    " 31 + ---- "
    "       12  "  and  "16"
    "-----------"
    "   5 + 6   "

The right subexpression contains only digits, so it evaluates to the value 16. The left subexpression has one row (row 3) with all '-' characters. Therefore, this expression is built by dividing two subexpressions. If we take the regions above and below row 3, and remove all rows and columns on the edges containing only spaces, we get the following two subexpressions: 


    "      24 "
    "31 + ----"  and  "5 + 6"
    "      12 "

Here, both subexpressions are addition. The right subexpression adds "5" and "6", resulting in the value 11. The left subexpression is built by adding two more subexpressions: 


               " 24 "
    "31"  and  "----"
               " 12 "

The left side evaluates to the value 31, and the right side evaluates to the division of the subexpressions "24" and "12". Working back up, 24 divided by 12 is 2, added to 31 is 33, divided by 11 is 3, plus 16 is 19.

 

Definition

    
Class:Untypeset
Method:evaluate
Parameters:String[]
Returns:int
Method signature:int evaluate(String[] expression)
(be sure your method is public)
    
 

Notes

-All division is guaranteed to have an integer result with no remainder.
-Note that division by zero is not possible.
 

Constraints

-expression will contain between 1 and 50 elements, inclusive.
-Each element of expression will contain between 1 and 50 characters, inclusive.
-Each element of expression will be the same size.
-Each element of expression will consist entirely of characters in the String "0123456789-+ ".
-expression will be formatted according to the rules specified in the problem statement.
-The result, all integer constants, and all intermediate computed values will be between 1 and 1000000, inclusive.
 

Examples

0)
    
{ "2801" }
Returns: 2801
1)
    
{ "  625       ",
  "------------",
  "        5   " }
Returns: 125
Any number of spaces could be added to the left or right of the numerator and denominator of fractions. But the row of '-' characters will always span the entire row.
2)
    
{ "       ",
  "500    ",
  "       ",
  "    +  ",
  "       ",
  "       ",
  "      1",
  "       ",
  "       " }
Returns: 501
Any number of blank rows could be added above and below the subexpressions before addition.
3)
    
{ "   120   ",
  "  -----  ",
  "    10   ",
  "---------",
  "    6    ",
  "   ---   ",
  "    2    " }
Returns: 4
Nested fractions are never ambiguous. There can never be two rows of '-' characters that fill an entire row.
4)
    
{ "       24       ",
  " 31 + ----      ",
  "       12   + 16",
  "-----------     ",
  "   5 + 6        " }
Returns: 19
This is the example from the problem statement.
5)
    
{"3 + 4 + 6"}
Returns: 13
6)
    
{ " 1     4     9 ",
  "--- + --- + ---",
  " 1     2     3 " }
Returns: 6
Three or more terms may be added together. This may be (1/1 + 4/2) + 9/3, or 1/1 + (4/2 + 9/3). Both will give the same result.
7)
    
{ "34      ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "   +    ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "        ",
  "     924" }
Returns: 958

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2919

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5852&pm=2919

Writer:

legakis

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Recursion, Simple Math, String Manipulation