PROBLEM STATEMENT
Given a fully parenthesized expression and a list of relative priorities of
operations allowed within the expression, remove as many pairs of parentheses
as possible without altering the order of evaluation of the expression.
DEFINITION
Class name: Parenthesizer
Method name: minParen
Parameters: String, String
Return type: String
Method signature (be sure your method is public): String minParen (String
expression, String operators);
String expression contains a fully parenthesized expression composed of
variable names, operators, and parenthesis. String operators contains special
characters denoting left-associative binary operators within the expression.
Operators are listed in the order of decreasing precedence. For example, if
operators = "*+", the '*' operator has higher precedence than the '+' operator.
Your method should return the initial expression, possibly with some of the
parentheses removed. Your method should not alter the expression in any other
way. In particular, your method should not alter the order in which the
expression components are listed.
Here is the BNF for the input expression:
Expression ::= '(' Expression Operation Expression ')' | Variable
Operation ::= '+' | '-' | '*' | '/' | '^'
Variable ::= 'a'.. 'z'
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- Each binary operation within the expression is enclosed in parentheses. This
in effect fixes the order of evaluation of the expression.
- All variable names inside the expression consist of a single lower-case
character.
- The expression is 1 to 50 characters in length, inclusive.
- The operators consist only of characters "+-*/^" (quotes are for clarity only).
- No operator is listed more than once within the operators String.
- All operators from the expression are listed in the operators String.
NOTES
- Your method should assume a left-to-right order of expression evaluation.
Therefore, if expression = "((a+b)*c)", and operators = "*+", minParen should
return "(a+b)*c". This is because '*' has higher precedence than '+', but
according to parenthesized expression the '+' has to be evaluated first. On the
other hand, if operators = "+*", minParen should return "a+b*c".
- Your method should assume that all operations are both left- and
right-associative. This means that if expression = "(a+(b+c))", and operators =
"+", your method should return "a+b+c", even though b+c was evaluated first in
the original expression.
- Your method should not assume that operator symbols have any mathematical
meaning.
EXAMPLES
- If expression = "((a*b)+(c*d))" and operators = "*+", minParen should return
"a*b+c*d".
- If expression = "((a*b)+(c*d))" (same as above) and operators = "+*",
minParen should return "(a*b)+(c*d)".
- If expression = "((((((((((a+b)-c)*(d/e))*f)/(g^h))/j)^k)*l)+m)-n)" and
operators = "+-*/^", minParen should return "((a+b-c*(d/e)*f/(g^h)/j^k)*l)+m-n".
- If expression = "((((((((((a+b)-c)*(d/e))*f)/(g^h))/j)^k)*l)+m)-n)" (same as
above) and operators = "-+/*^", minParen should return
"(((((a+b)-c*d/e*f)/(g^h)/j^k)*l)+m)-n".
- If expression = "a", minParen should return "a".
- If expression = "((a+b))" and operators = "+", minParen should return "a+b".