מחשבון כבקשתך -חלק ב’

בחלק א’ של פוסט זה הסברתי שאני רוצה לבנות מחשבון שיוכל לקבל קונפיגורציה של קונבנציית כתיבה, ולפתור תרגילים בהתאם.
הרעיון הגיע מהתרגיל  (2+2)2÷8 שהוא ביטוי שיש לו שתי תוצאות שונות בעבור שתי קונבנציות כתיבה שונות.
בחלק הראשון של הפוסט בניתי את המחשבון שלי, ובחלק הנוכחי אני רוצה להוסיף לו קונפיגורציות.

זה האלגורים הבסיסי שלי, שעליו אני בונה – 

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

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]

האלגוריתם שלי יודע להתמודד עם 4 פעולות חשבוניות שמיוצגות על ידי סימנים קבועים – חיבור (+), חיסור (-), כפל (*) וחילוק (/).

בגרסא הנוכחית, האלגוריתם שלי מכיר רק קונבנציית כתיבה אחת – כפל חייב להיות מיוצג על ידי סימן *, ואין כפל מובלע שיש לו קדימות על פני חילוק.
כלומר, כרגע המחשבון שלי בכלל לא יודע איך להתייחס לתרגיל (2+2)2÷8 כי הוא לא יודע איך להתייחס לסוגריים שמגיעים מיד אחרי מספר ללא אופרטור ביניהם.

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

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

8÷2(2+2) = 8÷2*(2+2) = 8÷2*4 = 4*4 = 16

ואופציה אחת שפותרת את התרגיל כך – 

8÷2(2+2) = 8/(2*(2+2)) = 8/(2*4) = 8/8 = 1

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

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

