A stack is a data structure sometimes called a LIFO structure, for “last in, first out.” A stack is.

A stack is a data structure sometimes called a LIFO structure,
for “last in, first out.” A stack is modeled by cars pulling into a driveway:
the last car in is the first car out. In a stack, only the last element stored
in the stack is accessible. Rather than use insert, remove, append, or delete,
the vocabulary associated with stack operations is

push—add an item to the stack; the last item added is the
only item accessible by the top operation.

top—return the topmost, or most recent, item pushed onto the
stack; it’s an error to request the top item of an empty stack.

pop—delete the topmost item from the stack; it’s an error to
pop an empty stack.

For example, the sequence push(3), push(4), pop, push(7),
push(8) yields the stack (3,7,8) with 8 as the topmost element on the stack.

Stacks are commonly used to implement recursion, since the
last function called is the first function that finishes when a chain of
recursive clones is called.

Write a (templated) class to implement stacks (or just
implement stacks of integers). In addition to member functions push, pop, and
top, you should implement size (returns number of elements in stack), clear
(makes a stack empty), and isEmpty (determines if the stack is empty). Use
either a vector or a linked list to store the values in the stack. Write a test
program to test your stack implementation.

After you’ve tested the Stack class, use it to evaluate
postfix expressions. A postfix expression consists of two values followed by an
operator. For example: 35+ is equal to 8. However, the values can also be
postfix expressions, so the following expression is legal.

35+48*+6*

This expression can be thought of as parenthesized, where
each parenthesized subexpression is a postfix expression.

( ( (3 5 +) (4 8 *) +) 6 * )

However, it’s easy to evaluate a postfix expression from
left to right by pushing values onto a stack. Whenever an operator (+, *, etc.)
is read, two values are popped from the stack, the operation computed on these
values, and the result pushed back onto the stack. A legal postfix expression
always leaves one number, the answer, on the stack. Postfix expressions do not
require parentheses; (6 + 3) × 2 is written in postfix as 6 3 + 2 ×. Write a
function to read a postfix expression and evaluate it using a stack.