streamalism.org

1. סקירה כללית

סוגריים מאוזנים, הידועים גם בשם סוגרים מאוזנים, הם בעיית תכנות נפוצה.

במדריך זה נבדוק האם הסוגריים במחרוזת נתונה מאוזנים או לא.

סוג מחרוזות זה הוא חלק ממה שמכונה שפת דייק.

2. הצהרת בעיות

סוגר נחשב לאחת מהתווים הבאים - "(", ")", "[", "]", "{", "}".

סט סוגריים הוא נחשב לזוג תואם אם סוגר פתיחה, “(“, “[“ ו- “{“, מתרחשת משמאל לסוגר הסגירה המתאים, ")", "]" ו- "}" בהתאמה.

עם זאת, מחרוזת המכילה זוגות סוגריים היא לא מאוזן אם סט הסוגריים שהוא סוגר אינו תואם.

בדומה לכך, מחרוזת המכילה תווים שאינם סוגריים כמו a-z, A-Z, 0-9 או תווים מיוחדים אחרים כמו #, $, @ נחשב גם לא מאוזן.

לדוגמא, אם הקלט הוא "{[(])}", צמד הסוגריים המרובעים, "[]", סוגר סוגר עגול פתיחה לא מאוזן יחיד, "(". באופן דומה צמד הסוגריים העגולים, "() ", סוגר סוגר מרובע יחיד ולא מאוזן,"] ". לפיכך, מחרוזת הקלט" {[(])} "אינה מאוזנת.

לכן, מחרוזת המכילה תווי סוגריים נאמרת מאוזנת אם:

1. סוגר פתיחה תואם מופיע משמאל לכל סוגר סגירה מתאים
2. סוגריים סגורים בסוגריים מאוזנים גם הם מאוזנים
3. הוא אינו מכיל תווים שאינם סוגריים

יש לזכור כמה מקרים מיוחדים: ריק נחשב כלא מאוזן, ואילו המחרוזת הריקה נחשבת למאוזנת.

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

() [()] {[()]} ([{{[(())]}}])

וכמה שאינם מאוזנים:

א ב ג[](){} {{[]()}}}} {[(])}

עכשיו שיש לנו הבנה טובה יותר של הבעיה שלנו, בואו נראה איך לפתור אותה!

3. גישות פיתרון

ישנן דרכים שונות לפתור בעיה זו. במדריך זה נבחן שתי גישות:

1. באמצעות שיטות של חוּט מעמד
2. באמצעות דק יישום

4. הגדרה בסיסית ואימותים

בואו ניצור תחילה שיטה שתחזור נָכוֹן אם הקלט מאוזן ו שֶׁקֶר אם הקלט אינו מאוזן:

ציבורי בוליאני isBalanced (String str)

בואו ניקח בחשבון את האימותים הבסיסיים של מחרוזת הקלט:

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

בהתחשב בכללים אלה, אנו יכולים ליישם את האימותים:

אם (null == str || ((str.length ()% 2)! = 0)) {return false; } אחר {char [] ch = str.toCharArray (); עבור (char c: ch) {if (! (c == '' || c == ']' || c == ')')) {return false; }}}

כעת, לאחר שתוקף מחרוזת הקלט, נוכל לעבור לפתרון בעיה זו.

5. שימוש String.replaceAll שיטה

בגישה זו נעבור במחרוזת הקלט ונסיר את המופעים של "()", "[]" ו- "{}" מהמחרוזת באמצעות String.replaceAll. אנו ממשיכים בתהליך זה עד שלא ימצאו התרחשויות נוספות במחרוזת הקלט.

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

בואו נראה את היישום המלא:

בעוד (str.contains ("()") || str.contains ("[]") || str.contains ("{}")) {str = str.replaceAll ("\ (\)", "") .replaceAll ("\ [\]", "") .replaceAll ("\ {\}", ""); } להחזיר (strllength () == 0);

6. שימוש דק

דק היא צורה של תוֹר המספק פעולות הוספה, אחזור והצצה בשני קצוות התור. אנו ננצל את תכונת ההזמנות Last-in-First-Out (LIFO) של מבנה נתונים זה כדי לבדוק את האיזון במחרוזת הקלט.

ראשית, בואו נבנה את שלנו דק:

Deque deque = LinkedList חדש ();

שים לב שהשתמשנו ב- רשימה מקושרת כאן כי זה מספק יישום עבור דק מִמְשָׁק.

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

אם (ch == '{' || ch == '[' || ch == '(') {deque.addFirst (ch);}

אבל אם הדמות מהווה סוגר סוגר, נבצע כמה בדיקות על ה- רשימה מקושרת.

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

עם זאת, אם רשימה מקושרת אינו ריק ואז אנו מציצים על הדמות האחרונה שלו באמצעות ה- הצצה ראשונה שיטה. אם ניתן לזווג אותו עם סוגר הסגירה, אנו מסירים את הדמות העליונה ביותר מה- רשימה משתמש ב removeFirst שיטה ולעבור לאיטרציה הבאה של הלולאה:

אם (! deque.isEmpty () && ((deque.peekFirst () == '{' && ch == '}') || (deque.peekFirst () == '[' && ch == ']') || (deque.peekFirst () == '(' && ch == ')'))) {deque.removeFirst (); } אחר {להחזיר כוזב; }

בסוף הלולאה, כל התווים נבדקים באיזון, כך שנוכל לחזור נָכוֹן. להלן יישום מלא של ה- דק גישה מבוססת:

Deque deque = LinkedList חדש (); עבור (char ch: str.toCharArray ()) {if (ch == '{' || ch == '[' || ch == '(') {deque.addFirst (ch);} אחר {if ( ! deque.isEmpty () && ((deque.peekFirst () == '{' && ch == '}') || (deque.peekFirst () == '[' && ch == ']') || (deque.peekFirst () == '(' && ch == ')'))) {deque.removeFirst ();} אחר {return false;}}} return true;

7. מסקנה

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

כמו תמיד, הקוד זמין ב- Github.