PROBLEM STATEMENT
When a mathematical expression is evaluated parentheses are evaluated from the
deepest nest out. Thus in the expression (1 + (2 * 3)), 2 * 3 is evaluated to
6 before being added to 1. However, sometimes people make untrue assumptions
about the order in which an expression should be evaluated.
You will be given a mathematical expression containing the operators '+', '-',
'*', '%' and integers (or possibly no operators and just one integer). The
expression will be entirely unparenthesized. Your job is to determine the
result of every possible parenthesization of the expression and determine how
many of the results are distinct.
The '%' operator is the modulus operator. a % b is defined as the remainder
when a is divided by b. Thus 7 % 3 = 1.
If a is negative, then the result of the operator should be the negative result
of (-a) % b. Thus, -5 % 3 = -(-(-5) % 3) = -(5 % 3) = -2
If b is negative, it is treated the same as though it were positive.
If b == 0, the operator is undefined and that particular parethesization should
not be evaluated. (see example 2)
The input expression will be formatted as follows:
<expression> ::= <num> | <num><sp><op><sp><expression>
<op> ::= '-' | '+' | '*' | '%'
<num> ::= a postive integer
<sp> ::= ' '
After an expression has been parenthesized, it will conform to the following
grammar:
<parenthesized> ::= <num> | '('<parenthesized><op><parenthesized>')'
Thus, a parenthesized expression can only contain either two numbers, a number
and another parenthesized expression, or two parenthesized expressions. See
example 1 for an example of how an expression can be parenthesized.
DEFINITION
Class: Parenthese
Parameters: String
Returns: int
Method signature (be sure your method is public): int countInts(String
expression);
NOTES
- Assume nothing about order of operations. Each parenthesization must be such
that there is absolutely no ambiguity about the order in which the operations
should be performed. Although 1 * 2 + 3 would normally be evaluated as (1 * 2)
+ 3, given standard precedence rules, you must consider the case 1 * (2 + 3) as
well.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- expression contains only the operators '+', '-', '*', '%', and digits 0 to 9,
inclusive
- there will be between 1 and 13 numbers, inclusive
- every pair of adjacent numbers will be separated by exactly one spaces, an
operator and exactly one more space
- all numbers will be integers in the range 0 to 99 (inclusive)
- all parenthesizations and subparenthesizations will result in numbers between
-(2^31) and (2^31)-1, inclusive
- expression will not begin or end with an operator
- expression will not begin or end with a space
- numbers will not have leading '0's, unless they are 0. i.e. 001 and 00 are
NOT valid numbers
EXAMPLES
1. expression = "1 % 2 + 3 * 4"
there are 5 possible parenthesizations:
(1 % 2) + (3 * 4) = 13
1 % (2 + (3 * 4)) = 1
1 % ((2 + 3) * 4) = 1
((1 % 2) + 3) * 4 = 16
(1 % (2 + 3)) * 4 = 4
there are 4 distinct values, so the method should return 4.
2. expression = "1 % 1 - 1"
(1 % 1) - 1 = -1
1 % (1 - 1) = 1 % 0. We do not evaluate expressions with a 0 on the right hand
side of the '%', so we simply skip this one. Thus the method returns 1
3. expression = "1 % 2 + 3 * 4 - 5"
can be parenthesized to give any number in the set: {-4,-2,-1,0,1,8,11}, thus
the method returns 7.
4. expression = "1 + 2 + 3 + 4" returns 1
5. expression = "11 * 11 - 6 + 6" returns 4
6. expression = "1 % 10 * 10 * 10 * 10 * 10 * 10 * 10 * 11 * 9" returns 9
7. expression = "3" returns 1