שאלה ב- Java

[iem]

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

{ } [ ] ( ) 6 תווים סה"כ.

ומוגדר שבין כל 2 תווים מופיע לפחות רווח אחד.

כמו כן ביטוי תקין יהיה אם הוא אחד מהבאים:

1) מחרוזת ריקה או מחרוזת המכילה רווח בלבד.

2)

st1 + "" + st2

כאשר st1 ן- st2 הם ביטויי סוגריים תקינים לדוגמא ("() []").

"(" +st +")" או "[" +st +"]" או "{" +st +"}" כאשר st הוא ביטוי סוגריים תקין.

אני צריך לכתוב שיטה סטטית ובוליאנית (מן הסתם..) שמקבלת ביטוי סוגריים ומחזירה true אם הוא תקין ו false אחרת.

למשל.... דוגמאות ....

isValid("()") == true

isValid("((") == false

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

O(n)

בשאלה...

ממש ממש צריך עזרה כאן... תודה !

[ftom2]

אני מקווה שהבנתי אותך נכון:

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

[adamshar]

למה לא להכניס למחסנית כל סוגר פותח ולהוציא על כל סוגר סוגר.

כך למשל, אם הגיע } ומהמחסנית יצא { זה בסדר אבל אם יצא ( למשל תחזיר F.

[iem]

אני מקווה שהבנתי אותך נכון:

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

אני לא אמור לספור את הסוגריים לכן ה counter אין לו משמעות, אני אמור רק להציג true או false והסיבוכיות המעצבנת כמובן

שתהיה ליניארית, כלומר

O(n)

למה לא להכניס למחסנית כל סוגר פותח ולהוציא על כל סוגר סוגר.

כך למשל, אם הגיע } ומהמחסנית יצא { זה בסדר אבל אם יצא ( למשל תחזיר F.

נשמע פצצה אבל אני משתגע ולא מצליח לרשום את השיטה... :'(

[שניצל]

נסה לכתוב, ותעלה לכאן מה שכתבת. נעזור לך משם.

[iem]

נסה לכתוב, ותעלה לכאן מה שכתבת. נעזור לך משם.

if input is '(' or '{' or '[' or ')' or '}' or ']' 
     {
     if input is '(' or '{' or '['
       push it into the stack.
     else if input is ')' or '}' or ']' 
       {
       if stack is empty
            report error.
       pop cell from stack
       if cell "matches input" 
            we are ok.
       else if cell dont "matches input" or stack is empty 
            report error.
       }
     }
   }
  if the stack is not empty
    report error

.

אני יודע בגדול אבל שוב ... אני בבעיה במימוש....

[שניצל]

האלגוריתם שלך סבבה (לא ממש צריך את ה-if החיצוני, אבל זה לא משנה).

מה אתה מתקשה לממש?

נסה להעלות לכאן קוד אמיתי ונראה איך נוכל לעזור לך.

[iem]

האלגוריתם שלך סבבה (לא ממש צריך את ה-if החיצוני' date=' אבל זה לא משנה).

מה אתה מתקשה לממש?

נסה להעלות לכאן קוד אמיתי ונראה איך נוכל לעזור לך.

[/quote']

אתה אומר שבגדול הפסאודו קוד (ככה קוראים לתיאור הזה ?) שלי בסדר כך?:

if input is '(' or '{' or '['
       push it into the stack.
     else if input is ')' or '}' or ']' 
       {
       if stack is empty
            report error.
       pop cell from stack
       if cell "matches input" 
            we are ok.
       else if cell dont "matches input" or stack is empty 
            report error.
       }

  if the stack is not empty
    report error

[שניצל]

סבבה, אבל תנסה להעלות קוד אמיתי (java, לא פסאודו קוד) ונראה איפה יש לך בעיות.

[iem]

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

אז איזה גודל מערך ? צריך לדעת מראש את גודלו הרי...

[שניצל]

למה מערך?

תקלוט קלט מהמשתמש תו אחר תו.

[iem]

למה מערך?

תקלוט קלט מהמשתמש תו אחר תו.

הקטע שאתה לא אמור לקלוט תו אחר תו... אתה אמור לקלוט מחרוזת שלמה ואותה "לנתח"...

[שניצל]

אז קלוט את כל המחרוזת, ואז תעבור עליה תו אחר תו.

[iem]

כן אבל אז חזרתי לבעיה הראשונה שלי שאני לא רוצה מונה סוגריים כי אז אני לא יודע איזה סוגריים קדמו לאחרים

אוף אני מתפוצץ עם השאלה הזאת !!!! :'(

[שניצל]

תשתמש במחסנית, כמו שאמרו לך!