| כותב |
|
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 23 April 2011 בשעה 12:46 | | IP רשוּם
|
|
|
|
שלום לכולם!
אני צריך לבנות תכנית שלמה שבנויה מפונקציות רקורסיביות. התכנית עצמה מייצגת מחשבון של מספרים שלמים. כאשר המשתמש מקליד מחרוזת של מספרים ופעולות חשבון וצריך לחשב ולהחזיר פתרון.
יש לי פונקציה אחת שצריכה לקבל את מחרוזת הקלט ושני מחרוזות ריקות נוספות וצריכה להחזיר את האופרטור כתו (למשל:+,* וכו') ובנוסף למלא את שתי המחרוזות בביטויים שנמצאים מימין ומשמאל לאופרטור.
באופן כללי, הקלט של המשתמש צריך להכיל ביטויים ופעולות כאשר כל ביטוי חייב להופיע בסוגריים. משהו בסגנון הזה:
(((11+29)%(3+1))^(((3c5)s10)s(1+2))) .
הצלחתי לממש את הפונקציה הזו על מקרה פרטי של:
(ביטוי-אופרטור-ביטוי) , למשל : (2+4).
השאלה שלי איך לעשות זאת עבור ביטוי ענק כמו שמוזכר למעלה?
אני מזכיר שזה חייב להיות רקורסיבי ושאסור לי להשתמש במצביעים אלא רק בכתובות של המערכים..
* חשבתי שאולי צריך פונקציה שתעבור על מחרוזת הקלט ותחזיר כביכול את מבנה המחרוזת, כלומר איפה מתחיל ביטוי ואיפה נגמר.. אבל זה רק באופן תאורטי..
אשמח לעזרה!
תודה מראש..
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 23 April 2011 בשעה 20:39 | | IP רשוּם
|
|
|
|
ככה: סוגריים אתה יודע איפה מתחילים ואיפה מסתיימים (סופר כמה פתיחות יש מהתחלה שלהם וכמה סגירות, וכשזה 0 נסגרו הסוגריים, אם זה קטן מ-0 יש סגירת סוגריים לא חוקית)
אם בביטוי אין סוגריים אתה פוטר אותו
אם יש בו סוגריים אתה מריץ עליהם רקורסיבית את הפונקציה ומחליף את הסוגריים בתוצאה (לא חייב ממש להחליף כמובן, יכול מאוד להיות שעבור שני המספרים שסובבים את האופרטור אתה תצטרך להחליט לפי התו הראשון בביטוי האם להריץ רקורסיבית את הפונקציה על סוגריים או פשוט לפרסר מספר - וזה יהיה המספר שתשמור)
בהצלחה
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 23 April 2011 בשעה 22:55 | | IP רשוּם
|
|
|
|
האמת שחשבתי על "להחליף" את מה שהיה בסוגריים לתוצאה אבל אני לא יודע איך לעשות את זה (כי צריך להפוך את התווים למספרים שלמים ע"מ לבצע חישוב ואז להחזיר את התוצאה להיות תו?!?)..
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 24 April 2011 בשעה 14:41 | | IP רשוּם
|
|
|
|
בוא נראה מה עשית בינתיים ונבין איך להמשיך משם ?
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 24 April 2011 בשעה 23:33 | | IP רשוּם
|
|
|
|
טוב... אפשר לומר בוודאות שלא הבנתי את הפתרון שלך.. ובאמת שניסיתי!
וגם אם הייתי מבין מה הצעת לעשות.. אין לי מושג איך להחליף רקורסיבית וכל זה.. אני אשמח אם תפנה אותי למקום שיש בו כל מיני טכניקות של רקורסיה(כבר קראתי את המאמרים של ניר אדר בנושא ד"א ).
או שאם תוכל לפרסם קוד של משהו דומה למה שהצעת..
תודה וסליחה..
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 25 April 2011 בשעה 12:11 | | IP רשוּם
|
|
|
|
קוד:
using System;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
string expression = Console.ReadLine();
double result = CalculateExpression(expression, 0, expression.Length-1);
Console.WriteLine(result);
}
private static double CalculateExpression(string expression, int start, int end)
{
if (expression[start] == '(')
{
int depth = 0;
for (int i = start; i <= end; i++)
{
if (expression[i] == '(')
{
++depth;
}
else if (expression[i] == ')')
{
--depth;
if (depth == 0)
{
if (i == end)
{
return CalculateExpression(expression, start + 1, end - 1);
}
else
{
return ApplyOperator(expression, start + 1, i - 1, expression[i + 1], i + 1, end);
}
}
}
}
throw new Exception("missing sograiim closing at position " + end.ToString());
}
else
{
int number = 0;
for (int i = start; i <= end; i++)
{
if (char.IsDigit(expression, i))
{
number = number * 10 + (expression[i] - '0');
}
else // char is operator
{
return ApplyOperator(expression, start, i - 1, expression[i], i + 1, end);
}
}
return number;
}
}
private static double ApplyOperator(string expression, int start1, int end1, char operatorChar, int start2, int end2)
{
double number1 = CalculateExpression(expression, start1, end1);
double number2 = CalculateExpression(expression, start2, end2);
switch (operatorChar)
{
case '-':
return number1 - number2;
case '+':
return number1 + number2;
case '/':
return number1 / number2;
case '*':
return number1 * number2;
case '^':
return Math.Pow(number1, number2);
default:
throw new Exception("invalid operator charachter '" + operatorChar + "'");
}
}
}
} |
|
|
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 25 April 2011 בשעה 13:37 | | IP רשוּם
|
|
|
|
זה כתוב בשפת c?
|
| חזרה לתחילת העמוד |
|
| |
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 25 April 2011 בשעה 13:38 | | IP רשוּם
|
|
|
|
אתה יכול להסביר את הקוד? כי חוץ מהסוויץ' קייס לא הבנתי כלום 
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 25 April 2011 בשעה 17:25 | | IP רשוּם
|
|
|
|
זה כתוב ב-C#
הפונקציה הראשית מחולקת לשני חלקים:
1. אם המחרוזת מתחילה בסוגריים
- מוצא איפה נגמרים הסוגריים
- אם זה סוף הביטוי מחזיר פתרון של מה שבתוך הסוגריים (לא כולל הסוגריים - קריאה רקורסיבית אחת לפונקציה הראשית).
- אם הסוגריים נגמרו וזה לא סוף המחרוזת מניח שאחרי הסוגריים יש אופרטור
- במקרה כזה מעביר לפונקציה שמקבלת שני ביטויים ואופרטור שבינהם (פונקציה נוספת): מעביר את הסוגריים כפרמטר השמאלי, את האופרטור, ואת הצד הימני - כל מה שנשאר מהמחרוזת לא כולל התו האחרון שהוא הסגירת סוגריים הראשיים.
במקרה כזה הפונקציה המפעילה אופרטור תעביר כל אחד מהצדדים לבדו לפונקציה הראשית - תקבל שתי תוצאות, ותפעיל את האופרטור על שני המספרים, ותחזיר את התוצאה.
2. אם המחרוזת מתחילה במספר
- מוצא איפה נגמר המספר
- אם המספר נגמר בסוף המחרוזת הגענו למקרה הפשוט של הפונקציה שלא דורש רקורסיה - ומחזירים את המספר הזה (כמספר ולא מחרוזת כמובן)
- אם המספר נגמר וזה לא סוף המחרוזת, כנראה שיש לפנינו מספר, אחריו אופרטור, ואחריו עוד ביטוי.
- מעביר רקורסיבית את הביטוי עד האופרטור (המספר), את האופרטור, ואת מה שנשאר מהביטוי אחרי האופרטור (המספר / הביטוי השני להפעיל עליו את האופטור) לפונקציה שמקבלת שני ביטויים ואופרטור.
במקרה כזה הפונקציה המפעילה אופרטור תעביר כל אחד מהצדדים לבדו לפונקציה
הראשית - תקבל שתי תוצאות, ותפעיל את האופרטור על שני המספרים, ותחזיר את
התוצאה.
------
דוגמא: (2+2)*6
1. הביטוי מתחיל במספר, אבל המספר מפסיק באמצע (יש אופרטור *)
2. קריאה לפונקציה שפותרת עם אופרטור. מחרוזת ראשונה היא עד האופרטור: 6, מחרוזת שנייה: כל מה שאחרי: (2+2). אופרטור: *.
3.1. פתרון ביטוי: 6 - המחרוזת כולה היא מספר, הפתרון הוא 6.
3.2. פתרון ביטוי: (2+2) - המחרוזת כולה סוגריים, מחזיר פתרון ביטוי ללא הסוגריים: 2+2
3.2.1. פתרון הביטוי 2+2, המחרוזת מתחילה במספר אבל המספר נגמר באופרטור, קריאה לפונקציה שמקבלת שני ביטויים ואופרטור, ביטוי ראשון: 2, אופרטור: +, ביטוי שני: 2.
3.2.1.1. פתרון ביטוי: 2 - מחזיר את המספר 2.
3.2.1.2. פתרון ביטוי: 2 - מחזיר את המספר 2.
3.2.1.3. הפעלת אורטור + על התוצאות: 2+2- מחזיר 4.
3.3. הפעלת האופרטור * על 6 ו-4: מחזיר 24 (כלומר גם סעיף 3 מחזיר 24, כלומר עם סעיף 1 מחזיר 24, כלומר זה בפלט של האלגוריתם).
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 26 April 2011 בשעה 09:54 | | IP רשוּם
|
|
|
|
אוקיי.. עכשיו הכל מובן יותר..
אני אצטרך קצת זמן לעכל את זה ולתרגם לשפת סי..
המון תודה לך!
|
| חזרה לתחילת העמוד |
|
| |
eyalmen
משתמש מתחיל
הצטרף / הצטרפה: 02 April 2011
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 02 May 2011 בשעה 20:32 | | IP רשוּם
|
|
|
|
איך אני מחליף את הלולאה ב-calculate expression לפונקציה רקורסיבית שעושה את אותה הפעולה? כי אסור לי לולאות בכלל?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 03 May 2011 בשעה 10:49 | | IP רשוּם
|
|
|
|
תוסיף עוד פרמטר לפונקציה שהוא I של הלולאה, ותקדם אותו בקריאה רקורסיבית
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
