PROBLEM STATEMENT:
Given an expression involving unions, intersections, and differences of sets,
determine which numbers in a list are in the set specified by the expression.
The expression will contain sets and set operations. All sets will contain
only integers.
Sets will be of the following forms:
(a, b) : Meaning all integers x satisfying a < x < b (That is open-paren,
closed-paren)
[a, b] : Meaning all integers x satisfying a <= x <= b (That is open-bracket,
closed-bracket)
(a, b] : Meaning all integers x satisfying a < x <= b (That is open-paren,
closed-bracket)
[a, b) : Meaning all integers x satisfying a <= x < b (That is open-bracket,
closed-paren)
{a1, a2, ... an } : Meaning the n integers a1, a2, ... and an. n is the
number of elements in the set, and must be greater
than 0. (That is open-curly-brace, closed-curly-brace)
Operations will be:
n : intersection - The intersection of two sets is the set of integers
in both sets. That is, A n B is equal to the set of integers
x such that x is in A and x is in B.
u : union - The union of two sets is the set of integers in either or both
sets. That is A u B is equal to the set of integers x such that
x is in A or x is in B (or x is in A and B).
- : difference - The difference of two sets is the set of integers in
the first set but not in the second set. (A - B is the
set of integers in A but not in B).
Operations can be grouped in parentheses to enforce the operations in
parentheses are performed before the operations not in parentheses. In the case
of no parentheses, assume the set operations all have the same precedence and
evaluate them from left to right.
You are to write a class SetOperations, which contains a method getNumbersIn,
which takes an expression (String) and list of integers (int[]) as parameters
and returns a list of integers (int[]) that is the integers given in the
inputted list that are in the set specified by expression. The returned
integers should be in the same relative order as the inputted integers.
DEFINITION:
Class Name: SetOperations
Method Name: getNumbersIn
Parameters: String, int[]
Returns: int[]
Method Signature: (be sure your method is public) int[] getNumbersIn(String
expression, int[] numbers)
TOPCODER WILL VERIFY:
* expression will contain a valid set expression containing at most 50
characters.
* Elements of numbers are integers between -1000 and 1000, inclusive.
* numbers will contain between 0 and 50 elements, inclusive.
An expression is valid if:
* It contains only digits, spaces, and the characters 'n', 'u', '-', '(', ')',
'[', ']', '{', and '}',
* Sets must contain values between -1000 and 1000, inclusive.
* All sets are of one of the forms above.
* All parentheses specifying operator order are well balanced.
* All operators will have a set (or something evaluating to a set) on either
side.
* White space can occur anywhere except in the middle of numbers.
NOTE:
* The same int may be in numbers more than once, in which case it should be
returned more than once if it is in the set represented by expression.
EXAMPLES:
If expression = "( 1, 3) n [2,4]" and numbers = {0, 1, 2, 3, 4, 5},
( 1, 3) is the set {2} and [2,4] is the set {2, 3, 4}.
The expression evaluates to the set {2}, so the method should return {2}.
If expression = "({1, 2, 3, 4}) u ((( (5,6) n [5,6])))" and numbers = {0, 4, 3,
2, 1, 4, 3, 2, 1, 1, 0},
First, the operation in the parentheses is done (5,6) n [5,6] = {} and then the
union is done, with the final result being {1, 2, 3, 4} so the method should
return {4, 3, 2, 1, 4, 3, 2, 1, 1}.
If expression = "[-001000, 1000] - (-1000, 001000)" and numbers = {-1000, 0,
1000},
The expression evaluates to {-1000, 1000} and thus the method returns {-1000,
1000}.
If expression = "[1,8]" and numbers = {-10, 10}, the method returns {}.
If expression = "[1,8]" and numbers = {-10, 5, 10}, the method returns {5}.
If expression = "[-1000, 1000] n [3, 2]" and numbers = {1, 2, 3, 4}, the method
returns {}.
If expression = "[4,7]u (-100 ,3] - (2,5 )" and numbers = {-1, 2, 3, 4, 5, -9,
12}, the method returns {-1, 2, 5, -9}.