**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 power
function symbol ^ in addition to the usual arithmetic
operations +, -, *, and /, so that 23^ (or 2 3 ^) means
2^{3} = 8, and 34-2^ means (3 - 4)^{2} =
(-1)^{2} = 1.

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:

- we start with an empty stack; then, it reads the string symbol-by-symbol;
- when the computer sees a number, it pushes this number into the stack;
- when the computer encounters an operation symbol, it pops two top values from the stack, performs the corresponding operation on these two numbers, and pushes the result back into the stack.

**For extra credit:** Write a compiler program that allows
variables in the postfix 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.