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

Background

The problem description below is based on one of the easier problems at the 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.

    #!/usr/bin/python3

    import sys

    stack = []

    def process(line):
        stack.append(int(line))
    def test_push():
        process("1")
        process("2")
        assert stack == [1,2]

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 == [3]

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

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

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

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 == [3]

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

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

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

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 == [4]

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.

    elif line == "print":
        return int(stack[-1])
    def test_print():
        process("clear")
        process("3")
        process("4")
        retv=process("print")
        otherv=process("+")
        assert retv == 4
        assert otherv == None
        assert stack == [7]

Some things to note

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 prints)

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) == [7]

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

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) == [12]

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) == [5]

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]

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.