SI221 Lab 6: Using stacks - postfix expressions!

Introduction

An arithmetical expression in postfix differs from our usual notation (which is called infix) in that the operator comes after the operands rather than in between. This is pretty clear cut for adding two numbers. For example, adding 3 and 5 is 3 + 5 in infix, and 3 5 + in postfix. Subraction, multiplication and division are similar, e.g. 3 - 5 versus 3 5 -, 3 * 5 versus 3 5 * and 3 / 5 versus 3 5 /.

Things are more interesting when several operators appear in one expression. For instance, the postfix expression 3 5 1 - *? What do you do with that? Well, the first operator is the '-', so immediately to its left are 1 then 5. Therefore, you subtract 1 from 5 and get 4. After that, you have the '*' applied to 4 and 3, and the result is 12. If you prefer a picture:

  3 5 1 - *

  3 5 1 - *

  3   4   *   =   12

So, you evaluate a postfix expression left to right, and whenever you run across an operator, you take it and the two numbers to its left, evalute than simple binary expression, and replace the whole thing with the result. Evalutating even complicated expressions is pretty easy:

3 3 7 8 - 5 + + 2 / 1 + +
3 3 7 8 - 5 + + 2 / 1 + +
3 3  -1   5 + + 2 / 1 + +
3 3  -1   5 + + 2 / 1 + +
3 3      4    + 2 / 1 + +
3 3      4    + 2 / 1 + +
3      7        2 / 1 + +
3      7        2 / 1 + +
3        3.5        1 + +
3        3.5        1 + +
3             4.5        +   =   7.5

To convince yourself that you understang postfix pretty well Evaluate the following expressions:

• 3 5 6 1 - + *
• 3 5 - 6 1 + *
• 3 5 - 6 + 1 *

Now, writing postfix expressions is a neat trick too, so see if you can translate the following expressions from infix into postfix:

• 3 * (5 + (6 - 1))
• (3 - 5) * (6 + 1)
• ((3 - 5) + 6) * 1

Now, when you've made these translations, you should see something surprising ... do you see it? Do you see any advantage in postfix versus infix? If you don't, ask your instructor, but think a little first!

Part 1: Evaluating postfix expressions

I wrote a program pfcalc that's a simple postfix calculator. You can copy the program with:

cp ~wcbrown/courses/SI221/labs/L06/pfcalc .
	

The program takes in a postfix expression involving +,-,*,/ and numbers (with decimal point if you want it), terminated by an equals sign. A typical run of the program might look like:

valiant[1] [~/]> pfcalc
Enter Postfix Expression: 4 2 7 5 - 6 + / * =
Expression Evaluates to : 1
valiant[2] [~/]> 
	

For Part 1, you're going to write the same kind of program! Now, you might be wondering how exactly to do that. Well, we've just been talking about stacks, so you might guess that they are involved. In fact, with stacks it's easy.

1. read in next symbol (i.e. number, +, -, *, / or = )
2. if symbol is a number, push it on "the stack"
3. if symbol is an operator (i.e. +,-,* or /) pop top of stack into b, pop top of stack into a, apply the operator to a and b, push the result onto "the stack"
4. if symbol is =, pop the top of the stack and print it: you're done!
5. go back to step 1.

To help you write this program, I'm providing you with the stack implementation we discussed in class (Stack.h or TradStack.h) and the following useful function: pnws. Now, get to work and write a program that evaluates postfix expressions! [HINT: remember that cin.get() reads the next character from the input stream, without skipping whitespace!]

Part 2: Add a factorial !

The four operators in your postfix calculator program are binary, meaning that they take two operands. Postfix is perfectly happy with unary operators as well. Consider the ! for factorial. In postfix, the ! is applied to whatever value is directly to it's left. For example:

• 4 ! = 24
• 2 2 + ! = 24
• 2 2 + ! 1 - = 23

Add the unary factorial operator ! to your program!

Part 3: A true calculator

Modify your program so that it's a true calculator, meaning that it evaluates more than one expression. When the program encounters an =, it will pop the top of the stack, print that value, push it back on, and keep reading! The letter q should signal the end of the program. A typical run of the program might look like:

valiant[2] [~/]> pfcalcv2
: 2 3 + =
5
: 2 - =
3
: 4 1 + * =
15
: q
valiant[3] [~/]> 

Notice how left over values on the stack from evaluating one expression simply stay there!

Part 4: Print the stack

Modify your program so that if the user types p, the contents of the stack are printed out. Note, when the printing is done, the exact same numbers should be on the stack, in the same order! Printing of the stack can be either left to right or right to left as you choose, but a # should indicate the bottom of the stack. A typical run of the program might look like:

valiant[3] [~/]> pfcalcv3
: 2 3 5 6 - =
-1
: p
#2 3 -1 
: + =
2
: p
#2 2 
: * =
4
: p
#4 
: q
valiant[4] [~/]>