עזרה בשאלה ברקורסיה שפת c

[evy]

אהלן,

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

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

המחרוזות שיוכנסו לדוגמא הם :(2+3) , ((45+5)*(6^4)) ,(5*(6^5)) וכו...

קלט לא תקין הוא 4+6 , 4 , (5+4 , (7+5*5) , (45 +6+7))....

בתוך זוג סוגריים חייבים להיות שני ביטויים לכל היותר (כלומר מותר מספר אחד או שניים)

לכל ביטוי חייבים להיות סוגריים כלומר לא יכול להיות 4+6

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

[Gil28]

הייתי חושב על ביטויים רגולריים.

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

ובאמצע תוודא שזה אופרטור.

[evy]

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

[Gil28]

עזוב ביטויים רגולריים.

פלינדרום הוא ביטוי שנראה אותו דבר מימין ומשמאל. למשל:

2332 , 1234321, aviva

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

קטן יותר (בלי התו הראשון והאחרון).

בעיקרון צריף לחשוב על זה. אתה יכול להשוות בין האיבר הראשון לאחרון ולוודא שאחד זה פותח ואחד סוגר. אח"כ צריך להסתדר עם המספרים (שלא חייבים להיות באותו אורך) קצת מסורבל בשביל רקורסיה האמת.

[evy]

הקטע שהביטוי (7+(5*4)) הוא חוקי! וזה לא סימטרי בדיוק...

אבל עזוב...

אם הייתי שואל על דרך לא רקורסיבית,איך ניתן לעשות זאת?

[שניצל]

רקורסיה היא לא תחליף ללולאות. יש אלגוריתמים שמיועדים ללולאות, ויש כאלו שמיועדים לרקורסיות. אמנם כל לולאה ניתן להחליף ברקורסיה בקלות יתרה (יש שפות שבהן אין באמת לולאות ולכן כל לולאה יש לממש ע"י רקורסיה), אבל יש רקורסיות שקשה להפוך ללולאות (אם היה קל להפוך את הרקורסיה ללולאה, כנראה לא היה צריך להשתמש ברקורסיה מלכתחילה).

תחשוב על זה באופן הבא: "ביטוי חוקי" הוא או מספר, או משהו מהצורה (ABC) כאשר B היא סימן של פעולה כלשהי (נניח +, -, ^, *) ו-A ו-C הם גם כן ביטויים חוקיים.

הפונקציה שלך צריכה לבדוק את הדברים הבאים:

1. אם הביטוי הוא פשוט מספר, החזר אמת.

2. אחרת, בדוק אם הביטוי מתחיל ונגמר בסוגריים. אם לא, אז הביטוי לא חוקי - החזר שקר.

3. חפש את B - הסימן ה"חיצוני" (זה שלא מוכל בשום סוגריים, פרט לסוגריים הראשיים) בביטוי. אם אין כזה, או שיש יותר מאחד - הביטוי לא חוקי.

4. חלק את הביטוי לשני הביטויים A ו-C כנ"ל, לפי המיקום של הסימן.

5. בדוק, באופן רקורסיבי, ש-A ו-C הם אכן ביטויים חוקיים. אם כן, החזר אמת, אחרת החזר שקר.

[evy]

מה שרשמת בסעיפים זה סדר הפעולות שאני צריך לבצע בפונק' רקורסיבית לפי הסדר? או שזה באופן אקראי?

ועוד שאלה ,אם אני רוצה שיהיו שני "ביטויים חוקיים" בלבד בכל זוג סוגריים,כלומר אסור (7+4+5) אז זה גם תופס?

[Gil28]

שניצל - לפי מה שאמרת הביטוי הבא חוקי:

((2+3)-(1+4))

[levy.mor]

הפונק הבאה כנראה היא הדרך לפיתרון

http://www.cplusplus.com/reference/clibrary/cstring/strtok/

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

אתה יכול להעזר בלמממש את זה עם atoi.

ואני הייתי משתמש בלולאת while עד שתקבל EOF.

[שניצל]

ועוד שאלה ,אם אני רוצה שיהיו שני "ביטויים חוקיים" בלבד בכל זוג סוגריים,כלומר אסור (7+4+5) אז זה גם תופס?

בבירור הכוונה היא לפי הסדר ולא באופן אקראי. בד"כ משאירים את הרקורסיה לסוף.

ועוד שאלה ,אם אני רוצה שיהיו שני "ביטויים חוקיים" בלבד בכל זוג סוגריים,כלומר אסור (7+4+5) אז זה גם תופס?

שים לב לבדיקה שהאלגוריתם עושה בשלב 3.

שניצל - לפי מה שאמרת הביטוי הבא חוקי:

((2+3)-(1+4))

מה הבעיה בזה?

[Gil28]

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

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

[שניצל]

נראה לי שהכוונה היא שבכל ביטוי צריך שני ביטויים לכל היותר (שים לב לדוגמאות).

[evy]

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

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

[evy]

שניצל אני חייב לך המון תודות!

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

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

 
int is_legal_exp (char s[]){ 
 int bad=0;
 char expr1[50]={'\0'},expr2[50]={'\0'};

if(check_quit(s)==-1) 
  return -1;
if(bad_chars(s))
  return 1;
if ( just_number(s,0) )
  return 0;
else{ 
  if (s[0]!='(' || s[strlen(s)-1]!=')' )
    return 1;
}
bad=check_oper(s);
if (bad)
  return 1;

partition (s,expr1,expr2);

if (is_legal_exp(expr1)==0 && is_legal_exp(expr2)==0 )
  return 0;
else
  return 1;
} 

[שניצל]

הקוד שלך לא ממש קריא, אתה צריך לדאוג לסוגריים מסולסלים בכל if/else ולהזחה נכונה (אינדנטציה).

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