문자열의 불균형 괄호를 찾는 알고리즘

Question

포스트 스크립트/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