Удалить несоответствующие скобки из строки

Question

Я хочу удалить «непаренные» скобки из строки.

Т.е. все ( должны быть удалены, если за ними не стоит ) где-то в строке. Аналогично, все ), которым не предшествует ( где-то в строке, должны быть удалены.

В идеале алгоритм должен учитывать и вложенность.

например:.

"(a)".remove_unmatched_parents # => "(a)"
"a(".remove_unmatched_parents # => "a"
")a(".remove_unmatched_parents # => "a"

Answer 1

Вместо регулярного выражения, возможно, рассмотрим автомат с нажатием. (Я не уверен, что регулярные выражения Ruby могут справиться с этим, я верю, что Perl может).

(очень упрощенный) процесс может быть:

Для каждого символа во входной строке:

1. Если это не '(' или ')', просто добавьте его к выводу
2. Если это '(', увеличьте счетчик seen_parens и добавьте его
3. Если это ')' и seen_parens равно> 0, добавьте его и уменьшите seen_parens. В противном случае пропустите это.

В конце процесса, если seen_parens равен> 0, удалите столько паренов, начиная с конца. (Этот шаг можно объединить с описанным выше процессом с использованием стека или рекурсии.)

Весь процесс O(n), даже если относительно высокие издержки

Удачного кодирования.

Answer 2

Следующее использует онигурума. Oniguruma - это встроенный движок регулярных выражений, если вы используете ruby1.9. Если вы используете ruby1.8, посмотрите это: oniguruma .

Обновление

Мне было так лениво просто скопировать и вставить чужое регулярное выражение. Казалось, есть проблема.

Итак, теперь я написал свой собственный. Я считаю, что это должно сработать сейчас.

class String
    NonParenChar = /[^\(\)]/
    def remove_unmatched_parens
        self[/
            (?:
                (?<balanced>
                    \(
                        (?:\g<balanced>|#{NonParenChar})*
                    \)
                )
                |#{NonParenChar}
            )+
        /x]
    end
end

• (?<name>regex1) называет (под) регулярное выражение regex1 как name и делает возможным его вызов.
• ?g<name> будет подстрокой, которая представляет regex1. Обратите внимание, что ?g<name> не представляет конкретную строку, которая соответствует regex1, но представляет собой regex1. Фактически, возможно встраивать ?g<name> в (?<name>...).

Обновление 2

Это проще.

class String
    def remove_unmatched_parens
        self[/
            (?<valid>
                \(\g<valid>*\)
                |[^()]
            )+
        /x]
    end
end

Answer 3

Создание простого парсера LR:

tokenize, token, stack = false, "", []

")(a))(()(asdf)(".each_char do |c|
  case c
  when '('
    tokenize = true
    token = c
  when ')'
    if tokenize
      token << c 
      stack << token
    end
    tokenize = false
  when /\w/
    token << c if tokenize
  end
end

result = stack.join

puts result

текущие урожаи:

wesbailey@feynman:~/code_katas> ruby test.rb
(a)()(asdf)

Я не согласен с теми, кто изменяет класс String, потому что вы никогда не должны открывать стандартный класс. Регулярные выражения довольно хрупки для парсера и их трудно поддерживать. Я не мог представить, что вернусь к предыдущим решениям через 6 месяцев и попытаюсь вспомнить, что они делали!

Answer 4

Вот мое решение, основанное на алгоритме @ pst:

class String
  def remove_unmatched_parens
    scanner = StringScanner.new(dup)
    output = ''
    paren_depth = 0

    while char = scanner.get_byte
      if char == "("
        paren_depth += 1
        output << char
      elsif char == ")"
        output << char and paren_depth -= 1 if paren_depth > 0
      else
        output << char
      end
    end

    paren_depth.times{ output.reverse!.sub!('(', '').reverse! }
    output
  end
end

Answer 5

Алгоритм:

1. Пройдите через данную строку.
2. При этом следите за позициями "(" в стеке.
3. Если ")" найдено, удалите верхний элемент из стека.
   • Если стек пуст, удалите ")" из строки.
4. В конце концов, у нас могут быть позиции непревзойденных фигурных скобок, если они есть.

Java-код: Подарок @ http://a2ajp.blogspot.in/2014/10/remove-unmatched-parenthesis-from-given.html