(*)))
0
1
2
1
0
-1 -> return false

То есть если мы в процессе обхода строки слева направо будем рассматривать все звёздочки как левые скобки, и нам этого не хватит на каком-то шаге, то перестановка не валидная.
Если мы в процессе обхода строки справа налево будем рассматривать все звёздочки как правые скобки, и нам этого не хватит на каком-то шаге, то перестановка не валидная.

Иначе перестановка валидная. Вот здесь я не понимаю, почему...

(***
1. c = 0 (From left to right)
Treat '(' or '*' as +1, ')' as -1. If c<0 return false.
c = 1, c < 0? -
c = 2, c < 0? -
c = 3, c < 0? -
c = 4, c < 0? -

2. c = 0 (From right to left)
Treat ')' or '*' as +1, '(' as -1. If c<0 return false.
c = 1, c < 0?-
c = 2, c < 0?-
c = 3, c < 0?-
c = 2, c < 0?-

3. return true

Тогда одиночная звёздочка будет валидной. Или я неправильно понял?

Да, валидной

Пустая строка валидная. Мы можем рассматривать звёздочку как пустое место

А, всё. Я невнимательно прочитал.

https://fardolieri.github.io/Valid-Parenthesis-String/
Кек

А есть РВ грамматика правильных скобочных выражений? Я не могу построить ее из грамматики калькулятора с скобками.

Не знаю, что это значит.🤷‍♂

тут же надо на планарность граф проверять? или чем-то другим можно обойтись?

Беатрикс Киддо в молодости была наемницей и любила составлять графы связей между её целями. Она цепляла на стену иголки и связывала их нитками. Но так как она наполовину японка, ей особенно нравилось, когда цели можно было расположить так, чтобы нитки не пересекались. Вам известна схема, которую хочет начертить Беатрикс. Выясните, может ли в этот раз схема ей понравиться?

Формат ввода
v:количество целей Беатрикс(макс. 1000), n:количество связей между целями(макс. 3000), n пар связей.

Формат вывода
YES, если Киддо может изобразить схему, которая ей понравится, NO - если не сможет.

по-моему тут более строгое условие - граф должен быть планарным, при этом ребра должны быть отрезками прямых

любой планарный граф так можно наприсовать

(чтобы ребра отрезками были)

Не, это равносильно планарности

ок

а можно как-то не через планарность решить?

Регулярной грамматикой (если речь о ней) скобочное выражение не распарсить.

В условии же написано: проверьте граф на планарность.
Тут не отвертеться.

Я про PEG  грамматику (разбирающую выражения).