A teacher's worked solution is full of brackets that do nothing. The expression expr uses
names, the binary operators +, - and *, and round brackets. The usual rules apply: *
is done before + and -, and operators of the same kind are done left to right. A name is a
lowercase letter followed by zero or more digits (a, x7, v123), and no name appears twice.
There are no spaces and no unary minus.
Write fewest_brackets(expr) that deletes as many bracket pairs as possible so that the
expression still gives the same value for every choice of numbers for the names. Keep
everything else in place and return the new string.
Examples
Input: expr = "((a-b))-(c*d)"
Output: "a-b-c*d"
Input: expr = "x-(y-z)+(p+q)*r"
Output: "x-(y-z)+(p+q)*r"
Explanation: removing either pair changes the value (for example x-y-z is not x-(y-z)).
Input: expr = "((a+b))*c"
Output: "(a+b)*c"
Explanation: one of the doubled pairs is spare; the other one is needed.
Constraints
1 <= len(expr) <= 3 * 10**5;expris a valid expression- brackets may be nested up to
10**5deep
Goals
- Match brackets with a stack and remember what each group contains
- Decide from a group's contents and its two neighbours whether its brackets matter
- Handle nested and doubled brackets without recursion