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

问题描述

的PostScript / PDF字符串被括号括起来，并允许包含转义括号的只要括号是完全平衡的。因此，例如

 （（））％有效的字​​符串常量
（（）％无效的字符串常量，内（应逃脱
 

我知道一个算法来告诉我，如果有的是的字符串中的任何不平衡的括号;我所寻找的是一种算法，将查找的一对括号是不平衡的，这样我就可以坚持反斜杠在他们面前，使整个一个有效的字符串字面量最小。更多的例子：

 （⟶\（
（）⟶（）
（（）⟶\（（）或（\（）
（））⟶（）\）或（\））
（）（⟶（）\（
 

解决方案

标准基于堆栈的算法的修改，以检测不平衡括号应该为你工作。下面是一些伪code：

 无效find_unbalaned_indices（字符串输入）
{
    //初始化含有整数重新presenting指数的堆栈
    //其中lparen（被视为

    堆叠＆LT; INT索引＆gt; = NIL

    对于（i = 0到input.size（））
    {
        // Lparen。推入堆栈
        如果（输入[I] =='（'）
        {
            //锯（索引= I
            stack.push（ⅰ）;
        }
        否则如果（输入[I] =='）'）
        {
           OUT = stack.pop（）;
           如果（出== NIL）
           {
               //堆栈是空的。不平衡RParen。
               //指数=我需要转义
               ...
           }
           //否则，本rparen具有平衡lparen。
           // 没事做。
        }
    }

    //检查，如果我们有任何不平衡lparens
    而（stack.size（）！= 0）
    {
        OUT = stack.pop（）;
        //出不均衡
        //指数= out.index需要转义。
    }
}
 

希望这有助于。

PostScript/PDF string literals are surrounded by parentheses, and are allowed to contain unescaped parentheses as long as the parentheses are fully balanced. So for instance

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

I know an algorithm to tell me if there are any unbalanced parentheses in a string; what I'm looking for is an algorithm that will locate a minimal set of parentheses that are unbalanced, so that I can then stick backslashes in front of them to make the whole a valid string literal. More examples:

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

解决方案

A modification of the standard stack based algorithm to detect imbalanced parenthesis should work for you. Here's some pseudo code:

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.
    }
}

Hope this helps.

这篇关于算法查找不平衡的括号中的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！