проверьте, сбалансирована ли строка скобок, выполнив определенную операцию над строкой

Учитывая строку скобок, мы должны выполнить 2 вида операций:

  1. flip- меняет i-ю скобку на противоположную (left->right , right->left)
  2. check- если строка является сбалансированным выражением в скобках

длина строки не более 30000.

Количество выполняемых операций не превышает 100 000.

какую структуру данных следует использовать для решения такой задачи?

Является ли дерево сегментов подходящей структурой данных?

Если да, то как его использовать?

Пример

строка = ()((

количество операций=4

  1. перевернуть 4 {новая строка ()()}
  2. проверить {строка сбалансирована}
  3. flip 2{новая строка становится ((()}
  4. проверить {строка не сбалансирована}

string algorithm data-structures segment-tree range-query
person Prashant Bhanarkar    schedule 07.08.2016    source источник
comment
Возможно, вы неверно истолковали вопрос, но вы ищете алгоритм, который с учетом несбалансированной строки превращает ее в сбалансированную с наименьшим возможным количеством переворотов? Или вы только ищете способ проверить, сбалансирована ли строка?   -  person user2464424    schedule 08.08.2016
comment
@user2464424 user2464424 заданная строка может быть сбалансированной/несбалансированной. Алгоритм, который я ожидал, дает две операции переворота и проверку, может быть любое количество переворотов или проверок (максимум 100000) для каждой проверки, я должен определить, сбалансирована ли вся строка и для каждого флипа я должен перевернуть i-й символ   -  person Prashant Bhanarkar    schedule 08.08.2016
comment
Почему вы начинаете с флипа, даже не проверив строку? И почему вы продолжаете после того, как проверка проходит? И как узнать, какой символ перевернуть? Проверка возвращает true/false или позицию первой проблемы?   -  person tobias_k    schedule 08.08.2016
comment
Все еще не ясно, вы (1) ищете реализацию для функций flip и check, или (2) алгоритмы, которые с учетом этих двух функций могут исправить несбалансированную строку скобок, или (3) и то, и другое?   -  person tobias_k    schedule 08.08.2016

Ответы (2)


arrow_upward
1
arrow_downward

Пусть каждый ( будет +1, а каждый ) будет -1. Тогда строка скобок сбалансирована, если и только если сумма для всей строки равна нулю, а сумма для каждого диапазона [0, k] неотрицательна.

Определим две функции для подстроки [i,j], sum и min. sum очевидно, а min(i,j) определяется как минимум из всех sum(i,k), где k <= j.

So

sum(i,k) = sum(i,j) + sum(j+1, k)

А также

min(i,k) = MIN( min(i,j), sum(i,j) + min(j + 1, k) )

Теперь мы можем построить бинарное дерево, где листьями являются +1 и -1, а корнем является весь диапазон [0, N-1]. Для каждого узла мы сохраняем min и sum.

Запрос баланса очевиден: мы проверяем root.min >= 0 и root.sum == 0, поэтому O(1).

Переворот выполняется путем обновления конечного узла и распространения изменений на корень. Обновляется не более log(N)+1 узлов, и каждое обновление O(1), поэтому O(logN).

person Community    schedule 08.08.2016

arrow_upward
0
arrow_downward

Легко сделать функцию, проверяющую, сбалансирована ли строка. Шагая по строке, увеличивайте значение, инициализированное нулем, если встречается символ "(", и уменьшайте его, если встречается ")". Если результат равен 0 и он никогда не опускался ниже 0 во время выполнения, строка сбалансирована. Перевернуть скобку в n-й позиции строки тривиально.

Вот простая реализация в javascript, которая переворачивает случайный символ строки в цикле и проверяет правильность полученной строки после каждого переворота.

http://jsbin.com/vagalijoca/edit?html,console

function checkbalanceness(str){
  var res = 0;
  for(i=0;i<str.length;i++) {
    str[i]=="(" ? res++ : res--;
    if (res < 0) break;
  }
  return res == 0;
}

function flipp(str, i){
  if (i >= str.length) return str;
  return str[i]=="(" ?
    str.substr(0,i) + ")" + str.substr(i+1) :
    str.substr(0,i) + "(" + str.substr(i+1) ;
}

//initial string
var curr = "()(())";
//operations to be executed
var ops = 40;

console.log('initial string: ' + curr + ' ' + checkbalanceness(curr));
console.log('operations: ' + ops);
console.log('start');
var ii;
var chartoflip;
for(ii=0;ii<ops;ii+=2){
  chartoflip = (ii/2)%(curr.length);
  curr = flipp(curr, chartoflip);
  console.log((ii) + ' - flip char ' + chartoflip + ': ' + curr);
  console.log((ii+1) + ' - checking ' + curr + ' ' + checkbalanceness(curr));
}
console.log('end');
person user2464424    schedule 08.08.2016