## CS 2401 Assignment #7

Due Date: Monday, November 7 or Tuesday, November 8, depending on the day of your lab.

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.