Using Stacks - Postfix Expressions!

Introduction

In the 1920's Polish Logician Jan Łukasiewicz developed a method of mathematical notation where an operand follows its operators. This became known as Reverse Polish Notation (due to Lukasiewicz's nationality), or "RPN" for short. It is also commonly known as "postfix" notation. An arithmetic 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. Subtraction, 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, what about 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, evaluate than simple binary expression, and replace the whole thing with the result. Evaluating 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 understand postfix pretty well, evaluate the following expressions:

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

Now, writing postfix expressions from infix takes a bit more work, but 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? I'll give you a hint: the folks as Hewlett-Packard thought it was so great that they used it in every hand-held calculator they sold until 1977! You can read more about it here: History of RPN implementations

Part 1 (60 points): Evaluating postfix expressions

Download the simple postfix program pfcalc from here: pfcalc. You'll need to ensure that the file is executable, and that the browser didn't add a file extension when it was downloaded. You can run the program using the terminal like this:

chmod 700 pfcalc  <---- if you get a permission error
./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:

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. Here's the pseudocode:

Initialize a stack of doubles
Prompt for postfix expression
While there is more input to read
  If the input is an operator
    Read the next character
    Pop two numbers off the stack, minding proper order
    Conduct the proper operation
    Push result onto the stack
  Else read the next input and push it onto the stack
Pop and print the answer

To assist, following are provided:

Start with starter.cpp that has the above pseudocode included and the pnws function for you to use. Now, get to work and write a program that evaluates postfix expressions! Name your file pfcalc.cpp

HINT: remember that cin.get() reads the next character from the input stream, without skipping whitespace!

But wait! There's more! Add the functionality demonstrated below to your program and get a 10 point BONUS!!

Part 2 (20 points): A true calculator

Modify your program in a new file named pfcalc2.cpp 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:

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

Part 3 (20 points): Print the stack

Modify your program again in a new file named pfcalc3.cpp 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! When printing the stack a # should indicate the bottom of the stack with the contents of the stack appearing to the right of the # as shown below. A typical run of the program might look like:

Deliverables

Due: 2359, Monday 08 Oct 2018

Submit your three cpp files (pfcalc.cpp, pfcalc2.cpp, and pfcalc3.cpp) via the the submisison website: submit.cs.usna.edu. 

~/bin/submit -c=SI221 -p=Lab05 pfcalc.cpp pfcalc2.cpp pfcalc3.cpp

Do NOT submit any .o or executable files.