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

Question

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

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

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

Не выполняется ни одна операция с максимальным значением 100000.

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

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

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

пример

строка = ()((

нет операции = 4

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

Answer 1

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

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

Так

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и root - это целый диапазон [0, N-1], Для каждого узла мы сохраняем min а также sum,

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

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

Answer 2

Функция, которая проверяет, сбалансирована ли строка, легко создается. Шагая по строке, увеличьте инициализированное нулями значение, если встречается символ "(", и уменьшите его, если ")". Если результат равен 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');