Implement a Tic Tac Toe game with a command line interface. Players should be able to take turns and undo past turns. Past turns $($called Moves$)$ will be stored in the MoveStack class, and the the tic tac toe game board will be managed by the GameState class.

MoveStack

A regular stack that stores instances of the Move structure. A Move records the coordinates of the $\text{'}$x$\text{'}$ or $\text{'}$o$\text{'}$ token placed on the game board. All past moves are stored here. The stack is required in order to be able to undo moves. In the template, you're provided with public functions. Add any private variables$/$functions as needed, but leave public function prototypes unchanged. You may use a linked list or an array to store the Moves. You will need to implement the member functions in the MoveStack.cpp file $($not provided$).$ A test driver is provided in "downloadable files".

MoveStack$()$ Initializes the stack.

~MoveStack$()$ Cleans up the dynamically allocated memory $($if any$).$ Must be defined, even if empty.

int getSize$()$ Returns the size of the stack $($number of Moves currently on the stack$).$

Move top$()$ Returns a move on top of the stack $($but does not remove it$).$

void push$($Move move$)$ Adds the move to the top of the stack.

void pop$()$ Removes a move from the top of the stack $($but does not return it$).$

Notes:

You must submit a program for grading by $11$:$59$ Friday Apr $12($worth $4$ pts$).$ It must pass $3$ of the first four automatic test cases.

Do not use a Standard Template Library class to implement MoveStack. Use an array, a dynamically allocated array, or a linked list.

GameState

The GameState class represents the current state of the game. It stores the current board in the "boardState" variable and past moves in the "moveStack" variable. The checkLastPlayerWin function returns true if the last player who moved has won the game $($this function is provided in the template file$).$ A test driver is provided in "downloadable files".

GameState$()$ Initializes the board to all underscore characters $(\text{'}\_\text{'}).$

int getCurrentPlayer$()$ Return the player that has to make the next turn. Hint: use the size of the stack to determine who's move it is$.$ Extra hint: odd$/$even$.$

int addMove$($Move move$)$ Updates the state of the board and stack of the past moves given a move of the current player. If the turn is invalid $($the target position is not empty$)$ it returns $-1.$ If all positions are filled, it returns $0.$ If the move was successfully done and there are moves available, it returns $1.$ Hint: use the size of the stack to determine if all positions are filled.

bool undoLast$()$ Undoes the last turn by changing the board state to the previous one and removing the last move from the stack. Returns true if the move was removed, false if there are no moves to undo.

void displayBoardState$($std::ostream& out$)$ Prints the board state to the "out" stream.

Note: checkLastPlayerWin uses this syntax: c $?$ x : y$.$ If you are curious, it is called the "conditional operator". Now you can look it up$.$

main.cpp

Contains the main game loop. Players should be able to enter their move in a format "move x y$",$ where x and y are the coordinates of the target cell. Also, players should be able to undo the previous move $($of their opponent$)$ by entering "undo". The player board should be displayed at the beginning of the game and after every valid move. After every valid move the win condition has to be checked for the last player who made the move $($checkLastPlayerWin$).$ If the win condition is reached a winner should be declared and the program should be terminated. The same goes for if the game ends in a draw.

Sample execution.

$\_\_\_$

$\_\_\_$

$\_\_\_$

Player $0$ make a turn.

move $11$

$\_\_\_$

$\_$x$\_$

$\_\_\_$

Player $1$ make a turn.

move $12$

$\_\_\_$

$\_$xo

$\_\_\_$

Player $0$ make a turn.

undo

$\_\_\_$

$\_$x$\_$

$\_\_\_$

Player $1$ make a turn.

undo

$\_\_\_$

$\_\_\_$

$\_\_\_$

Player $0$ make a turn.

undo

No moves to undo.

Player $0$ make a turn.

move $11$

$\_\_\_$

$\_$x$\_$

$\_\_\_$

Player $1$ make a turn.

move $12$

$\_\_\_$

$\_$xo

$\_\_\_$

Player $0$ make a turn.

move $22$

$\_\_\_$

$\_$xo

$\_\_$x

Player $1$ make a turn.

move $12$

Incorrect move. Please try again.

Player $1$ make a turn.

move $22$

Incorrect move. Please try again.

Player $1$ make a turn.

move $02$

$\_\_$o

$\_$xo

$\_\_$x

Player $0$ make a turn.

undo

$\_\_\_$

$\_$xo

$\_\_$x

Player $1$ make a turn.

move $00$

o$\_\_$

$\_$xo

$\_\_$x

Player $0$ make a turn.

move $20$

o$\_\_$

$\_$xo

x$\_$x

Player $1$ make a turn.

move $02$

o$\_$o

$\_$xo

x$\_$x

Player $0$ make a turn.

move $21$

o$\_$o

$\_$xo

xxx

Player $0$ won!

Here is the given gamestate.h file

#include

#include "MoveStack.h$"$

class GameState $\{$

char boardState$[3][3]$;

MoveStack moveStack;

public:

GameState$()$;

int getCurrentPlayer$()$;

int addMove$($Move move$)$;

bool undoLast$()$;

void displayBoardState$($std::ostream& out$)$;

bool checkLastPlayerWin$()$;

$\}$;

and the given movestack.h file

struct Move$\{$

int x;

int y;

Move$()\{$ x$=0$; y$=0$; $\}$

Move$($int a$,$ int b$)\{$ x$=$a$,$ y$=$b;$\}$

$\}$;

class MoveStack$\{$

private:

public:

int start;

MoveStack$()$;

~MoveStack$()$;

int getSize$()$;

Move top$()$;

void push$($Move move$)$;

void pop$()$;

$\}$;