Removing Parentheses
Time limit2sMemory limit128 MB
Given an arithmetic expression with letters and +,-,*,/,() parse it and print an equivalent expression using the fewest parentheses, applying sign/operator flips when parentheses are removed.
- Level
Medium5 of 10
- Topics
- Recursion, String, Implementation
- Solved
- No attempts yet
Problem
You are given a valid expression made only of lowercase English letters, the operators +, -, *, /, and parentheses. The grammar is defined as follows.
- A lowercase letter is a character.
- A term,
expression+term, andexpression-termare expressions. - A factor,
term*factor, andterm/factorare terms. - A character and
(expression)are factors.
This grammar gives * and / higher precedence than + and -, and operators with the same precedence group from left to right.
You may remove parentheses only when the meaning of the expression does not change. Parentheses after + may be expanded as they are. When parentheses after - are expanded, the exposed + and - operators inside them are swapped. Similarly, if the parentheses after * contain one term, they may be expanded as they are. When such parentheses are expanded after /, the exposed * and / operators inside them are swapped.
Given an expression, output an equivalent expression with the minimum possible number of parentheses.
Input
The first line contains an expression with no spaces. Its length is at most 1,000.
Output
Print an expression with no spaces that has the minimum possible number of parentheses.