Алгоритм нахождения несбалансированных скобок в строке

Question

Строковые литералы PostScript / PDF заключены в круглые скобки и могут содержать неэкранированные круглые скобки , если круглые скобки полностью сбалансированы . Так например

( () )  % valid string constant
( ( )   % invalid string constant, the inner ( should be escaped

Я знаю алгоритм, чтобы сообщить мне, если есть какие-нибудь несбалансированные скобки в строке; я ищу алгоритм, который находит минимальный набор несбалансированных скобок, чтобы я мог затем поставить обратную косую черту перед ними, чтобы сделать целую правильную строку буквальной. Больше примеров:

(     ⟶   \(
()    ⟶   ()
(()   ⟶   \(() or (\()
())   ⟶   ()\) or (\))
()(   ⟶   ()\(

Answer 1

Модификация стандартного стекового алгоритма для обнаружения несбалансированных скобок должна работать на вас.Вот некоторый псевдокод:

void find_unbalaned_indices(string input)
{
    // initialize 'stack' containing of ints representing index at
    // which a lparen ( was seen

    stack<int index> = NIL          

    for (i=0 to input.size())
    {
        // Lparen. push into the stack
        if (input[i] == '(')
        {
            // saw ( at index=i
            stack.push(i);
        }
        else if (input[i] == ')')
        {
           out = stack.pop();
           if (out == NIL)
           {
               // stack was empty. Imbalanced RParen.
               // index=i needs to be escaped
               ... 
           }  
           // otherwise, this rparen has a balanced lparen.
           // nothing to do.
        }
    }

    // check if we have any imbalanced lparens
    while (stack.size() != 0)
    {
        out = stack.pop();
        // out is imbalanced
        // index = out.index needs to be escaped.
    }
}

Надеюсь, это поможет.

Answer 2

def escape(s):
    return ''.join(r(')(', r('()', s)))

def r(parens, chars):
    return reversed(list(escape_oneway(parens, chars)))

def escape_oneway(parens, chars):
    """Given a sequence of characters (possibly already escaped),
    escape those close-parens without a matching open-paren."""
    depth = 0
    for x in chars:
        if x == parens[0]:
            depth += 1
        if x == parens[1]:
            if depth == 0:
                yield '\\' + x
                continue
            else:
                depth -= 1
        yield x