You will write a program to evaluate and display a prefix expression using a stack, not recursion. C$++$ Data Abstration Soluction.

It is easy to evaluate a prefix expression starting at the end, saving each operand until you encounter an operator, which will operate on the two operands you last encountered $($saved$).$

You will use the stack ADT provided with the assignment. This ADT was covered in Chapter $7.$ The files are attached to this assignment.

The expression will contain single integer values and only binary operators $+,-,/,*.$

Your main should ask the user to enter a valid prefix expression. You can assume they will enter a valid prefix expression that follows the restrictions. Your main should pass the expression to a function that evaluates and returns the calculated value. The main should display a message for the user.

Ex$.$ If the user enters $+*234$ the result should be $10$

If the user enters $*/638$ the result should be $16$

Write your program using a sentinel controlled while loop to continue to read and evaluate prefix expressions until the user enters the sentinel$.$ You pick the sentinel value.

C$++$ Data Abstration Soluction.

Sample input:

$+-86*34=14$

$+-*3481=5$

$+3*98=75$

$/+-*5433+23=4$

###########ArrayStack.cpp

@file ArrayStack.cpp $*/$

#include $//$ For assert

#include "ArrayStack.h$"//$ Header file

template

ArrayStack::ArrayStack$()$ : top$(-1)$

$\{$

$\}//$ end default constructor

$//$ Copy constructor and destructor are supplied by the compiler

template

bool ArrayStack::isEmpty$()$ const

$\{$

return top $<0$;

$\}//$ end isEmpty

template

bool ArrayStack::push$($const ItemType& newEntry$)$

$\{$

bool result $=$ false;

if $($top $<$ MAX$\_$STACK $-1)//$ Does stack have room for newEntry?

$\{$

top$++$;

items$[$top$]=$ newEntry;

result $=$ true;

$\}//$ end if

return result;

$\}//$ end push

template

bool ArrayStack::pop$()$

$\{$

bool result $=$ false;

if $(!$isEmpty$())$

$\{$

top$--$;

result $=$ true;

$\}//$ end if

return result;

$\}//$ end pop

template

ItemType ArrayStack::peek$()$ const

$\{$

$//$assert$(!$isEmpty$())$; $//$ Enforce precondition

$//$ Stack is not empty; return top

ItemType value;

if $(!$isEmpty$())$

value $=$ items$[$top$]$;

return value;

$\}//$ end peek

$//$ End of implementation file.

###########ArrayStack.cpp

##########ArrayStack.h

@file ArrayStack.h $*/$

#ifndef ARRAY$\_$STACK$\_$

#define ARRAY$\_$STACK$\_$

#include "StackInterface.h$"$

const int MAX$\_$STACK $=20$;

template

class ArrayStack : public StackInterface

$\{$

private:

ItemType items$[$MAX$\_$STACK$]$; $//$ Array of stack items

int top; $//$ Index to top of stack

public:

ArrayStack$()$; $//$ Default constructor

bool isEmpty$()$ const;

bool push$($const ItemType& newEntry$)$;

bool pop$()$;

ItemType peek$()$ const;

$\}$; $//$ end ArrayStack

#include "ArrayStack.cpp$"$

#endif

##########ArrayStack.h

#########StackInterface.h

$/**$ @file StackInterface.h $*/$

#ifndef STACK$\_$INTERFACE$\_$

#define STACK$\_$INTERFACE$\_$

template

class StackInterface

$\{$

public:

$/**$ Sees whether this stack is empty.

@return True if the stack is empty, or false if not. $*/$

virtual bool isEmpty$()$ const $=0$;

$/**$ Adds a new entry to the top of this stack.

@post If the operation was successful, newEntry is at the top of the stack.

@param newEntry The object to be added as a new entry.

@return True if the addition is successful or false if not. $*/$

virtual bool push$($const ItemType& newEntry$)=0$;

$/**$ Removes the top of this stack.

@post If the operation was successful, the top of the stack

has been removed.

@return True if the removal is successful or false if not. $*/$

virtual bool pop$()=0$;

$/**$ Returns the top of this stack.

@pre The stack is not empty.

@post The top of the stack has been returned, and

the stack is unchanged.

@return The top of the stack. $*/$

virtual ItemType peek$()$ const $=0$;

$/**$ Destroys object and frees memory allocated by object. $*/$

virtual ~StackInterface$()\{\}$

$\}$; $//$ end StackInterface

#endif

#########StackInterface.h