def apply_writing_conv(exp_arr, config):
	new_exp = []
	for i in range(0,len(exp_arr)):
		next_val = exp_arr[i]
		new_exp.append(next_val)
		
		if is_number(next_val) and i < len(exp_arr) - 1 and exp_arr[i+1] == (:
			if config == “config_1”:
				new_exp.append(*)
	return new_exp

אני אריץ דוגמא – 

exp_arr = [8, ÷, 2, (, 2, +, 2, )] apply_writing_conv([8, ÷, 2, (, 2, +, 2, )], config_1): new_exp = [] i=0 next_val = 8 new_exp = [8] i=1 next_val = ÷ new_exp = [8,÷] i=2 next_val = 2 new_exp = [8,÷,2] is_number(2) and exp_arr[3] == ( → new_exp = [8,÷,2, *] i = 3 new_exp = [8,÷,2, *, (] …. new_exp = [8,÷,2, *, (, 2, +, 2, )]

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

אני אתחיל במקרה הפשוט – 

1 + 2(1+1) → 1 + (2*(1+1))

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

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

1 + 2(1+1+2+3+4) → 1 + (2*(1+1+2+3+4))

מה קורה כשיש לי סוגריים בתוך סוגריים?

1 + 2(1+1+(2+3))+4 → 1 + (2*(1+1+(2+3)))+4

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

1 + (2 / 2(1 + 1) + 3) → 1 + (2 / (2*(1 + 1)) + 3) 

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

אני אשנה את האלגוריתם בהתאם – 

def apply_writing_conv_config_2(exp_arr, new_exp, index):
	number = new_exp.pop()
	new_exp.extend( [ (, number, *, ( ])
	parenthesis_counter = 1
	index += 2
	while parenthesis_counter > 0:
		next_val = exp_arr[index]
		new_exp.append(next_val)
		if next_val == (:
			parenthesis_counter += 1
		elif next_val == ):
			parenthesis_counter -= 1
		index += 1
	
	new_exp.append( ) )
	return new_exp, index
		
			
def apply_writing_conv(exp_arr, config):
	new_exp = []
	i =0 
	while i < len(exp_arr):
		next_val = exp_arr[i]
		new_exp.append(next_val)
		if is_number(next_val) and i < len(exp_arr) - 1 and exp_arr[i+1] == (:
			if config == “config_1”:
				new_exp.append(*)
			elif config == “config_2”:
				new_exp, i = apply_writing_conv_config_2(exp_arr, new_exp,i)
		i += 1
	return new_exp

עכשיו אני אריץ את אותה הדוגמא עם הקונפיגורציה השנייה שלי – 

exp_arr = [8, ÷, 2, (, 2, +, 2, )] apply_writing_conv([8, ÷, 2, (, 2, +, 2, )], config_2): new_exp = [] i=0 next_val = 8 new_exp = [8] i=1 next_val = ÷ new_exp = [8,÷] i=2 next_val = 2 new_exp = [8,÷,2] is_number(2) and exp_arr[3] == ( → apply_writing_conv_config_2([8, ÷, 2, (, 2, +, 2, )], [8,÷,2],2) apply_writing_conv_config_2([8, ÷, 2, (, 2, +, 2, )], [8,÷,2],2): number = 2 new_exp = [8, ÷, (, 2, *, ( ] parenthesis_counter = 1 index = 4 next_val = 2 new_exp = [8, ÷, (, 2, *, (, 2 ] index = 5 next_val = + new_exp = [8, ÷, (, 2, *, (, 2, + ] index = 6 next_val = 2 new_exp = [8, ÷, (, 2, *, (, 2, +, 2 ] index = 7 next_val = ) new_exp = [8, ÷, (, 2, *, (, 2, +, 2, ) ] parenthesis_counter = 0 new_exp = [8, ÷, (, 2, *, (, 2, +, 2, ), ) ] return [8, ÷, (, 2, *, (, 2, +, 2, ), ) ], 7 apply_writing_conv([8, ÷, 2, (, 2, +, 2, )], config_2): new_exp, i = [8, ÷, (, 2, *, (, 2, +, 2, ), ) ], 7 return [8, ÷, (, 2, *, (, 2, +, 2, ), ) ]

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

def apply_writing_conv(exp_arr, config):
	new_exp = []
	i =0 
	parenthesis_counter = 0
	while < len(exp_arr):
		next_val = exp_arr[i]
		new_exp.append(next_val)

		if is_number(next_val) and i < len(exp_arr) - 1 and exp_arr[i+1] == (:
			if config == “config_1”:
				new_exp.append(*)
			elif config == “config_2”:
				parenthesis_counter += 1
				number = new_exp.pop()
				new_exp.extend( [ (, number, * )])
		elif next_val == ):
			parenthesis_counter -= 1
			if parenthesis_counter == 0:
				new_exp.append( ) )
		i += 1
	return new_exp

אני אריץ שוב את הדוגמא מלמעלה – 

exp_arr = [8, ÷, 2, (, 2, +, 2, )] apply_writing_conv([8, ÷, 2, (, 2, +, 2, )], config_2): new_exp = [] i =0 parenthesis_counter = 0 next_val = 8 new_exp = [8] i=1 next_val = ÷ new_exp = [8,÷] i=2 next_val = 2 new_exp = [8,÷,2] is_number(2) and exp_arr[3] == ( → parenthesis_counter = 1 number = 2 new_exp = [8,÷, (, 2, *] i = 3 next_val = ( new_exp = [8,÷, (, 2, *, (] parenthesis_counter = 1 i = 4 next_val = 2 new_exp = [8,÷, (, 2, *, (, 2] … i = 7 next_val = ) new_exp = [8,÷, (, 2, *, (, 2, +, 2, )] parenthesis_counter = 0 new_exp = [8,÷, (, 2, *, (, 2, +, 2, ), )] i = 8 return [8,÷, (, 2, *, (, 2, +, 2, ), )]

והוו, הרבה יותר טוב!

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

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

בינתיים, אני אגש לקודד.
קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/calculator/magic_calc.py