אם שוטטתן בפייסבוק לאחרונה כנראה נתקלתן בהתייחסויות לתרגיל (2+2)2÷8 (ואם לא, כדאי לקרוא את ההסבר של לא מדויק).
בקצרה, מדובר בתרגיל חשבוני שיש לו שני פתרונות אפשריים שנובעים מקונבנציות שונות של כתיבת מתמטית. אפשר להתייחס אליו כך –
8÷2*(2+2) = 8÷2*4 = 4*4 = 16
ואפשר להתייחס אליו כך –
8÷2*(2+2) = 8/(2*(2+2)) = 8/(2*4) = 8/8 = 1
אז לפני שמתחילה מלחמת עולם בסגנון ה-little endians מול ה-big endians, חשבתי לנסות ליצור אלגוריתם שיוכל לשרת את שני המחנות.
הרי, אף אחד לא מתווכח על החישוב עצמו, אלא רק על קונבנציית הכתיבה – אז אני הולכת לבנות מחשבון קסום שאפשר יהיה לקנפג, ויספק לכל משתמשת את התשובה שהיא מחפשת.
הפוסט הזה יצא די ארוך, ולכן חילקתי אותו לשני חלקים. בחלק הראשון אני רק בונה את המחשבון שלי, ובחלק הבא אני אוסיף לו את הפיצ’ר של הקונפיגורציה.
אם מעניין אתכן לקרוא איך בניתי מחשבון, תקראו הלאה, ואם לא, אתן יכולות לקפוץ ישר לחלק הבא.
הנה רשימת הדרישות למחשבון שלי –
- המחשבון צריך לקבל ביטוי מתמטי סופי ולהחזיר את התוצאה שלו.
- המחשבון צריך לטפל בחיבור, חיסור, כפל, חילוק וסוגריים לפי סדר פעולות חשבון.
- בהמשך, המחשבון יצטרך לדעת לקבל קונפיגורציות ספציפיות של קונבנציות כתיבה.
אני אתחיל בהתחלה עם כמה דוגמאות פשוטות.
התרגילים הקלים ביותר הם אלו שכוללים רק פעולות מאותו סדר חשיבות.
למשל –
1 + 3 + 2 = 6
2 * 3 * 2 = 12
אם הייתי צריכה לכתוב מחשבון שמתמודד רק עם פעולות מסוג אחד, ללא חשיבות לסדר, הייתי יכולה לכתוב אלגוריתם פשוט שקורא את הביטוי משמאל לימין ופותר אותו.
def solve_expression(exp_arr):
res = exp_arr[0]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
val = exp_arr[i+1]
res = eval_expression(res, operator, val)
i += 2
return res
באלגוריתם הנ”ל אני מניחה ש- exp_arr היא רשימה שכל איבר בה הוא איבר בתרגיל שקיבלתי, וש-eval_expression היא פונקציה שמקבלת שני ארגומנטים ואופרטור ומחזירה את התוצאה של האופרטור על האגרגומנטים.
אני אריץ דוגמא –
exp = 1 + 3 + 2 solve_expression([1,+,3,+,2]): res = 1 i = 1 operator = + val = 3 res = eval_expression(1,+,3) = 4 i = 3 operator = + val = 2 res = eval_expression(4,+,2) = 6 i = 5 return 6
אחלה הדוגמא הזו עובדת. האלגוריתם הנ”ל יעבוד גם לתרגילים שמערבים חיבור וחיסור או כפל וחילוק, אבל לא בעבור תרגילים שמערבים פעולות משני סדרים שונים.
לדוגמא –
exp = 2 + 1 * 3 solve_expression([2,+,1,*,3]): res = 2 i = 1 operator = + val = 1 res = eval_expression(2,+,1) = 3 i = 3 operator = * val = 3 res = eval_expression(3,*3) = 9 i = 5 return 9
כצפוי, קיבלתי תוצאה לא נכונה.
לפי סדר פעולות החשבון החלק הימני של התרגיל – 1*3 צריך להתבצע לפני החלק השמאלי, אבל האלגוריתם הנוכחי שלי פשוט פותר מימין לשמאל, בלי להתייחס לסדר פעולות.
איך אני יכולה להתגבר על הבעיה הזו?
הפתרון הראשון שעולה לי לראש הוא לכתוב אלגוריתם שרץ על התרגיל פעמיים, ובכל פעם פותר רק את החלקים בתרגיל שהם באותו סדר.
כלומר – בריצה הראשונה האלגוריתם יפתור רק פעולות כפל וחילוק, ואז בריצה השנייה הוא יפתור פעולות חיבור וחיסור.
אני אכתוב את האלגוריתם הזה –
def solve_multiplicatio_and_division(exp_arr):
new_exp = [exp_arr[0]]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
if operator in [*,/]:
val_1 = new_exp.pop()
val_2 = exp_arr[i+1]
res = eval_expression(val_1,operator,val_2)
new_exp.append(res)
else:
new_exp.append(operator)
new_exp.append(exp_arr[i+1])
i += 2
return new_exp
def solve_expression(exp_arr):
exp_arr = solve_multiplicatio_and_division(exp_arr)
res = exp_arr[0]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
val = exp_arr[i+1]
res = eval_expression(res, operator, val)
i += 2
return res
מגניב, אז האלגוריתם solve_expression נשאר די אותו הדבר, רק שעכשיו הוא קורא ל- solve_multiplication כדי שיפתור את כל הכפל והחילוק לפני שהוא פותר את החיבור והחיסור.
אני אריץ את אותה הדוגמא שעשיתי קודם ואראה מה קורה הפעם –
exp = 2 + 1 * 3 solve_expression([2,+,1,*,3]): exp_arr = solve_multiplicatio_and_division([2,+,1,*,3]) solve_multiplicatio_and_division([2,+,1,*,3]): new_exp = [2] i = 1 operator = + new_exp = [2,+,1] i = 3 operator = * val_1 = new_exp.pop() = 1 val_2 = 3 res = eval_expression(1,*,3) = 3 new_exp = [2,+,3] i = 5 return [2,+,3] solve_expression([2,+,1,*,3]): exp_arr = [2,+,3] res = 2 i = 1 operator = + val = 3 res = eval_expression(2, +, 3) = 5 i = 3 return 5
יש! קיבלתי תוצאה נכונה.
האם האלגוריתם הזה יעבוד גם במקרה של כמה הכפלות רצופות? למשל –
2 + 1 * 3 * 2 + 4
כן.
מה שעשיתי ב-solve_multiplicatio_and_division הוא בעצם להשתמש במחסנית כדי ליצור את הביטוי החדש שלי. בכל פעם שנתקלתי בכפל או בחילוק שלפתי את האיבר האחרון מהמחסנית, ביצעתי את הפעולה והחזרתי את התוצאה למחסנית. אז במקרה של מספר פעולות כפל רצופות האיבר האחרון שיצא מהמחסנית תמיד יהיה התוצאה של ההכפלה הקודמת.
אז טיפלתי בחיבור, חיסור, כפל וחילוק. אבל מה לגבי סוגריים?
בסדר פעולות החשבון סוגריים הם בדרגה גבוהה יותר מכפל וחילוק.
כלומר, אם יש לי את התרגיל הזה –
2 * (1 + 3)
החיבור צריך להתבצע לפני הכפל –
2 * (1 + 3) = 2 * 4 = 8
נראה לי שבשביל לטפל בסוגריים אני אצטרך טריק דומה לזה שהתמשתי בו בכפל. הבעיה היחידה היא שסוגריים יכולים להכיל ביטוי של יותר משני איברים, כך שאני אצטרך לעקוב ולראות מתי סיימתי כדי שאדע מתי להחזיר את התוצאה למחסנית…
הרעיון הראשון שעולה לי הוא קריאה רקורסיבית ל-solve_expression על הביטוי שבתוך הסוגריים, ואת התוצאה להכניס למחסנית. בעיניי זה פתרון אלגנטי ונקי (נו, אני אוהבת רקורסיות). החיסרון שלו הוא שאני מסתכנת במספר גדול של קריאות רקורסיביות פתוחות. למשל, בביטוי –
2 * (1 + (4 + (2 + ………)))
כמו כן, כדי לאתר את הסגירה של הסוגריים אני אאלץ לרוץ שוב ושוב על אותם איברים וזה לא כל כך יעיל. ואם יש לי כמה זוגות סוגריים אחד בתוך השני אני בכלל אסתבך.
האם יש פתרון יותר טוב?
אני אנסה לחשוב שנייה…
אני יכולה לשנות קצת את האלגוריתם המקורי שלי כדי שקודם יפתור את כל פעולות הכפל והחילוק שמערבות רק מספרים (כלומר, לדלג על פעולות כפל שאחד מהערכים שלהם הוא סוגריים) ואז את כל פעולות החיבור והחיסור שמערבות רק מספרים, ואז להסיר את כל הסוגריים שבתוכם יש מספר יחיד (בשלב הזה כולם אמורים להיות כאלו) ולהריץ את האלגוריתם שוב.
האם פתרון כזה יכול לעבוד?
נראה לי שכן, אבל אני לא בטוחה שהוא יהיה כל כך יעיל.
למשל, בדוגמא מרובת הסוגריים שנתתי למעלה –
2 * (1 + (4 + (2 + ………)))
האלגוריתם הנ”ל ירוץ מספר רב מאוד של פעמים, כי הוא תמיד יגיע לביטוי הפנימי ביותר בסוגריים, יפתור אותו, ואז ירוץ מהתחלה שוב. אז שיפרתי את סיבוכיות המקום, כי האלגוריתם שלי כבר איננו רקורסיבי, אבל שילמתי על כך בסיבוכיות זמן גרועה.
טוב, כרגע לפחות נראה לי שהאינסטינקט הראשוני שלי צדק, ורקורסיה היא אכן התשובה הנכונה. כדי לייעל, אני כן רוצה להימנע מהצורך לחפש סוגריים ימניים כל פעם שאני נתקלת בסוגריים שמאליים, ובמקום זאת להשתמש בסוגריים ימניים כתנאי עצירה לחישובים שלי.
האלגוריתם החדש שלי צריך לפעול באופן הבא –
- לאתחל מחסנית ריקה ולרוץ על הביטוי משמאל לימין.
- אם הוא רואה מספר, להכניס אותו למחסנית.
- אם הוא רואה סוגריים ימניים (סוגרים), לסיים את הריצה ולהחזיר את תוכן המחסנית.
- אם הוא רואה אופרטור, לשלוף את האיבר האחרון מהמחסנית ולחשב את תוצאת ההפעלה של האופרטור עליו ועל הערך הבא בביטוי.
- אם הוא רואה סוגריים פותחים, לקרוא קריאה רקורסיבית על הביטוי מהאינדקס הנוכחי.
*אני מניחה כאן שהאיבר הראשון הוא תמיד מספר ולא סוגריים למען הנוחות, אבל זו הנחה שאפשר לתקן.
def solve_expression(exp_arr, current_operators):
new_exp = [exp_arr[0]]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
if operator == ):
return new_exp
if operator in current_operators:
val = exp_arr[i+1]
if val == (:
val = solve_expression_wrap(exp_arr[i+2:])
res = eval_expression(new_exp.pop(), operator, val)
new_exp.append(res)
else:
new_exp.append(operator)
new_exp.append(exp_arr[i+1])
i += 2
return res
def solve_expression_wrap(exp_arr):
exp_arr = solve_expression(exp_arr, [*,/])
exp_arr = solve_expression(exp_arr, [+,-])
return exp_arr[0]
אוקי, נראה לא רע.
אני אתחיל מבדיקה של דוגמא פשוטה –
exp_arr = [2, *, (, 1, +, 3, )] solve_expression_wrap([2, *, (, 1, +, 3, )]): exp_arr = solve_expression([2, *, (, 1, +, 3, )], [*,/]) solve_expression([2, *, (, 1, +, 3, )], [*,/]): new_exp = [2] i = 1 operator = * val = ( val = solve_expression_wrap([1, +, 3, )]) solve_expression_wrap([1, +, 3, )]): exp_arr = solve_expression([1, +, 3, )], [*,/]) solve_expression([1, +, 3, )], [*,/]): new_exp = [1] i = 1 operator = + new_exp = [1,+,3] i = 3 operator = ) return [1,+,3] solve_expression_wrap([1, +, 3, )]): exp_arr = [1,+,3] exp_arr = solve_expression([1,+,3], [+,-]) … = [4] return 4 solve_expression([2, *, (, 1, +, 3, )], [*,/]): val = 4 res = eval_expression(2, *, 4) = 8 new_exp = [8] i = 3 operator = 1
אוקי, נתקלתי בבאג קטן, אבל סה”כ ההרצה הייתה מאוד טובה.
הסיבה לבאג היא שאני מגדילה את האינדקס בקפיצות קבועות של שתיים, כי עד עכשיו כל החישובים שלי כללו בדיוק שני ארגומנטים ואופרטור, אבל עכשיו הקפיצות צריך להיות תלויות בגודל הביטוי שאני מחשבת, אז אני ארצה ש-solve_expression_wrap יחזיר גם את אורך הביטוי שהוא חישב.
נגיד, בדוגמא למעלה, הביטוי בסוגריים היה באורך 5 סה”כ (כולל סוגריים), והייתי רוצה להזיז את האינדקס 6 מקומות קדימה (5 מקומות לביטוי בסוגריים + מקום אחד לאופרטור).
אני אכניס את השינוי הזה לאלגוריתם –
def solve_expression(exp_arr, current_operators):
new_exp = [exp_arr[0]]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
if operator == ):
return new_exp
exp_length = 2
if operator in current_operators:
val = exp_arr[i+1]
if val == (:
exp_length, val = solve_expression_wrap(exp_arr[i+2:])
res = eval_expression(new_exp.pop(), operator, val)
new_exp.append(res)
else:
new_exp.append(operator)
new_exp.append(exp_arr[i+1])
i += exp_length
return res
def solve_expression_wrap(exp_arr):
exp_arr = solve_expression(exp_arr, [*,/])
exp_arr = solve_expression(exp_arr, [+,-])
return len(exp_arr) + 1, exp_arr[0]
אוקי, עכשיו נראה לי שאני רוצה לעשות דוגמא קצת יותר ארוכה ומאתגרת, רק כדי לוודא שלא פספסתי כלום.
exp = 2 * (1 + 6 / 3) – (5 * 2) exp_arr = [2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )] solve_expression_wrap([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )]): exp_arr = solve_expression([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]) solve_expression([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]): new_exp = [2] i = 1 operator = * exp_length = 2 val = ( exp_length, val = solve_expression_wrap([1, +, 6, /, 3), -, (, 5, *, 2, )]) solve_expression_wrap([1, +, 6, /, 3), -, (, 5, *, 2, )]): exp_arr = solve_expression([1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]) solve_expression([1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]): new_exp = [1] i = 1 operator = + exp_length = 2 new_exp = [1,+,6] i = 3 operator = / exp_legnth = 2 val = 3 res = eval_expression(6, /, 3) = 2 new_exp = [1, + , 2] i = 5 operator = ) return [1 + 2] solve_expression_wrap([1, +, 6, /, 3), -, (, 5, *, 2, )]): exp_arr = [1+2] exp = solve_expression([1,+,2], [+,-]) … = [3] return 12, [3]
אוי לא, עוד באג! טוב שעשיתי דוגמא ארוכה.
גם הפעם הבאג הוא בדמות הקפיצה קדימה, בטעות עשיתי קפיצה באורך כל הביטוי מהנקודה הנוכחית ועד סופו, במקום רק באורך הביטוי שבתוך הסוגריים.
הפתרון ההגיוני הוא לחשב את אורך הביטוי ברגע שאני נתקלת בסוגריים ימניים ולהחזיר אותו.
אני אשנה בהתאם –
def solve_expression(exp_arr, current_operators):
new_exp = [exp_arr[0]]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
if operator == ):
current_exp_length = i + 2
return current_exp_length, new_exp
sub_exp_length = 2
if operator in current_operators:
val = exp_arr[i+1]
if val == (:
sub_exp_length, val = solve_expression_wrap(exp_arr[i+2:])
res = eval_expression(new_exp.pop(), operator, val)
new_exp.append(res)
else:
new_exp.append(operator)
new_exp.append(exp_arr[i+1])
i += sub_exp_length
return len(exp_arr), new_exp
def solve_expression_wrap(exp_arr):
sub_exp_length, exp_arr = solve_expression(exp_arr, [*,/])
_, exp_arr = solve_expression(exp_arr, [+,-])
return sub_exp_length + 1, exp_arr[0]
הסיבה שאני מתייחסת לאורך הביטוי רק בקריאה הראשונה (עם הכפל והחילוק) ולא בקריאה השניה (עם החיבור והחיסור) הוא שהחישוב הראשון יכול לקצר את הביטוי, ואני רוצה לקבל את האורך המקורי.
אני אמשיך את הדוגמא שלי מאותה נקודה עם השינוי –
solve_expression_wrap([1, +, 6, /, 3), -, (, 5, *, 2, )]): exp_arr = [1+2] exp_arr = solve_expression([1,+,2], [+,-]) … = [3] return 7, 3 solve_expression([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]): sub_exp_length, val = 7, 3 res = eval_expression(2, *, 3) new_exp = [6] i = 8 operator = – sub_exp_length = 2 new_exp = [6, -, (] i = 10 operator = 5
אוי, באג.
טוב, ידעתי שלכתוב מחשבון לא יהיה התהליך הכי מהיר בעולם.
מה בעצם קרה פה?
כיוון שהאופרטור היה חיסור, והייתי בשלב של כפל וחילוק רציתי לדחוף אותו למחסנית כמו שהוא ולהמשיך הלאה.
אם החיסור היה בין שני מספרים, הייתי דוחפת את שני המספרים והאופרטור למחסנית (זה מה שעשיתי עד כה) אבל כיוון שהחיסור נעשה בין מספר ובין תוצאה של חישוב בסוגריים אני לא יכולה פשוט לדחוף את המספר פנימה, אני צריכה לחשב את הביטוי בסוגריים קודם.
בעצם נראה שאם אני נתקלת בביטוי בסוגריים אני תמיד צריכה לחשב אותו כדי לפשט את התרגיל הכללי, ללא תלות באופרטור שקדם לסוגריים. זה מאוד הגיוני.
אני אשנה את האלגוריתם בהתאם –
def solve_expression(exp_arr, current_operators):
new_exp = [exp_arr[0]]
i = 1
while i < len(exp_arr):
operator = exp_arr[i]
if operator == ):
current_exp_length = i + 2
return current_exp_length, new_exp
sub_exp_length = 2
val = exp_arr[i+1]
if val == (:
sub_exp_length, val = solve_expression_wrap(exp_arr[i+2:])
if operator in current_operators:
res = eval_expression(new_exp.pop(), operator, val)
new_exp.append(res)
else:
new_exp.append(operator)
new_exp.append(val)
i += sub_exp_length
return len(exp_arr), new_exp
[/sourcecode]
אני אמשיך את הדוגמא שלי מאותה נקודה עם השינוי –
solve_expression([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]): i = 8 operator = – sub_exp_length = 2 val = ( sub_exp_length, val = solve_expression_wrap([5, *, 2, )]) solve_expression_wrap([5, *, 2, )]): sub_exp_length, exp_arr = solve_expression([5, *, 2, )], [*,/]) solve_expression([5, *, 2, )], [*,/]): new_exp = [5] i = 1 operator = * sub_exp_length = 2 val = 2 res = eval_expression(5, *, 2) = 10 new_exp = [10] i = 3 operator = ) current_exp_length = 5 return 5, [10] solve_expression_wrap([5, *, 2, )]): sub_exp_length, exp_arr = 5,[10] _, exp_arr = solve_expression([10], [+,-]) … = [10] return 6, 10 solve_expression([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )], [*,/]): sub_exp_length, val = 6,10 new_exp = [6,-,10] i = 14 return 3, [6, -10] solve_expression_wrap([2, *, (, 1, +, 6, /, 3), -, (, 5, *, 2, )]): sub_exp_length, exp_arr = 3, [6,-,10] _, exp_arr = solve_expression([6,-,10], [+,-]) = … = -4 return 3, -4
יש! קיבלתי את התוצאה הנכונה!
(למי ששכחה התרגיל היה 2 * (1 + 6 / 3) – (5 * 2), תרגישו חופשיות לבדוק).
אני מודה שזו הייתה הבדיקה הכי ארוכה בעולם, אבל תראו כמה באגים מצאתי במהלכה, איזה אושר!
עכשיו אני אגש לקודד את המחשבון שלי, ובחלק הבא של הפוסט אני אוסיף לו קונפיגורציה!
קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/calculator/basic_calc.py
תגובה אחת בנושא “מחשבון כבקשתך – חלק א’”