INTRODUCTION TO RPN
Reverse Polish Notation (RPN) is a way of expressing arithmetic or logic
equations that avoids the need for parentheses. In infix (normal) notation the
operators (such as +) come between the operands (such as the things being
added), and ambiguity arises about which order to apply the operators. In RPN,
the evaluation is done from left to right, with the operator coming after its
operands. An operand may be either a value or the result of a previous
operation.
An RPN expression can be evaluated using a stack with the following method:
Process the tokens of the expression from left to right.
When an operand (a number or variable reference) is encountered, push it
onto the stack.
When a binary operator is encountered pop two values from the stack, apply
the operator to the values, and push the result.
When a unary operator is encountered pop a single value from the stack,
apply the operator to the value, and push the result.
If the RPN expression is properly formed then after all of the tokens from the
expression have been processed there will be a single value remaining on the
stack. This value will be the result of the expression. Consider the expression
"3 5 + 2 *"
1. 3 is an operand, so push it onto the stack.
2. 5 is an operand, so push it onto the stack.
3. + is a binary operator, so pop two values (3 and 5) from the stack, add
them, then push the result (8) onto the stack.
4. 2 is an operand, so push it onto the stack.
5. * is a binary operator, so pop two values (8 and 2) from the stack,
multiply them, then push the result (16) onto the stack.
6. After all of the tokens are processed the stack contains the single value
16.
So "3 5 + 2 *" evaluates to 16.
PROBLEM STATEMENT
You are to create a class RPNSolver that contains the method countTrue. The
method should take an RPN expression that may contain references to an unknown
variable X. The method should return the number of different integral values
of X that make the expression evaluate to true. The values (operands) in the
expression will be either numeric constants or "X", the unknown value. The
operators in the expression will be either <, &&, ||, or !. All numbers
(numeric constants and possible values of X) are constrained to integral values
between 0 and 999,999,999 inclusive. TopCoder will ensure that the input is
valid.
DEFINITION
Class: RPNSolver
Parameters: String
Returns: int
Method signature: int countTrue(String expr) (make sure your method is public)
NOTES
- The < operator takes two numeric operands and returns true if the left
operand is less than the right operand, false otherwise.
- The && operator takes two boolean operands and returns true if both operands
are true, false otherwise.
- The || operator takes two boolean operands and returns true if either operand
is true, false otherwise.
- The ! operator takes a single operand and returns true if the operand is
false, false otherwise.
INPUT CONSTRAINTS
TopCoder will ensure that the input is a valid RPN expression. An expression
is valid if all of the following criteria are met:
- The < operator is always given two numeric operands (X counts as a numeric
operand).
- The && and || operators are always given two boolean operands.
- The ! operator is always given a single boolean operand.
- The number of binary operators (<, &&, or ||) present in the expression is
equal to 1 less than the number of numeric operands (numeric values or
references to the unknown value X).
- The RPN expression evaluates to a boolean value.
- All operands directly given in expr are either a numeric constant in the
range of 0 to 999,999,999 inclusive or a reference to the unknown value X.
- All operators are chosen from the set [<, &&, ||, !].
- The expression consists of at most 50 characters.
- The elements in the expression are separated by exactly one space.
- There is no space preceding the first element.
- There is no space after the last element.
EXAMPLES
"X 100 < ! X 200 < &&" can be expressed in infix notation as !(X < 100) && X <
200. This encodes the test that X is greater than or equal to 100 and X is
less than 200. There are exactly 100 integral values that satisfy this
constraint (the natural numbers from 100 to 199 inclusive), so the return value
from countTrue should be 100.
"10 10 <" is never true. No possible value of X can make it true, so the
method returns 0.
"10 20 <" is always true. All possible values of X are solutions, so the
method returns 1000000000.
"X 100 < ! X 200 < && X 50 < ||" returns 150.
"X 999 < !" returns 999999001.
"X X <" returns 0.