查找字符串中不平衡括号的算法

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