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

Question

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

1. flip- изменяет I-й скобки в противоположном (лево- > правые, право-> слева)
2. регистрации по прибытию, если строка является сбалансированным выражением скобки

длиной струны при макс 30000.

Нет операцию должны быть проведено I с при макс. 100000.

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

Факс:

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

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

Пример

строка =() ((

нет работы = 4

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

Answer 1

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

Answer 2

Пусть каждый (+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 's и -1' ы, и корень весь диапазон [0, N-1]. Для каждого узла мы сохраняем min и sum.

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

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