UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 16

Background

The problem description below is based on one of the easier problems at the 2017 Science Atlantic programming contest. We'll work through it in smaller pieces in order to understand (at least) numbers, lists, and numeric operations from Dive Into Python 3, chapter 2.

Problem Description

Time
5 minutes
Activity
Demo / Discussion

The goal of this lab is to write a postfix (“Reverse Polish Notation”) calculator. Unlike the probably more familiar “infix” notation, in postfix notation the numbers are given first, then the desired operation.

The following example is from Wikipedia. The infix notation `((15/(7 − (1 + 1)))*3)−(2 + (1 + 1))` can be written as `15 7 1 1  +   −  / 3  *  2 1 1  +   +  −`. It can be evaluated by what Wikipedia calls the “left to right” algorithm as follows:

``````
15 7 1 1 + - / 3 * 2 1 1 + + - =
15 7     2 - / 3 * 2 1 1 + + - =
15         5 / 3 * 2 1 1 + + - =
3 3 * 2 1 1 + + - =
9 2 1 1 + + - =
9 2     2 + - =
9         4 - =
5
``````

Input

Your program will read and process lines of input one at a time, until it reads ’quit’ on a line by itself. Each line of input will either be an integer, or a string +, -, *, /, ^, `print`, `pop`, `swap`, `dup` representing an operation.

If the input is a number, your program should save it on a stack. If the input is an arithmetic operation, your program should remove the two most recently saved numbers, and replace them with the result of the operation. If before the operation, the most recently added number (i.e. the top of the stack) is b, and the second most recently added number is a, you should replace them with

operation replacement
+ a+b
- a-b
/ ⌊a / b⌋
* a*b
^ ab

The non-arithmetic operations should be implimented as follows:

 dup copy the top element of the stack print print the top element of the stack pop remove the top element of the stack swap interchange the top two elements on the stack quit Stop reading and processing input

You may assume that there will always be sufficient arguments for each operation (i.e. there is no “stack underflow”), and that no division by zero is attempted.

Output

The output should be the output from the print operations in the input (if any).

Design for test

We saw in Lab 12 and Lab 13 that retrofitting tests for existing code could be quite a lot of work. To reduce that work here we are going to develop the code and the tests at the same time.

The original specification is in some sense designed to support integration testing of the whole program by allowing the judge system to run the contestant code against known input files and checking the output. It turns out that working with `stdin` and `stdout` in pytest is a bit inconvenient, and takes us into more advanced features of Python. To avoid that, we're going to structure our code take a list of numbers operations for input, and produce a list of numbers as output. As a last step, when everything is tested, we can read and write files to and from those lists.

Numbers

Time
10 minutes
Activity
Demo / Group programming

In order to test our handling of numbers, before implimenting anything else, we resort to white box testing and examine the state of the internal data structures.

• Create a file `~/fcshome/cs2613/labs/L16/rpn.py` containing
```    #!/usr/bin/python3

import sys

stack = []

def process(line):
stack.append(int(line))
```
• Create a file `~/fcshome/cs2613/labs/L16/test_rpn.py` with the following test in it.
```    def test_push():
process("1")
process("2")
assert stack == [1,2]
```
• Add appropriate import statements to `test_rpn.py`

• Run `pytest-3`

• Run `pytest-3 --cov=rpn`

• Run `pytest-3 --cov=rpn --cov-report=term-missing`

Arithmetic

Time
20 minutes
Activity
Small groups

Use an `if / elif / else` construction to Update your implimentation of `process` to pass the following tests

```def test_plus():
process("+")
assert stack == 

def test_minus():
process("1")
process("-")
assert stack == 

def test_mult():
process("2")
process("*")
assert stack == 

def test_div():
process("2")
process("/")
assert stack == 
```

Improving robustness of the tests

Time
15 minutes
Activity
Small Groups

Observe that each test above depends on the results of the previous test. This is not really what we want for unit tests. So let's add an operation "clear" that resets the stack to empty. Hint: avoid using assignment to clear the list, as that creates odd scope related bugs.

A simple test is

