How to fix bracket sequence?

Question

Algorithms

How to fix a bracket sequence by closing brackets or deleting? I can't get hold of anything.
Example sequences:
1) [(]) (invalid, how to fix it?)
2) }])
, etc.

Answer 1

You can define such a sequence using a stack - this is a structure in memory (a regular array), where you will have to add brackets as you go through the text line with brackets. If the parenthesis is open, then push it onto the stack. If closing, then pop the corresponding opening parenthesis from the stack. And if the bracket is not the right one (the type did not match), or it is necessary to take the bracket from the empty stack, or the stack is not empty at the end of the line, then there is an error in the line.
But automatically correctmistake is a thankless task. Because the text string with the defect does not contain information about what it should be. For example, if the error is that a parenthesis is missing, how do you know where to insert the missing parenthesis? No way! Unless your string has a certain format and all sorts of hints about where this bracket can be. But even in this case, most likely, there will be ambiguity.
For example, a line from the text of the program: x = 2 * 2 + 2);
Using the algorithm above, you can find out that a mistake was made in the bracket sequence. But there are three places where you can insert an opening parenthesis to make the string syntactically valid. If it's a C-like language, then four. But even if we consider more or less reasonableplaces to insert, then there are two of them, and it is still not clear what exactly will be the error correction.
PS I give you a bonus example of a line for meditation:
/* [(]) */ y = (a[i] + 7); // }])

Answer 2

If this is such a task, then I assume that there it is necessary to remove the minimum number of brackets so that the sequence becomes correct. You can only remove parentheses, because instead of adding a parenthesis in any way, you can simply remove the second pair. The number of actions will not change. True, in your examples it will remove all parentheses.
Here you can solve dynamic programming. Let F(l,r) be the minimum number of deletion operations to make a correct bracket sequence from the string l through r.
Base - if l..r is an empty string - the answer is 0.
Otherwise, you need to consider options for what will happen to the last character. If there is an opening bracket at the end, then it must be removed - there are no other options: F(l,r) = 1+F(l,r-1).
If there is a closing bracket, then there are 2 options: either delete this character, or take it in response. In the first option, the answer is the same as above. In the second - it is necessary to sort out, and what character in the string will be the opening bracket for this one. Let it be the character i (there must be an opening bracket of the same type). Then the answer is F(l,i-1)+F(i+1,r-1) - after all, the parts before and inside the pair of brackets must also be regular sequences.
Of all the options, you must choose the minimum - this will be the answer for the current state.
If you want to restore the sequence itself, then, while maintaining the minimum, you also need to save in a separate two-dimensional array - which of the options was chosen (drop the last character, or which character to pair it with).
The answer to the problem is F(1,n) - for the entire line.
This solution consumes O(n^2) memory and takes O(n^3) time.