CS 2401 Assignment #7

Due Date: Friday, July 20, 2012.

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 23 = 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:

At the end of the input string, the remaining number is popped from the stack and returned as the desired value of the original expression.

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.