Sane's Monthly Algorithms Challenge: November 2008

For no apparent reason (why else?), you have decided to create your own interpreter which evaluates mathematical expressions by "befungulating" an inputted grid of characters.

The grid is given to you as an ~n \times m~ (~n~ rows, ~m~ columns) matrix of the following characters:

0–9	Each of the ~10~ digits represents a single digit number as usual
+	Add
-	Subtract
*	Multiply
/	Integer division
%	Remainder (mod)
>	Continue reading instructions in the right direction
<	Continue reading instructions in the left direction
^	Continue reading instructions in the upward direction
v	Continue reading instructions in the downward direction
X	Print the integer value followed by a newline. Stop and exit.

Any other characters should be ignored.

To befungulate a grid of characters, you start at the top-left of the grid, and read right until you find a valid character. If the character is an operator or operand, you intuitively use the character in the evaluation of the mathematical expression (i.e. as you would with a normal calculator).

If you hit a directional operator (>, <, ^, or v), you change the direction of reading the grid.

You may assume:

• All operands are single digits.
• The sequence of operators and operands makes sense.
  (e.g. 5+3*9 is valid. 53, +3*, and 3**9 are not)
  With exception to an expression interrupted by an error (see Error Handling, below).
• The order of operations does not matter (evaluate left to right).
• An X will not be interpreted if no value has been defined.
• The calculation will fit within a normal integer data type.

Error Handling:

If you end up reading off the grid, then output Invalid Direction with a newline and quit.
If you divide by zero, then output Zero Division Error with a newline and quit.
If you modulate by zero, then output Invalid Modulo with a newline and quit.
If you end up in an infinite loop, then output Infinite Loop with a newline and quit.
Errors occur in the order that they are interpreted (e.g. If there is both Zero Division and Invalid Direction, Zero Division must be interpreted first).

Input Specification

On the first line are integers ~n~ and ~m~ ~(1 \le n, m \le 100)~.
On the next ~n~ lines are ~m~ characters each, representing the row of characters. These characters are listed from "left" to "right". The rows are listed from "top" to "bottom".

Output Specification

See problem statement.

Sample Input 1

1 14
1+2*3/4+9%4-1X

Sample Output 1

2

Explanation of Sample 1

1+2*3/4+9%4-1
= 3*3/4+9%4-1
= 9/4+9%4-1
= 2+9%4-1
= 11%4-1
= 3-1
= 2

Sample Input 2

2 2
>v
^<

Sample Output 2

Infinite Loop

Sample Input 3

7 8
....v...
........
>../5X..
........
^9*1+..<
....7...
....>*2^

Sample Output 3

45

Explanation of Sample 3

5+7*2+1*9/5
= 12*2+1*9/5
= 24+1*9/5
= 25*9/5
= 225/5
= 45

Sample Input 4

3 15
vPrimality test
>1*2*3*4*5*6*7v
X......for 8!%<

Sample Output 4

0