EECS 12 Summer 2006 Homework 8

General Instructions

Please place your programs in seperate files named as described in the problem. Improperly named programs will not count. Turn in your files by placing them in the dropbox. NOTE THAT THERE IS A FIRM DEADLINE FOR THIS HOMEOWRK!!!!

Grading

Correct	80%
Commented	10%
Attempted	10%

Problems

Problem 0: 50 points

Implement a doubly linked list with some functions to operate on them.

• (head, success) = insertAfter(item, afterItem, head). This function takes a doubly linked list head node head and attempts to insert the given item after the first occurance of afterItem. It returns the new head node head as well as a boolean that is True if the operation was successful and False otherwise. Note: In this function, the new head node should be the same as the old head node; in the other functions this will not always be the case.
• (head, success) = insertBefore(item, beforeItem, head). This function takes a doubly linked list head node head and attempts to insert the given item before the first occurance of beforeItem. It returns the new head node head as well as a boolean that is True if the operation was successful and False otherwise.
• (head, success) = remove(item, head). This function takes a doubly linked list head node head and attempts to remove the given item. It returns the new head as well as a boolean that is True if the operation was successful and False otherwise.

Problem 1: 50 points

Write a program called postfix.py that calculates postfix expressions interactively, using a continuous stack and variables.

• Include the standard operations + - * /.
• Include the additional operation =, which sets a variable name equal to a value (see examples for details).
• In the context of this program, a continuous stack means that the stack is not emptied between the evaluation of expressions. Things stay on the stack if you do not consume them.
• Users should be able to leave out whitespace between symbols and and numbers and letters. 3 4+ should be the same as 3 4 +. Note that numbers and letters themselves are deliniated by whitespace, because 34 is not the same as 3 4.
• Use re.split to split the user's input (hint: split on things that are not letters or numbers), and then use a list comprehension to remove all whitespace. Hint: string.whitespace.
• You can use the stack class that we defined in class, or you can just use a standard python list as a stack.
• This calculator does NOT operate on lists, so you do not need to worry about things like mapping. If you want to make an operation dictionary (which you should), then all functions in the dictionary should take two arguments: the stack and the variable dictionary.
• The only global variable should be the operation dictionary.
• The main loop should print out the whole stack and variable list each time
• Because both numbers and variable names can be on the stack, you should probably also write a function that will check an operand to see if it is a string, and then look it up in the variable list if it is a string.
• Make special note of the order of the operands for - and /
• Convert everything that is not a variable name into a float before you even put it on the stack. Never place an operation on the stack.
• Your processing loop should look like this:

  
  Get and split user input
  Filter out whitespace (can be combined with previous step)
  If user input starts with 'quit', then break out of the loop
  For each item in the user input:
     if it is an operation, do the operation
     if it starts a letter, push the item on the stack (it is a variable name)
     otherwise, convert it to a float and push it on the stack
  Print the stack
  Print the variable dictionary
  

• Python will throw an IndexError if you pop an empty stack. Catch this exception and tell the user that the stack is empty.
• Because of our parsing rules, you cannot enter negative numbers. This is okay. If the user wants a negative number, they can still get it... 0 19 - should give -19.

Below is an example run of the program

> 3 4 5 + *
[27.0]
{}
> 4 5 + 3 *
[27.0, 27.0]
{}
> apple =
[27.0]
{'apple': 27.0}
> 1 + bannana =
[]
{'bannana': 28.0, 'apple': 27.0}
> 5 apple +
[32.0]
{'bannana': 28.0, 'apple': 27.0}
> 32 /
[1.0]
{'bannana': 28.0, 'apple': 27.0}
> 7 orange = 1 2 3*apple-
[1.0, 1.0, -21.0]
{'bannana': 28.0, 'orange': 7.0, 'apple': 27.0}
> ++
[-19.0]
{'bannana': 28.0, 'orange': 7.0, 'apple': 27.0}
> 0 19 -
[-19.0, -19.0]
{'bannana': 28.0, 'orange': 7.0, 'apple': 27.0}
> +
[-38.0]
{'bannana': 28.0, 'orange': 7.0, 'apple': 27.0}
> +
Stack is empty!
[]
{'bannana': 28.0, 'orange': 7.0, 'apple': 27.0}
> quit