Contents

Overview

Now that we know how easy it is to implement a stack, in this homework we'll see one way to use it. Reverse Polish Notation (RPN) is a method of performing mathematical operations like addition and subtraction. We are use to an infix notation, where the operator goes between the operands: 1 + 5. RPN uses postfix, so the operands come first, followed by the operator: 1 5 +. The nice thing about RPN is that, with the use of stacks, it's really simple to parse: 1 5 + 8 * 100 / (this is the same things as: ((1+5)*8)/100).

How does a stack help? Suppose we have a stack operands that starts off empty. As we consider each operand (i.e., number) and operator (i.e., + / - *) provided by the user from left to right, we ask: is it an operator? If not, then it must be a number. We just push it onto the stack and move on to the next input. If an input is an operator, pop off the last two numbers added to the stack and apply the operator to them and push the result on the stack (be careful here, because 5 / 6 is not the same as 6 / 5). When we reach the end, the answer should be the only thing left on the stack.

(Back to top)

Requirements

Your mission for this homework is to complete the code below. I'm giving you the code that will interact with a user, read a line of input, and split that input into strings. I am also providing a function that will convert a string to a float. Your job is to write the code that handles taking the input sequence and calculating the result using a stack. Your code should support the +, -, /, and * operators. Here's an example of what the output should look (input from the user is shown in orange):

$ ./hw4
Welcome to the RPN calculator!
Please enter an RPN expression and hit enter:
89 60 / 8 + 32 - 29 *
Answer: -652.983
Please enter an RPN expression and hit enter:
2 5 +
Answer: 7
Please enter an RPN expression and hit enter:
21 7 /
Answer: 3
Please enter an RPN expression and hit enter:
33.333 3 * 100 /
Answer: 0.99999
Please enter an RPN expression and hit enter:
quit

The code for the hw4.cpp is below, however you can download a zip file with all necessary files contained within (including hw4.cpp) from here. You should be able to compile via Sublime, or via the command line like this: g++ -o hw4 hw4.cpp.

(Back to top)

Checklist

• the code compiles (2 points)
• the program runs correctly (2 point)
• computeExpression is fully implemented (3 points)
• the code is well documented (1 point)
• the file has the header (see the style guidelines), including who you've collaborated with (1 point)
• all code follows the style guidelines (1 point)

(Back to top)

Extra credit

Extra credit will be capped at 5 points.

EC-1 (2 points)

Turn your assignment in a day early—by Sunday night at 11:59pm.

EC-2 (2 points)

Add support for two or more unary operators (like square root, ceil, and floor).

EC-3 (2 points)

Gracefully handle bad inputs rather than letting the program crash. For instance, 5 + 6 should result in an error message.

(Back to top)

Submissions

Everything should be uploaded to Canvas by the deadline posted.

(Back to top)