BaOH2's blog

A question about bracket strings
By BaOH2, history, 4 years ago, In English

Could you please answer my question, thank you very much!

here are some laws about legal bracket strings:

  • an empty string is a legal bracket string
  • if A is a legal bracket string, so (A) is a legal bracket string
  • if A is a legal bracket string and B is a legal bracket string, so AB is a legal bracket string

And I want to know that what is the minimum edits that letting a bracket string to be legal?

Thank you so much!

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

Is there a place to submit, I have this greedy idea

cnt = 0

diff = 0 /// count('(') - count(')')
For each char &c in string in normal order
-- if (c = '(') ++diff else --diff
-- if (diff < 0)
---- c = '('
---- diff += 2
---- cnt += 1

diff = 0 /// count(')') - count('(')
For each char &c in string in reverse order
-- if (c = ')') ++diff else --diff
-- if (diff < 0)
---- c = ')'
---- diff += 2
---- cnt += 1

out << cnt
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you for helping me and i am soooooooo sorry that i didn't log into this account yesterday and i did not see this answer

    and i really want to say thank you for solving a kind of strange question :)

    i will study hard tomorrow :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sometimes ad-hoc/implementation problems takes time to solve whatever your level is. It is ok bro

      → Reply