| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14048 | DS_2023_Quiz_Stack&Queue |
|
Description
In this quiz, you are asked to balance parentheses.
For each input, there are N strings.
Each string only contains ‘(‘ and ‘)’, and your task is to balance the parentheses by Adding and Removing minimum parentheses. Then, you will need to output the balanced strings.
Imbalance parentheses
Imbalance parentheses is the part where does not belong to any valid substring.
For example, if the input is ()())))))(()()())(())()((()((), the red part is valid substring and the rest of the text (blue part) is imbalance substring.
Adding
You should add the parentheses next to each imbalance parenthesis to balance parenthesis.
For example, if the input is ()())))))(()()())(())()((()(()
, the blue part is imbalance parentheses, you should add parentheses like
()()()()()()()(()()())(())()()()()()()
Removing
You should remove the imbalance parentheses.
For example, if the input is ()())))))(()()())(())()((()(()
, the blue part is imbalance parentheses, you should remove parentheses like
()()(()()())(())()()()
You will need to output both the balanced strings.
Hint: Implement a stack class
Notice: Any kind of STL is not allowed in this homework. (string is allowed)
Rules of valid parentheses string:
A string is considered valid if every opening parenthesis '(' has a corresponding closing parenthesis ')' and is in the correct order.
Example:
(()()()()) is considered valid, each '(' has a corresponding ')' in the correct order.
((((()) is considered not valid, because some '(' has no corresponding ')'.
))(( is considered not valid, because the order is wrong.
Input
The first line has one number, N, indicating there are N strings needed to be balanced.
The next N lines are strings that only contains characters '(' and ')'.
Constraint:
0 < N <= 100000
0 <= length of string< 10000000
Output
For each string, you will first output the balanced string by adding, and secondly the balanced string by removing.
Note that you need to print ‘\n’ at the end of the output.