ביטוי regular expression למציאת סוגריים מרובעות הכי פנימיות בג'אווה

[oOtalOo]

אנא עזרו לי פה

אני צריך ביטוי regular expression למציאת סוגריים מרובעות הכי פנימיות באמצעות pattern ו - matcher בג'אווה

לדוגמא, [1 + [ 1 + [[1 + 2]+1]]] יצא 1 + 2

תודה

[Zelig]

באופן תאורטי, לא ניתן לעשות זאת עם regular expression טהור בשל למת הניפוח.

http://stackoverflow.com/questions/133601/can-regular-expressions-be-used-to-match-nested-patterns/133684#133684

אבל בהרבה שפות יש הרחבות של regex שמאפשרות מחסנית או רקורסיה. עדיין הרושם שאני מקבל זה שזו לא הדרך הנכונה.

חפש ברשת.

[שניצל]

במקרה כזה דווקא כנראה יותר פשוט ומהיר לספור את הסוגריים. תגדיר לך מונה ותעבור על המחרוזת - כל פעם שיש פתיחת סוגריים תגדיל אותו ב-1, כל סגירת סוגריים תקטין ב-1, ופשוט תזכור מתי המונה הגיע לערך הכי גדול.

[captaincaveman]

במקרה כזה, כשיודעים מה התווים החוקיים, נראה לי שאפשר לעשות את זה בביטוי רגולרי אם מניחים שכל הסוגריים הם או:

א. בתוך סוגריים אחרים.

ב. לא בתוך סוגריים אחרים משמע הם החיצוניים ביותר.

אני ממש ממש ממש לא חזק בתחביר של ביטויים רגולריים, (נניח שמותר ספרות, רווחים רגילים וארבע פעולות חשבון בסיסיות):

[[ 0123456789-/*+]n times]]

כמו שאמרתי, אני רע בתחביר שלהם, ואין לי כוח לחפש באמצע הלילה ברשת.

אבל הרעיון: חפש סוגריים מרובעים שבתוכם רק ספרות או פעולות חשבון ורווח. האם זה יעבוד?

[Zelig]

בשיטה זו (בהנחה שהיא בכלל נכונה) עדיין מוגבלים למספר מוגדר מראש של ] ו-[.

בשלב זה הייתי הולך על קוד ספירה פשוט, בהנחה שאין סיבוכים כמו מחרוזות, escape characters, או מעברי שורה בתוך השורה.

[Lee Jun Fan]

במקרה כזה, כשיודעים מה התווים החוקיים, נראה לי שאפשר לעשות את זה בביטוי רגולרי אם מניחים שכל הסוגריים הם או:

א. בתוך סוגריים אחרים.

ב. לא בתוך סוגריים אחרים משמע הם החיצוניים ביותר.

אני ממש ממש ממש לא חזק בתחביר של ביטויים רגולריים, (נניח שמותר ספרות, רווחים רגילים וארבע פעולות חשבון בסיסיות):

[[ 0123456789-/*+]n times]]

כמו שאמרתי, אני רע בתחביר שלהם, ואין לי כוח לחפש באמצע הלילה ברשת.

אבל הרעיון: חפש סוגריים מרובעים שבתוכם רק ספרות או פעולות חשבון ורווח. האם זה יעבוד?

גם אם מה שאתה אומר אפשרי בתחביר של ביטויים רגולריים, זה עדיין לא בהכרח יעבוד...

דוגמה:

[1*[2+5*[7+2]+[18-[14*9/[48+14]]]]]

מה שאמור לחזור זה 48+14, אבל במה שאתה מציע, יכול לחזור גם 7+2.

[Zelig]

חשוב להכיר בעובדות: יש בעיות ש-regex לא פותר.

[captaincaveman]

@Lee Jun Fan:

בדוגמא שלו אין סוגריים ברמה מקבילה:

[ [ ] [ ] ]

רק סוגריים מוכלים.

הפתרון שהצעתי יעבוד במקרה שמובא בדוגמא שלו, ואכן לא יעבוד בדוגמא שלך.

@Zelig:

למה מוגבלים למספר סוגריים ידוע מראש? ההגבלה היחידה שיש (למיטב ידיעתי) היא גודל הזכרון העומד לרשות התוכנית. הביטוי הרגולרי יודע להתמודד עם גדלים משתנים של קלט, שאם לא כן, מה הטעם בו?

[Zelig]

כי אתה צריך להכניס סוגריים לתוך הביטוי. "סוגריים מאוזנות" זה לא שפה רגולרית. לפי הבנתי גם עם התוספות שלהם, regex-ים עדיין לא יכולים לבטא סוגריים מאוזנות בכל עומק אפשרי.

[Gil28]

בבקשה:

"\\[[^\\[|\\]]*\\]"

[Zelig]

אין בדיקת חוקיות.

דוגמאות בעיתיות:

[[[[[a]]][[[[[b]]]]][c]]]      // only b should be found

aaaaaaa[[[[[[[[[[[[[[[[[[[[[[[]sss      // unbalanced

[[[[x][x]][[[x]][[[[[[[[[[[[[[[[[[x]]]]]]]]]]]][x]]]]]]]]]]]]]]]]]]][x]   // all x's are found despite unbalance

[captaincaveman]

כי אתה צריך להכניס סוגריים לתוך הביטוי. "סוגריים מאוזנות" זה לא שפה רגולרית. לפי הבנתי גם עם התוספות שלהם, regex-ים עדיין לא יכולים לבטא סוגריים מאוזנות בכל עומק אפשרי.

מסכים.

מצד שני, זה לא צויין כאחת הדרישות

[Zelig]

אני חושב שזה נדרש implicitly, שכן כאשר הסוגריים לא מאוזנות ניתן לפרש את הקלט במספר דרכים.

אבל גם אם כל הקלט תקין, עדיין יש בעיה גם כאשר הסוגריים מאוזנות (לפחות בתבנית המוצעת):

[[[[[X]]][[[[[Y]]]]][Z]]] 

ממש לא צריך לדון בזה - נראה לי שאנחנו מסכימים ש-REGEX זה הפטיש הלא נכון במקרה זה. אולי נצליח בכח לפתור את הבעיה עם REGEX, אבל עדיין זו לא הדרך הנכונה.