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