убрать лишние скобки
Вопрос:
Удалите лишние скобки из строки.
например
((a+b))*c => (a+b)*c
(a+b)+c => (a+b)+c
((a+b)/(c+d)) => ((a+b)/(c+d))
(a+(((b-c)))*d) => (a+(b-c)*d) and so on.
Я придумал следующее решение:
Подход: я сканирую строку и запоминаю (используя карту) индекс открывающей скобки, а также, является ли она дополнительной или нет (по умолчанию это дополнительная). Если я нахожу закрывающую скобку, я проверяю соответствующую открывающую скобку на карте и, если она есть, удаляет обе.
void removeExtraParentheses(string& S){
map<int, bool> pmap;
for(int i = 0; i < S.size(); i++){
map<int, bool>::iterator it;
if(S.at(i) == '('){
pmap[i] = true;
}
else if(S.at(i) == ')'){
it = pmap.end();
it--;
if(!(*it).second){
pmap.erase(it);
}
else{
S.erase(S.begin() + i);
S.erase(S.begin() + (*it).first);
pmap.erase(it);
i = i - 2;
}
}
else{
if(!pmap.empty()){
it = pmap.end();
it--;
(*it).second= false;
}
}
}
}
Временная сложность: O (n2)
Пробел: O (n)
Я не слишком доволен своим решением, потому что я использую дополнительное хранилище и делаю это в квадратичное время.
Можем ли мы сделать это в O (n) времени и O (1) пространстве? Если нет, что лучше всего сделать?
Решение
Создайте дерево выражений, затем регенерируйте выражение с минимальным
скобки. Любые скобки в оригинале, которых нет в
генерировать не нужно.
Простым, почти правильным решением было бы назначить приоритет
каждый оператор. Затем вам нужно круглые скобки в любое время напрямую
под узлом, над которым вы работаете, это оператор, который имеет более низкий
приоритет, чем у узла; например, если вы находитесь на *
(умножение), и один из двух дочерних узлов имеет +
(дополнение) узел. Плюс некоторая логика для обработки левой или правой привязки: если
ты в + узел, а правый узел также является + узел, ты
нужны скобки.
Это только частично правильно, потому что есть несколько конструкций в
C ++, который не может быть сопоставлен с грамматикой предшествования: некоторые из
на ум приходят типы литейных конструкций или троичный оператор. В
по крайней мере, в случае троичного оператора, однако, особая обработка
не так сложно
РЕДАКТИРОВАТЬ:
Что касается ваших больших вопросов: очевидно, это не O (1) в
пространство, так как вам нужно построить все выражение в памяти. я
не думайте, что O (1) для памяти возможна, так как потенциально вы можете
иметь неограниченное вложение, и вы не можете сказать, являются ли круглые скобки
необходимо или нет до неопределенного времени спустя. Я на самом деле не
проанализировал это, но я думаю, что это O (n) во времени. Верхняя граница на
количество узлов n (длина строки), и вам нужно посетить
каждый узел ровно один раз.
Другие решения
Более или менее найден в Интернете …
Учитывая вход: ((A + B) * C)
Ожидаемый результат: (A + B) * C
Предположения:
- Peek (очередь) просто сообщает элементу переднего конца очереди, не удаляя его.
- priordence () — это функция, которая просматривает таблицу приоритетов операторов
Псевдокод ниже:
-
Преобразовать инфиксное выражение в RPN (например, алгоритм Shunting-yard O (n))
AB+C* -
Вставлять только операторов в очередь
Q(спереди) + ——— * (сзади)
- Разбор постфиксного выражения
- Если операнд, нажмите на стек ‘S’
- Если оператор
- у = Удалить (Q)
- Если приоритет (y)> приоритет (peek (Q)), то нажмите (S, «Pop (S) y Pop (S)»)
- Если приоритет (у) < приоритет (заглянуть (Q)), затем нажать (S, «(Pop (S) y Pop (S))»)
- Окончательный результат на вершине
S
Все должно быть O (n).
Я думал, что сделаю это. Это решение проблемы, которая пришла мне в голову. Обратите внимание, что это псевдокод и не предназначен для непосредственного запуска.
(На самом деле, это скорее C ++, но с тех пор, как я в последний раз писал настоящий C ++, я давно не чувствовал, что прилагаю усилия к тому, чтобы все было правильно, когда я собирался найти алгоритм.)
queue<tuple<int, bool> > q = new queue<tuple<int, bool> >();
for (int i = 0; i < str.length; i++)
{
char a = str.charAt(i);
if (a == '(')
{
q.push(new tuple<int, bool>(i, false));
}
else if (a == ')')
{
if (q.top().bool)
{
// remove top.int and i from string
}
q.pop();
q.top().bool = true;
}
else
{
q.top().bool = false;
}
}
Это делает работу в O(n) и использует O(n) пробел (или фактически, объем используемого пространства фактически основан на самом глубоком уровне вложенности, присутствующем в строке, но он гарантированно будет ниже, чем n)
(Обратите внимание, что // remove top.int and i from string на самом деле не может быть сделано в O(1), Однако, если вы немного креативны, вы можете сделать что-то подобное в O(1),
Например, вы можете создать список символов для вывода и сохранить итератор вместо int, тогда вы можете удалить два символа в O (1). В конце вы можете построить свою последнюю строку, перебирая список в O (n). Альтернативным решением будет фактически работать с массивом (или вектором) DummyOrCharacters, которые являются либо фиктивными, но ничего не содержат или содержат символ. Еще раз, вы можете заменить персонажа на пустышку в O(1), Еще раз, вы будете перебирать структуру и строить свою выходную строку в O(n))