TopCoder problem "ParenReduction" used in SRM 224 (Division II Level Three)

Problem Statement


In mathematics, we don't bother to parenthesize every expression. For example, we write "a*b+c*d" instead of "((a*b)+(c*d))". To make sense of unparenthesized expressions, we depend on two ideas: precedence and associativity. For this problem, we will only consider the operations of exponentiation ('^'), multiplication ('*'), division ('/'), addition ('+'), and subtraction ('-').

There are three levels of precedence. Exponentiation has the highest precedence, multiplication and division have the middle level of precedence, and addition and subtraction have the lowest level of precedence. Unless overridden by parentheses, an operator with a higher level of precedence is executed before an operator with a lower level of precedence. For example, "a+b*c" means "a+(b*c)", and "d^e/f" means "(d^e)/f".

The order of execution among unparenthesized operators at the same level of precedence is determined by associativity. Exponentiation is right associative, meaning that, when there are several exponentiation operators, the rightmost is executed first. For example, "a^b^c" means "a^(b^c)". Division and subtraction are left associative, meaning that, when there are several divisions or several subtractions, the leftmost is executed first. For example, "a-b-c" means "(a-b)-c". Multiplication and addition are associative, meaning that, when there are several multiplication operators or several addition operators, it doesn't matter which one is executed first. For example, "a*b*c" can mean either "(a*b)*c" or "a*(b*c)" because the two parenthesizations are equivalent.

When mixing different unparenthesized operators at the same level of precedence, either multiplication and division or addition and subtraction, the interplay between associativity and left associativity is complicated. The operators can be executed in any order as long as each division or subtraction is executed before the operator to its immediate right. For example, "a*b/c*d" can mean "((a*b)/c)*d" or "(a*(b/c))*d" or "a*((b/c)*d)" but not "(a*b)/(c*d)" or "a*(b/(c*d))". Similarly, "a-b+c-d" can mean "((a-b)+c)-d" or "(a-b)+(c-d)" but not "a-((b+c)-d)" or "a-(b+(c-d))" or "(a-(b+c))-d".

You will be given a fully parenthesized expression as a String expr satisfying the following grammar:

   <expr> = <lowercase letter>
          | "(" <expr> <op> <expr> ")"
   <op>   = "^" | "*" | "/" | "+" | "-"
No letter will be used more than once in the same expression. Your task is to remove all unnecessary parentheses and return the resulting expression, also as a String. The expression cannot be changed in any way other than removing parentheses. For example, "(a-(b+c))" cannot be changed to "a-b-c". Similarly, you should make no use of algebraic laws other than those described above. For example, "(a-(b-(c-d)))" cannot be changed to "a-(b-c)-d".


Method signature:String pretty(String expr)
(be sure your method is public)


-expr contains between 1 and 49 characters, inclusive.
-Each character of expr is a lowercase letter ('a'-'z'), a parenthesis ('(',')'), or a binary operator ('^','*','/','+','-').
-No letter appears more than once in expr.
-expr satisfies the grammar given in the problem statement.


Returns: "a-b/c^d"
Exponentiation has higher precedence than division and division has higher precedence than subtraction.
Returns: "e*(f+g+h)*i"
Multiplication has higher precedence than addition. Both are associative.
Returns: "(a-(b-c)-d)^(e/f/(g/h))"
Subtraction and division are both left associative.
Returns: "x"
Returns: "(a+l-g+o)^(r/i*t/h*m)"
Returns: "((t-k/(o*m))*c*f*(n/j+v-z))^l/(x-h)"

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

String Manipulation, String Parsing