Using PYTHON:

Part 1:

For this part of the assignment, you will write a class (Stack) that implements all of the stack operations described in the lectures. Those operations are provided, below:

top(): Returns the top of the stack

pop(): Removes and returns the top of the stack

push(): Places a new element on top of the stack

isEmpty(): Returns True if the stack is empty

Use the following code to test your stack:

 stack = Stack() 

 print('isEmpty():', stack.isEmpty()) print('empty:', stack) stack.push(1) print('after push(1):', stack) print('isEmpty():', stack.isEmpty()) stack.push(10) 

 print('after push(10):', stack) print('pop():', stack.pop()) print('after pop():', stack) stack.push(2) 

 print('after push(2):', stack) stack.push(3) print('after push(3):', stack) stack.push(4) 

 print('after push(4):', stack) print('pop():', stack.pop()) print('after pop():', stack) print('pop():', stack.pop()) print('after pop():', stack) print('pop():', stack.pop()) print('after pop():', stack) print('pop():', stack.pop()) print('after pop():', stack) print('isEmpty():', stack.isEmpty()) 

Part 2:

For this part of the assignment, you will write a function (isPalindrome) that uses a stack to check if a string is a palindrome. The function takes just one argument, the string to check. The function returns True if the string is a palindrome, False otherwise. The basic algorithm will work like this:

let n be the length of the string for each of the first n/2 characters in the string 

 push the character onto the stack if n is odd, skip the character at n/2+1 (this is in the middle) for each character on the stack 

pop the character off the stack compare each character popped to the next character in the string if any do not match, the string is not a palindrome

Part 3:

For this part of the assignment, you will write a function (calculateRPN) that uses a stack to calculate the result of an expression in Reverse Polish Notation (RPN) (also called Post x notation). Reverse Polish Notation is described on the following Wiki page:

http://en.wikipedia.org/wiki/Reverse_Polish_notation 

Basically, for a binary operator (an operator that takes two arguments, called operands), the operands come rst, then the operator. Operands can, themselves, be RPN expressions. One advantage to RPN is that no brackets are required to ensure proper order of operations.

You can assume that the RPN expression contains only operators and numbers. The numbers, in our example, will be integers. Your function will take a single string as argument, and will return an integer (the result of the expression). You must support the following operators:

+: addition

-: subtraction

*: multiplication

/: division

The string argument will contain a RPN expression, with spaces between each number and/or operator. For example:

84 * 72 / + 41+ -

The statement above is equivalent to the following in x expression (and should compute to the value 30):

 ((8 * 4) + (7 / 2))  (4 + 1) 

Some functions have been provided to help you to implement this function, since you may need to determine if a string contains a valid integer value, and it is does, you may wish to convert the string into an integer value. The following functions do exactly that:

def isInteger(str): for chr in str: 

 if (chr < '0') or (chr > '9'): return False 

return True

def toInteger(str): return int(str) 

You will use your implementation of Stack to compute the result. The following is the basic algorithm you should use:

for every token (value separated by spaces): if the token is a number: 

 push the number to the stack if the token is an operator: 

 Pop two numbers off of the stack (in reverse order) Apply the operator with the two numbers as operands Push the result to the stack 

The result is the only value left on the stack