Regex để kiểm tra xem chuỗi có dấu ngoặc đơn không khớp không?

Question

Trong tập lệnh PHP, tôi nên sử dụng regex nào để kiểm tra các dấu ngoặc đơn không khớp trong một chuỗi? Những điều mà tôi muốn cho phép bao gồm:

• Đây là (ok)
• này (là) (ok)

điều tôi muốn ngăn chặn:

• Đây là) xấu (
• Đây cũng là (xấu
• Đây là (xấu) (quá)

Cảm ơn!

Cập nhật: Tất cả các bạn đều là rock. Làm điều này với một regex có vẻ phức tạp hơn nó cần phải có, và các loại câu trả lời cấp 2 là những gì làm cho stackoverflow đẹp. Cảm ơn các liên kết và mã giả. Tôi không chắc ai sẽ đưa ra câu trả lời, vì vậy tôi xin lỗi mọi người có câu trả lời tôi không thể chấp nhận.

Answer 1

Regex không phải là công cụ thích hợp cho công việc. Quét chuỗi theo cách thủ công.

Pseudo-code:

depth = 0 
for character in some_string: 
    depth += character == '(' 
    depth -= character == ')' 
    if depth < 0: 
     break 

if depth != 0: 
    print "unmatched parentheses" 

Answer 2

Không thể thực hiện điều này bằng regex. Kết hợp cú đúp yêu cầu tính năng đệ quy/đếm không có sẵn trong regex. Bạn sẽ cần một trình phân tích cú pháp cho việc này.

Thông tin chi tiết có sẵn ở đây: http://blogs.msdn.com/jaredpar/archive/2008/10/15/regular-expression-limitations.aspx

Answer 3

Để mở rộng câu trả lời JaredPar, nó không phải là rất khó khăn để giải quyết mà không cần sử dụng một regex, chỉ cần viết một hàm kiểm tra từng nhân vật trong chuỗi và gia/decrements một quầy. Nếu bạn tìm thấy một "(", tăng nó, và nếu bạn tìm thấy một ")", giảm nó. Nếu bộ đếm đi xuống dưới 0, bạn có thể ngắt, chuỗi không hợp lệ. Khi bạn đã xử lý toàn bộ chuỗi, nếu bộ đếm không phải là 0, có một dấu ngoặc đơn mở chưa từng có.

Answer 4

ví dụ bạn không bao gồm bất kỳ dấu ngoặc lồng nhau ... nếu bạn không quan tâm đến làm tổ, sau đó điều này có thể được thực hiện bằng cách sử dụng biểu thức sau đây:

^[^()]*(?:\([^()]*\)[^()]*)*$ 

Điều này sẽ khớp với tất cả các chuỗi trong danh sách "cho phép" của bạn và không chống lại các chuỗi trong danh sách "ngăn chặn" của bạn. Tuy nhiên, nó cũng sẽ không thành công với bất kỳ chuỗi nào có ngoặc đơn lồng nhau. ví dụ. "this (is (not) ok)"

Như những người khác đã chỉ ra, biểu thức chính quy không phải là công cụ chính xác nếu bạn cần xử lý lồng nhau.

Answer 5

Đồng ý với thực tế rằng điều này là không thể với REGEX. Bạn có thể làm những điều sau đây, mặc dù:

<?php 

$testStrings = array('This is (ok)', 'This (is) (ok)', 'This is)bad(', 'This is also (bad', 'This is (bad (too)'); 

foreach($testStrings as $string) { 
    $passed = hasMatchedParentheses($string) ? 'passed' : 'did not pass'; 
    echo "The string $string $passed the check for matching parenthesis.\n"; 
} 

function hasMatchedParentheses($string) { 
    $counter = 0; 
    $length = strlen($string); 
    for($i = 0; $i < $length; $i ++) { 
     $char = $string[ $i ]; 
     if($char == '(') { 
      $counter ++; 
     } elseif($char == ')') { 
      $counter --; 
     } 
     if($counter < 0) { 
      return false; 
     } 
    } 
    return $counter == 0; 
} 

?> 

Answer 6

Tại sao nó không thể xảy ra với một regex

Những câu trả lời khác đều đúng, nhưng tôi chỉ muốn đưa vào một plug cho khoa học máy tính lý thuyết .. .đây là một trường hợp khi biết lý thuyết đưa ra một lợi thế thực tế thực tế.

Một regex tương ứng với một automaton hữu hạn xác định (DFA), nhưng khớp paren yêu cầu ngữ cảnh không có ngữ cảnh, có thể được nhận ra như một automaton hữu hạn (PDA) nhưng không phải bởi DFA.

Bởi vì điều này, không có nhiều công việc não bộ, chúng tôi biết rằng câu trả lời là không, và chúng tôi không phải lo lắng rằng có điều gì đó chúng tôi chỉ xem xét. Vì vậy, bạn có thể tự tin trong các câu trả lời ở trên, và không lo lắng rằng các tác giả chỉ nhìn ra một cái gì đó khi họ đưa ra câu trả lời đó.

Hầu như tất cả các sách biên dịch sẽ nói về vấn đề này, đây là một cái nhìn tổng quát:

http://books.google.com/books?id=4LMtA2wOsPcC&pg=PA94&lpg=PA94&dq=push-down+finite+automata&source=bl&ots=NisYwNO1r0&sig=ajaSHFXwpPOWG8IfbcfKoqzS5Wk&hl=en&ei=m26cSdf6DZGYsAPB-6SsAg&sa=X&oi=book_result&resnum=6&ct=result

Answer 7

Bạn thể làm điều này với một biểu thức chính quy - PCRE, như được sử dụng bởi PHP, cho phép mẫu đệ quy. Cuốn cẩm nang PHP cung cấp cho một example đó là gần như chính xác những gì bạn muốn:

\(((?>[^()]+)|(?R))*\) 

này phù hợp với bất kỳ chuỗi mở ngoặc một cách chính xác miễn là nó bắt đầu và kết thúc với dấu ngoặc đơn. Nếu bạn muốn đảm bảo toàn bộ chuỗi được cân bằng, cho phép chuỗi như "wiggedy (wiggedy) (wiggedy (wack))", đây là những gì tôi đã đưa ra:

^((?:[^()]|\((?1)\))*+)$ 

Dưới đây là một lời giải thích của mô hình, trong đó có thể chiếu sáng nhiều hơn obfuscatory:

 
^    Beginning of the string 
(   Start the "balanced substring" group (to be called recursively) 
    (?:   Start the "minimal balanced substring" group 
    [^()]  Minimal balanced substring is either a non-paren character 
    |   or 
    \((?1)\) a set of parens containing a balanced substring 
)   Finish the "minimal balanced substring" group 
    *   Our balanced substring is a maximal sequence of minimal 
       balanced substrings 
    +   Don't backtrack once we've matched a maximal sequence 
)    Finish the "balanced substring" pattern 
$    End of the string 

Có rất nhiều cân nhắc về hiệu quả và tính đúng đắn của các loại regex này. Hãy cẩn thận.

Answer 8

php Làm việc mà không regex:

function analyse($input){ 
    $len = strlen($input); 
    $depth = 0; 
    for ($i = 0; $i < $len; $i++) { 
     $depth += $input[$i] == '('; 
     $depth -= $input[$i] == ')'; 
     if ($depth < 0) break; 
    } 
    if ($depth != 0) return false; 
     else return true; 
} 
$check_nestled = analyse('(5 * 2) + ((2 + 2) - 4)'); 
if($check_nestled){ 
    // do stuff, everything is ok 
}