Calculator

Reading and parsing of expressions (Grade 6)

to_number(s)

Convert string to int if possible, else return the original string.

to_number(‘42’) returns 42, while to_number(‘x’) returns ‘x’.

Parameters:s (str) – string that is converted to a number
Returns:if the argument contains a number; to_number(‘42’) return 42 str: otherwise; to_number(‘x’) return ‘x’
Return type:int
parse(s)

Parse a string with expression into tuple (name, operation, arguments).

Parameters:s (str) – expression
Returns:expression parsed into (name, operation, arguments)
Return type:tuple

See documentation for function read() for examples of expressions.

The operation can be unary SET or NOT, or binary AND, OR, LSHIFT or RSHIFT. Note that SET is not spelled out in the input string; see the examples below. The last element, arguments is itself a tuple of arguments; that is, a tuple with 1 or 2 elements. Numeric arguments are converted to int.

Examples

  • parse(‘abc OR x -> z’) returns (‘z’, ‘OR’, (‘abc’, ‘x’))

  • parse(‘t RSHIFT 3 -> a’) returns (‘a’, ‘RSHIFT’, (‘t’, 3))

    (the second element of the tuple, 3 is an int, ot a str ‘3’)

  • parse(‘42 -> ever’) returns (‘ever’, ‘SET’, (42, ))

    Note that ‘SET’ is not present (but only applied) in the input string, yet it is explicit in the parsed string. Also note that arguments is a tuple with a single element, (42, ).

  • parse(‘NOT big -> small’) returns (‘small’, ‘NOT’, (‘big’)

read(filename)

Read a file with expressions (one in each line) into a list.

Parameters:filename – the name of the file
Returns:a list of expressions as tuples, such as returned by parse

Example

If file input.txt looks like this:

123 -> x
456 -> y
x AND y -> d
x OR y -> e
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i

then read(‘input.txt’) must return the following list:

[('x', 'SET', (123,)),
 ('y', 'SET', (456,)),
 ('d', 'AND', ('x', 'y')),
 ('e', 'OR', ('x', 'y')),
 ('f', 'LSHIFT', ('x', 2)),
 ('g', 'RSHIFT', ('y', 2)),
 ('h', 'NOT', ('x',)),
 ('i', 'NOT', ('y',))]

Expression checking (Grade 7)

inputs(exprs)

Return a set of names of all variables that appear as arguments

Parameters:exprs (list) – a list of expressions, like those returned be read
Returns:a set of variable names
Return type:set

Examples

Call

outputs([('a', 'SET', ('b',)),
         ('e', 'AND', (12, 'x')),
         ('x', 'AND', ('z', 5))]`

returns {‘b’, ‘x’, ‘z’}. Note that 12 and 5 are absent from the list since these are not variables.

outputs(exprs)

Return a set of names of all variables that are computed by expressions

Parameters:exprs (list) – a list of expressions, like those returned be read
Returns:a set of variable names
Return type:set

Examples

Call

outputs([('a', 'SET', ('b',)),
         ('e', 'AND', (12, 'x')),
         ('x', 'AND', ('z', 5))]`

returns {‘a’, ‘e’, ‘x’}

check_names(exprs)

Check whether all inputs are also computed by some expression

Parameters:exprs (list) – a list of expressions
Returns:True if all inputs also appear as outputs of some expression
Return type:bool
check_operators(exprs)

Check the validity of operator names

Valid operator names are SET, NOT, AND, OR, LSHIFT and RSHIFT

Parameters:exprs (list) – a list of expressions
Returns:True if all operators are valid
Return type:bool

Example

The function returns False for a list like this:

[('a', 'SET', ('b',)),
 ('e', 'LSHIFT', (12, 'x')),
 ('f', 'NOSUCHTHING', ('z', 5)),
 ('g', 'OR', (7, 5)),
 ('b', 'NOT', ('c',))]

Evaluation of expressions and lists of expressions (Grade 8)

get_value(name, variables)

Return the value corresponding to the name.

Parameters:
  • name (str or int) – the name of a variable or an int
  • variables (dict) – a dictionary with variables names as keys and their values as values
Returns:

the value of the variable or the integer given as argument
Return type:

int

The function assumes that the name exists in the dictionary.

Examples

  • get_value(42, {‘a’: 13, ‘foo’: -65) returns 42
  • get_value(‘foo’, {‘a’: 13, ‘foo’: -65) returns -65
get_values(args, variables)

Return the tuple of values corresponding to the names in the tuple.

Parameters:
  • args – a tuple of str and/or int
  • variables (dict) – a dictionary with variables names as keys and their values as values
Returns:

values of variables as int
Return type:

tuple

The function is similar to get_value except that it takes a tuple and returns a tuple.

Example

get_values((‘foo’, 42), {‘a’: 13, ‘foo’: -65) returns (-65, 42)

compute_expr(op, args)

Compute an expression

Parameters:
  • op – operator, one of ‘SET’, ‘NOT’, ‘AND’, ‘OR’, ‘LSHIFT’, ‘RSHIFT’
  • args – arguments, given as a tuple with one or two int
Returns:

result of an expression
Return type:

int

The function assumes that the operator is valid and that the number of arguments matches the operator type.

Operations are interpreted as bitwise, not logical operations. The function uses Python built-in operators ~ for NOT, & for AND, | for OR, << for LSHIFT and >> for RSHIFT.

Let a and b be the first and the second argument (if there are two). The function works as follows. If the operator is

  • “SET”, result is a,
  • “NOT”, result is ~a (note: tilde, not minus),
  • “AND” and “OR”, results are a AND b and a OR b, respectively,
  • “LSHIFT” and “RSHIFT”, results are a << b and a >> b, respectively.

Examples

  • compute_expr(“SET”, (12, )) returns 12
  • compute_expr(“AND”, (13, 69)) returns 5, computed as 13 & 69
compute_list(exprs)

Compute a list of expressions; return a dictionary with names and values

Parameters:exprs (list) – a list of expressions
Returns:dictionary with names of output variables and the corresponding values
Return type:dict

The function assumes (without checking) that expressions are valid and that they can be evaluated from top to bottom.

Example

Call

compute_list([('a', 'SET', (12,)),
              ('b', 'NOT', ('a',)),
              ('c', 'LSHIFT', ('a', 2)),
              ('d', 'AND', ('b', 'c'))])

returns {‘a’: 12, ‘b’: -13, ‘c’: 48, ‘d’: 48}, which corresponds to {‘a’: 12, ‘b’: ~12, ‘c’: 12 << 2, ‘d’: ~12 & (12 << 2)}.

General evauation of expressions (Grade 9)

dict_expr(exprs)

Construct a dictionary from a list of expressions

Parameters:exprs (list) – a list of expressions
Returns:dictionary with names of output variables as keys and tuples with operands and arguments as values
Return type:dict

Example

Call

dict_expr([('a', 'SET', (12,)),
           ('b', 'NOT', ('a',)),
           ('c', 'LSHIFT', ('a', 2)),
           ('d', 'AND', ('b', 'c'))])

returns

{'a': ('SET', (12,)),
 'b': ('NOT', ('a', )),
 'c': ('LSHIFT', ('a', 2)),
 'd': ('AND', ('b', 'c'))}
compute(var, exprs, variables)

Return the value of a variable given a list of expressions and values

This function is similar to compute_list except that it evaluates the expressions in a different order if needed. For instance, it computes

[(‘b’, ‘SET’, (‘a’,)),
(‘a’, ‘SET’, (42, ))]

by first computing a and then b.

The function assumes that the list of expressions is valid and that each variable appears as output only once.

The function may modify the dictionary variables by adding the intermediate results, that is, the values of variables that are computed in while computing the value of the target variable var.

Parameters:
  • var (str) – the name of the variable to compute
  • exprs (dict) – a dictionary with expressions (see dict_expr)
  • variables (dict) – known variable values
Returns:

the value of variable var
Return type:

int

Examples

Call compute(‘b’, {‘b’: (‘SET’, (‘a’,)), ‘a’: (‘SET’, (42, ))}, {}) returns 42.

Call compute(‘b’, {‘b’: (‘SET’, (‘a’,))}, {‘a’: 42}) also returns 42.

compute_file(var, filename)

Return the value of a variable for the expressions in the given file.

The function is similar to compute except that it reads expressions from the file and then calls compute.

Parameters:
  • var (str) – the name of the variable to compute
  • filename (str) – file name
Returns:

the value of var
Return type:

int

Checking for computability (Grade 10)

computable(exprs)

Check whether the list of expressions is computable.

The list is not computable is some variables appear as outputs without appearing as inputs or if there are cycles, like in the following case:

[('a', 'SET', ('b',)),
 ('b', 'SET', ('c',)),
 ('c', 'SET', ('a',))

Note that cycles can also be more complicated, like in this case

[('a', 'AND', ('b', 'd')),
 ('b', 'AND', ('c', 'd')),
('c', 'LSHIFT', ('f', 2)),
('d', 'OR', ('c', 'f')),
('e', 'NOT', ('d',)),
('f', 'SET', ('g',)),
('g', 'SET', ('a',))]

where g needs a, a needs b and d, b needs c and d, c needs f and f needs g, which completes the cycle.

Parameters:exprs (list) – a list of expressions
Returns:True if expressions can be evaluated, False otherwise
Return type:bool