Home/

...

/

Problem Challenge 1

Problem Challenge 1

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Problem Challenge 1 lesson:

Press + to interact
Python 3.5
def diff_ways_to_evaluate_expression(input):
  result = []
  # base case: if the input string is a number, parse and add it to output.
  if '+' not in input and '-' not in input and '*' not in input:
    result.append(int(input))
  else:
    for i in range(0, len(input)):
      char = input[i]
      if not char.isdigit():
        # break the equation here into two parts and make recursively calls
        leftParts = diff_ways_to_evaluate_expression(input[0:i])
        rightParts = diff_ways_to_evaluate_expression(input[i+1:])
        for part1 in leftParts:
          for part2 in rightParts:
            if char == '+':
              result.append(part1 + part2)
            elif char == '-':
              result.append(part1 - part2)
            elif char == '*':
              result.append(part1 * part2)
  return result
def main():
  print("Expression evaluations: " +
        str(diff_ways_to_evaluate_expression("1+2*3")))
  print("Expression evaluations: " +
        str(diff_ways_to_evaluate_expression("2*3-4-5")))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample input #1

input: 1+2*3

Recursive Call

Line No.

char

input[0:i]

input[i+1:]

leftParts

rightParts

result

Evaluating 1+2*3

-


-

-

-

-

[]


8

1

-

-

-

-

[]

Next Operator Found

8

+

-

-

-

-

-

Expressions Divided

11-12


1

2*3

-

-

-

Recursive call on expression "1" returns

11




[1]



Recursive call on expression 2*3

8

2






Expressions Divided

8

*

2

3





11

*

2

3

[2]




12

*

2

3

[2]

[3]



20

*

2

3

[2]

[3]

[6]

Recursive call on expression 2*3 returns

12




[1]

[6]



16

+

1

2*3

[1]

[6]

[7]

Next Operator Found

8

*

-

-




Expressions Divided

11-12

*

1+2

3




Recursive call on expression 1+2

8

1







8

+

1

2





11

+

1

2

[1]




12

+

1

2

[1]

[2]



20

+

1

2

[1]

[2]

[3]

Resursive call on expression 1+2 returns

11

*

1+2

3

[3]



Recursive call on expression "3" returns

12

*

1+2

3

[3]

[3]



20

*

1+2

3

[3]

[3]

[7,9]

Sample input #2

Students may be encouraged to complete the dry-run with this input:

input: 2*3-4+5

Rescursive call

Line No.

char

input[0:i]

input[i+1:]

leftParts

rightParts

result

Evaluating 2*3-4+5

-

-





[]

Next Operator Found

8

*






Expressions Divided

11-12

*

2

3-4+5




Recursive call on expression "2" returns

11

*

2

3-4+5

[2]



Recursive call on expression "3-4+5"

8

-






Expressions divided

11-12

-

3

4+5




Recursive call on expression "3" returns

11

-

3

4+5

[3]



Recursive call on expression 4+5

8

+






Recursive call on "4" returns

11

+

4

5

[4]



Recursive call on "5" returns

12

+

4

5

[4]

[5]



16

+

4

5

[4]

[5]

[9]

Recursive call on 4+5 returns

12

-

3

4+5

[3]

[9]



18

-

3

4+5

[3]

[9]

[-6]

...

...

...

...

...

...

...

...

Step-by-step solution construction

We start parsing the expression from the left and divide the expression into sub-expressions whenever we hit upon an operator (lines 8-17).

In the code below, referring to lines 11-12, we split the expression when calling the function recursively on sub-expressions input[0:i] and input[i+1:].

Notice the new parameter level in the function prototype: it is only used to generate the execution trace. It has nothing to do with the actual solution to the problem.

Press + to interact
Python 3.5
def diff_ways_to_evaluate_expression(input,level):
  result = []
  # base case: if the input string is a number, parse and add it to output.
  if '+' not in input and '-' not in input and '*' not in input:
    result.append(int(input))
  else:
    print("\t"*level,"Evaluating Expression: ",input)
    for i in range(0, len(input)):
      char = input[i]
      if not char.isdigit():
        print("\t"*level,"\tEvaluating operator: ",char)
        # break the equation here into two parts and make recursively calls
        print("\t"*level,"\tEvaluating Sub-expressions: (", input[0:i], ") & (",input[i+1:], ")", sep="")
        leftParts = diff_ways_to_evaluate_expression(input[0:i],level+1)
        print("\t"*level,"\tResult(s) of Expression ",input[0:i]," is/are: ",leftParts)
        rightParts = diff_ways_to_evaluate_expression(input[i+1:],level+1)
        print("\t"*level,"\tResult(s) of Expression ",input[i+1:]," is/are: ",rightParts)
        
  return result
def main():
  expressions = ["1+2*3","2*3-4+5"]
  for expression in expressions:
    print("Evaluating expression: ",expression)
    result = diff_ways_to_evaluate_expression(expression,0)
    print("All possible results of the expression evaluation are: ",result)
    print("-"*100+"\n")
main()

We will receive multiple results from expression evaluations because the sub-expressions can also be split into multiple expressions. We have to perform the operation for all pairs of results from the expression divisions input[0:i] and input[i+1:].

In the code below, we get results for all possible expressions of the sub-expression input[0:i] in leftParts. Similarly, we receive results for all possible expressions of the sub-expression input[i+1:] in rightParts. We have to perform the operation on each result in rightParts against all results in leftParts (lines 18-31).

Press + to interact
Python 3.5
def diff_ways_to_evaluate_expression(input,level):
  result = []
  # base case: if the input string is a number, parse and add it to output.
  if '+' not in input and '-' not in input and '*' not in input:
    result.append(int(input))
  else:
    print("\t"*level,"Evaluating Expression: ",input)
    for i in range(0, len(input)):
      char = input[i]
      if not char.isdigit():
        print("\t"*level,"\tEvaluating operator: ",char)
        # break the equation here into two parts and make recursively calls
        print("\t"*level,"\tEvaluating Sub-expressions: (", input[0:i], ") & (",input[i+1:], ")", sep="")
        leftParts = diff_ways_to_evaluate_expression(input[0:i],level+1)
        print("\t"*level,"\tResult(s) of Expression ",input[0:i]," is/are: ",leftParts)
        rightParts = diff_ways_to_evaluate_expression(input[i+1:],level+1)
        print("\t"*level,"\tResult(s) of Expression ",input[i+1:]," is/are: ",rightParts)
        for part1 in leftParts:
          for part2 in rightParts:
            if char == '+':
              print("\t"*level,"\tPerforming ",part1,"+",part2)
              result.append(part1 + part2)
              print("\t"*level,"\tUpdated result array: ",result)
            elif char == '-':
              print("\t"*level,"\tPerforming ",part1,"-",part2)
              result.append(part1 - part2)
              print("\t"*level,"\tUpdated result array: ",result)
            elif char == '*':
              print("\t"*level,"\tPerforming ",part1,"*",part2)
              result.append(part1 * part2)
              print("\t"*level,"\tUpdated result array: ",result)
  return result
def main():
  expressions = ["1+2*3","2*3-4+5"]
  for expression in expressions:
    print("Evaluating expression: ",expression)
    result = diff_ways_to_evaluate_expression(expression,0)
    print("All possible results of the expression evaluation are: ",result)
    print("-"*100+"\n")
main()