убрать лишние скобки

Постройте дерево выражений, затем перегенерируйте выражение с минимальным количеством скобок. Любые круглые скобки в оригинале, которых нет в генераторах, не нужны.

Простым, почти правильным решением было бы назначить приоритет каждому оператору. Затем вам понадобятся круглые скобки каждый раз, когда узел непосредственно под узлом, над которым вы работаете, является оператором, который имеет более низкий приоритет, чем у узла; например, если вы находитесь на узле * (умножение), а один из двух дочерних узлов имеет узел + (сложение). Плюс немного логики для обработки левой или правой привязки: если вы находитесь на узле +, а правый узел также является узлом +, вам нужны круглые скобки.

Это правильно лишь отчасти, потому что в C++ есть несколько конструкций, которые на самом деле не могут быть сопоставлены с грамматикой приоритета: на ум приходят некоторые конструкции приведения типов или тернарные операторы. Однако, по крайней мере, в случае с тернарным оператором особая обработка не так уж сложна.

РЕДАКТИРОВАТЬ:

Что касается ваших больших вопросов: это, очевидно, не O (1) в пространстве, поскольку вам нужно построить все выражение в памяти. Я не думаю, что O (1) для памяти возможен, поскольку потенциально вы можете иметь неограниченное количество вложений, и вы не можете сказать, необходимы ли круглые скобки или нет, до неопределенного времени позже. Я на самом деле не анализировал это, но я думаю, что это O (n) по времени. Верхняя граница количества узлов равна n (длина строки), и вам нужно посетить каждый узел ровно один раз.

Более-менее нашел в сети...

Данные входные данные: ((A+B)*C) Ожидаемый результат: (A+B)*C

Предположения:

• Peek (очередь) просто указывает элемент в начале очереди, не удаляя его.
• priority() — это функция, которая просматривает таблицу приоритетов операторов.

Псевдокод ниже:

1. Преобразование инфиксного выражения в RPN (например, алгоритм маневровой станции O (n))

   AB+C*

2. Вставить только операторов в очередь Q

   (спереди)+ -------- *(сзади)

3. Разобрать постфиксное выражение
4. Если операнд, поместите в стек 'S'
5. If operator
   • y=Delete(Q)
   • Если приоритет (y) > приоритет (Peek (Q)), то нажмите (S, «Pop (S) y Pop (S)»)
   • Если приоритет(y) ‹ приоритет(Peek(Q)), то Push (S, "( Pop(S) y Pop(S) )")
6. Окончательный результат поверх 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))