**Objective:** The goal of this assignment is to practice the
use of stacks in compiling.

**Assignment:** Write a program that, given a postfix
expression, uses stacks to compute its value. Allow your
program to take arbitrary non-negative one-digit integers,
blank spaces between numbers and/or symbols, and the factorial
symbol ! in addition to the usual arithmetic operations +, -,
*, and /, so that 23!+ (or 2 3! +) means 2 + 3! (so that the
desired value is 2 + 1
* 2 * 3 = 2 + 6 = 8).

Write down two implementations of stacks: as arrays and as linked lists, and show that your method for computing values works correctly with both implementations of stacks.

The algorithm for computing the value of an expression was described in class; it is also described, in detail, in Section 7.4 of the class textbook. Please note that since factorial is a unary operation, it needs to be treated slightly differently:

- when the computer encounters a binary operation
symbol (like +), it peeks and pops
*two*top values from the stack, performs the corresponding binary operation on these two numbers, and pushes the result back into the stack; - on
the other hand, when the computer encounters the factorial
symbol, it peeks and pops only
*one*top value from the stack, then performs the corresponding unary operation, and pushes the result back into the stack.

**For extra credit:** Write a compiler program that takes,
as inputs, usual (infix) expressions containing +, -, *, /, and
!, and uses the stacks to compute their values. The
corresponding algorithm was also given in the class and it is
also described in Section 7.4 of the textbook.

**For even more extra credit:** Write a compiler program
that allows variables in the expressions; for each variable,
your program should ask the user for the value of this
variable, and then compute the value of the corresponding
expression.