```def test_clear():
process("1")
process("2")
process("clear")
assert stack == []
```

You should now be able to rewrite your arithmetic tests to the following independent tests. One could argue about whether it's better to clear the stack at the beggining of the test or the end. The beginning is a bit more defensive, since it doesn't rely on other tests doing the right thing.

```def test_plus():
process("clear")
process("1")
process("2")
process("+")
assert stack == 

def test_minus():
process("clear")
process("4")
process("2")
process("-")
assert stack == 

def test_mult():
process("clear")
process("2")
process("2")
process("*")
assert stack == 

def test_div():
process("clear")
process("4")
process("2")
process("/")
assert stack == 
```

Stack manipulation

Time
20 minutes
Activity
Small groups

Extend your `process` implimentation to pass the following tests

```def test_dup():
process("clear")
process("4")
process("2")
process("dup")
assert stack == [4,2,2]

def test_pop():
process("clear")
process("4")
process("2")
process("pop")
assert stack == 

def test_swap():
process("clear")
process("4")
process("2")
process("swap")
assert stack == [2,4]
```

Output

Time
10 minutes
Activity
Demo / Group programming

Remember that we decided not to output directly to `stdout` to aid in testing. So in place of print, let's just return a value from `process` when appropriate. Either returning a string or a number is a defensible design choice, let's go with returning a number to skip one conversion.

• Add the following code to your `process` function
```    elif line == "print":
return int(stack[-1])
```
• The new function should pass the following test:
```    def test_print():
process("clear")
process("3")
process("4")
retv=process("print")
otherv=process("+")
assert retv == 4
assert otherv == None
assert stack == 
```

Some things to note

• for better or worse, it's reasonably common to return 'None' as from python functions.
• this is more complex than a purely functional model. We are testing not only return values, but the state we left behind.

Processing lists of operations

Time
15 minutes
Activity
Small groups

Our next level of abstraction from processing indidividual operations is to process lists of operations. Complete the following definition of `process_list` (in `rpn.py`) that takes a list of operations, and returns a list of numbers (the outputs from all `print`s)

```def process_list(lines):
out = []
for line in lines:

return out;
```

An east way to generate a list of strings is to use the `split` method of a string:

```def test_list_plus():
ops ='clear 3 4 + print'.split()
assert process_list(ops) == 

def test_list_mult():
ops ='clear 3 4 * print'.split()
assert process_list(ops) == 

def test_list_combo():
ops ='clear 3 4 * print 2 + print'.split()
assert process_list(ops) == [12,14]
```

In the original programming contest version, "quit" was added to make the life of contestants easier, since detecting end of file is a bit tricking in some languages. Here, it's just one more feature we have to impliment

```def test_list_quit():
ops ='clear 3 4 * print 2 + quit print'.split()
assert process_list(ops) == 
```

With that working, you should now be able to pass the sample tests from the programming contest:

```def test_a():
ops='15 7 1 1 + - / 3 * 2 1 1 + + - print quit'.split()
assert process_list(ops) == 

def test_b():
ops='17 3 2 * print dup dup pop + 3 / print swap - 13 + 2 ^ print quit'.split()
assert process_list(ops) == [6,4,0]

def test_c():
ops='2 128 ^ 3 / -2 * print quit'.split()
assert process_list(ops) == [-226854911280625642308916404954512140970]
```
• Check the test coverage using pytest-3.

Working with files

Time
5 minutes
Activity
Demo / Group discussion

Add some variation of the following to `rpn.py` so that we can run file based tests.

```if __name__ == '__main__':
ops=[]
for line in sys.stdin:
line = line.strip()
ops.append(line)

out = process_list(ops)
for line in out:
print(line)
```

Save the following as `a.in`

```15
7
1
1
+
-
/
3
*
2
1
1
+
+
-
print
quit
```

Run the calculator

``````\$ python3 rpn.py < a.in
``````

Here's the second test

```17
3
2
*
print
dup
dup
pop
+
3
/
print
swap
-
13
+
2
^
print
quit
```

Here's the third test

```2
128
^
3
/
-2
*
print
quit
```

Verify all 3 tests against your unit tests from above.