# How to balance parentheses/brackets in a string with minimum cost?

Given a word composed of opening and closing parentheses and brackets, we can do two operations:

• Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, [ for ] and ] for [. This operation has cost 1

• Replace a parentheses for a bracked and viceversa without changing its orientation. That is, change ( for [, ) for ], [ for ( and ] for ). This operation has cost 2.

Which is the minimum cost to balance the given word properly? For example, given ]( we can achieve [] by rotating twice and replacing once, with a total cost of 4

• Have you tried using stacks? Can you elaborate on what you did? – Sagnik Dec 2 '15 at 13:21
• What did you try? Where did you get stuck? For questions that look like homework exercises (which this does, even if it's not actually homework), we're happy to help but just giving you the answer usually doesn't help in any true sense. – David Richerby Dec 2 '15 at 13:33
• I don't even know where to begin to be honest. I already have a function that checks if a string is properly balanced in linear time using stacks. I also know that this is a dynamic programming problem, and it kind of reminds me to the Levenhstein distance algorithm, in the sense that it deals with strings and changes within it, but I just cant get the recursion that I need – Ivan Dec 2 '15 at 14:24
• Read the advice in cs.stackexchange.com/q/645/755 and cs.stackexchange.com/q/47216/755, and start by trying to find a recursive algorithm without regard to its running time (even exponential time is OK). Then I encourage you to edit the question to show what approaches you've tried and see if you can articulate any question that is more narrowly focused than "please do my exercise for me". – D.W. Dec 2 '15 at 17:07
• This is a problem statement, not a question. If you have a specific question regarding the wording of the problem or about specific steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jan 1 '16 at 17:57

## 1 Answer

Two possible recursive approaches.

• The string $(w$ is balanced iff $w$ is of the form $u)v$ where each of $u$ and $v$ are balanced (but either of them may be empty).

• The (nonempty) string $w$ is balanced iff it is of the form $(u)$ where $u$ is balanced, or it is of the form $uv$ where each of $u$ and $v$ are balanced (and nonempty).

• The question is about the minimal cost of balancing a word. How do you guarantee that your approaches are optimal? And which cost do they have? – Danny Dec 3 '15 at 8:17
• @Danny That is the dynamic programming part. Which follows the recursion. – Hendrik Jan Dec 3 '15 at 10:03
• Of course, but this part should be a part of the answer, or? Because the question is about optimality, not about the algorithm. – Danny Dec 3 '15 at 11:02
• @Danny I actually think the question is about an algorithm for optimality, but I simply start by answering the comment "I just cant get the recursion that I need". Once the question gets more specific, I can offer more help. See also the comments above by David and D.W. for background to this. – Hendrik Jan Dec 3 '15 at 13:32