Q1. Every web browser has both a back and a forward button which allows the user to navigate to previously seen web pages. Your task is to implement this functionality using two stacks (i.e. a simulation):

The interaction with your program will be a sequence of commands, either ">", "<", or "=". The ">" and "<" tokens will be used to indicate forward and back, respectively. The "=" is to indicate a new current page. after the "=", the computer would expect a web address. You can assume the web addresses are always valid.

You will not actually have to do any web navigation and you will simply be keeping track of the current page by outputting the given address between "[" and "]".

There are a few situations you should take care to handle.

o First, if a user enters "<" or ">" without there being a previous or next page to go to, you should output a corresponding error message but allow the user to continue browsing.

o Secondly, if a user enters "<" and then a new web address, the user's previous browsing history in the ">" direction should be erased.

o For example, if a user is on "www.google.com", enters "<", and then enters "www.yahoo.com", the history of visiting "www.google.com" should be lost. This means that if the user then enters ">", this should generate an error message and not "www.google.com". This behaviour can also be seen below in the sample data. You can also test an actual web browser (specifically Firefox or Chrome) if you feel there is other ambiguity. Also, keep in mind that navigation should start with a home page which we will set as "www.cs.ualberta.ca".

o The interaction should start with the current page being www.cs.ualberta.ca

You may choose how your program receives the input.

Sample Interaction with the program. Input is in red.

[www.cs.ualberta.ca]

= www.google.com [www.google.com]

<

[www.cs.ualberta.ca]

<

< is an invalid action [www.cs.ualberta.ca]

>

[www.google.com]

=

www.yahoo.com

[www.yahoo.com]

=

www.ualberta.ca

[www.ualberta.ca]

=

www.beartracks.ualberta.ca

[www.beartracks.ualberta.ca]

>

> is an invalid action

[www.beartracks.ualberta.ca]

<

[www.ualberta.ca]

<

[www.yahoo.com]

>

[www.ualberta.ca]

<

[www.yahoo.com]

=

www.microsoft.com

[www.microsoft.com]

>

> is an invalid action

<

[www.yahoo.com]

Q2. Write a program that uses the Stack implementation given to you in stack.py to check if there is a solution to a maze. A simple maze implementation is given to you in maze.py. To solve a maze using the Stack, use the following algorithm: 1. Add the start square to the stack.

2. Repeat the following as long as the stack is not empty:

Pop a square off the stack (the current square)

If the current square is the finish square, the solution has been found

Otherwise, get the list of squares which can be moved to from the current square, and add them to the stack Maze Description:

The maze.py file has two classes: Maze and MazeSquare.

You can create a new maze by calling the constructor: Maze(file_name), where file_name is the name of a file containing a maze.

You can get the start square of the maze by calling maze.get_start_square(). This method returns a MazeSquare.

To check if a square is the finish square, call maze.is_finish_square(square), where square is a MazeSquare.

The MazeSquare class represents a single square in the Maze. Calling maze_square.get_legal_moves() returns a list of MazeSquares that can be moved to. An algorithm example is given at this link. Two mazes files are included for this exercise: solvable_maze.txt and unsolvable_maze.txt. A graphic representation of each maze is given at this link. The maze files and classes can be found at this folder.