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".
|