Computer Laboratory #1 Solution

It’s  possible to solve an  equation  numerically,  by substituting numbers  for its  variables. It’s also possible to solve an equation symbolically, by using algebra.  For example, to solve the equation m × x + b = y symbolically for x, you’d first subtract b from both sides, giving m × x = y − b. Then you’d divide both sides by m, giving x = (y − b) / m. You may assume that no variable  is equal to zero.

In this laboratory exercise, you’ll write  a Python program  that uses algebra  to solve simple equations symbolically. Your program  will use Python tuples to represent equations, and Python strings  to represent variables.  To simplify the problem,  the equations will use only the binary  arithmetic operators ‘+’, ‘−’, ‘×’, and  ‘/’. Also, your program  need only solve for a variable  that appears  exactly once in an equation. Your program  will use ideas from the constant expression  evaluator that I discussed in class.

 

1. Theory.

 

Here’s a mathematical description of how your program  must  work. First,  L → R means that an equation L is algebraically  transformed into a new equation R. For example:

 

A + B = C     →     B = C − A

 

Second, a variable  is said to be inside an expression if it appears  in that expression at least once. For example,  the variable  x is inside the expression m × x + b, but  it isn’t inside the expression  u − v. Each variable  is considered  to be inside itself, so that x is inside x.

Now suppose that A ◦ B = C is an equation, where A, B, and C are expressions,  and

◦ is one of the four binary  arithmetic operators. Also suppose that the variable  x is inside either  A or B. Then  the following rules show how this equation can be solved for x.



−                                              (1)
 
A + B = C     →     n A = C − B    if x is inside A B = C     A    if x is inside B



−                                               (2)
 
A − B = C     →     n A = C + B    if x is inside A B = A    C    if x is inside B

 



(3)
 
A × B = C     →       A = C / B    if x is inside A B = C / A    if x is inside B

 



(4)
 
A / B = C     →       A = C × B    if x is inside A B = A / C    if x is inside B

 

For example,  I can use the rules to solve the equation m × x + b = y for x. In Rule 1, A is m × x, and  B is b. Since x is inside A, I can transform the equation to m × x = y − b. Then  in Rule 3, A is m, and  B is x. Since x is inside B, I can transform the equation to x = (y − b)/m. Now x is alone on the left side of the equal sign, so the equation is solved. This solution  used only two rules, but  a more complex equation might use more rules, and it might use rules more than once.

2. Representation.

 

Your  program  must  represent  operators  and  variables  as  Python strings.  For  example, it  must  represent the variable  x as the string  'x'. It must  also represent equations and expressions as Python tuples with three elements each. For example,  it must  represent the expression  a + b as the Python tuple  ('a',  '+',  'b').  These  tuples  can  be nested,  so that the equation m × x + b = y is represented like this:

 

((('m',  '*',  'x'),  '+',  'b'),  '=',  'y')

 

The  asterisk  '*' is used  as  the multiplication operator. If you  ignore  the parentheses, commas,  and  apostrophes, then this tuple looks much  like how you’d write  the original equation.  It’s  helpful  to define functions  left,  op,  and  right  that return the parts of tuples that represent expressions.

 

def  left(e):

return  e[0]

def  op(e):

return  e[1]

def  right(e):

return  e[2]

 

For example,  if e is the tuple ('a',  '+',  'b'), then left(e) returns 'a', op(e) returns

'+', and right(e) returns 'b'.

 

3. Implementation.

 

Your program must define the following Python functions, and those functions must behave as described  here.  You must  use the same function  names  as I do, but  you need not use the same parameter  names  as I do. Your functions cannot change  elements of the tuples that are passed to them as arguments, because tuples are immutable.

 

• isInside(v,  e). Test  if the variable  v is inside the expression  e. It’s inside if (1) v equals e, or (2) v is inside the left side of e, or (3) v is inside the right side of e. This definition  is recursive.  Other  functions  in your  program  will need to call isInside. Hint:  Don’t  use the Python operator in  when you write  this  function;  it doesn’t  do what you want here.

 

• solve(v,  q). Solve the equation q for the variable  v, and  return a new equation in which v appears  alone on the left side of the equal sign. For example, if you call solve like this:

 

solve('x',  ((('m',  '*',  'x'),  '+',  'b'),  '=',  'y'))

 

then it will return this:

 

('x',  '=',  (('y',  '-',  'b'),  '/',  'm'))

 

The function solve really just sets things up for the function solving, which does all the work. If v is inside the left side of q, then call solving with v and q. If v is inside the right side of q, then call solving with  v and  a new equation like q, but  with  its

left and  right sides reversed.  In either  case, return the result  of calling solving. If v

is not inside q at all, then return None.

 

• solving(v,  q).  Whenever  this  function  is called,  the variable  v must  be inside the left side of q. If v is equal to the left side of q, then the equation is solved, so simply return q. Otherwise,  decide which of the four transformation  rules (from  Section  1) must  be used next to solve q. Call the function that implements that rule on v and q, then return the result.

 

• solvingAdd(v,  q). Use rule 1 to transform the equation q, then call solving on the variable  v and the transformed q. Return the result  of calling solving.

 

• solvingSubtract(v,  q). Use rule 2 to transform the equation q, then call solving

on the variable  v and the transformed q. Return the result  of calling solving.

 

• solvingMultiply(v,  q). Use rule 3 to transform the equation q, then call solving

on the variable  v and the transformed q. Return the result  of calling solving.

 

• solvingDivide(v,  q). Use rule 4 to transform the equation q, then call solving on the variable  v and the transformed q. Return the result  of calling solving.

 

The functions solvingAdd, solvingSubtract, solvingMultiply, and solvingDivide will have  very  similar  definitions.  If you can  write  one of these functions, then you can  also write  the other three. You need not write  any kind of user interface that reads  equations from the keyboard,  or writes equations to the display. Instead, just call the function solve directly with a nested  tuple that represents an equation.

 

4. Tests.

 

The  file tests.py  on Moodle contains  a series of tests.  Each  test calls a function  from your program,  then prints what the function returns. Each  test also has a comment that says what it should print, and how many  points it is worth.

To grade your work, the TA’s will run  the tests using your functions. If a test prints exactly what it should,  without error,  then you will receive all the points for that test. If a test does anything else, then you will receive no points for that test. Your score for this assignment is the sum of points you receive for all the tests.

 

5. Deliverables.

 

Run  the tests in the file tests.py. Then  submit  the Python code for your functions and the results  of the tests. Your TA will tell you how and where to turn them in. If your lab is on Monday,  January 22, then your work must  be submitted by Monday,  January 29 at

11:55 pm. If your  lab is on Tuesday, January 23, then your  work must  be submitted by Tuesday, January 30 at 11:55 pm. If your lab is on Wednesday, January 24, then your work must  be submitted by Wednesday, January 31 at 11:55 pm. To avoid late penalties,  do not confuse these dates!