Lab 10: A postfix calculator

1. Introduction

Arithmetic expressions can be written in a variety of forms, depending on the punctuation that you use and how you place operators relative to their operands. The most familiar form is known as infix notation, because you place a binary operator in between its operands. For example,

2.0 + 3.0

says to apply the operator + to the operands 2.0 and 3.0. Infix notation is actually somewhat complicated, because you have to know precendence rules, and sometimes you need parentheses. For example,

2.0 + 3.0 x 5.0

should be interpreted as

2.0 + ( 3.0 x 5.0 )

because multiplication has higher precedence than addition. (We'll use x for multiplication in this lab.)

An alternative is postfix notation, which, while unfamiliar to most people, is actually simpler to understand. (Because it was popularized my a Polish mathematician, it is often called reverse Polish notation, or RPN. In postfix notation, the operator appears after its operands. Thus

2.0 3.0 +

says to add 3.0 to 2.0. The longer expression above would be written as

2.0 3.0 5.0 x +

You may at this point be wondering how this can be simple. The trick is that all you need is a stack. As you process the input, if you get a literal (value), you simply push it onto the stack. When you encounter an operator, you pop the right number of operands from the stack and then push the result back onto the stack. When you reach the end of the expression, there should be one value on the stack, and that is the result.

Today, you will be writing a simple calculator that evaluates postfix expressions. To make it work, you will also need to write a class for a stack.

2. Seting up

I've provided a Mercurial repository that has the framework you will need. Copy that by cloning the repository in /cslab/class/csci235/lab10.

You will need to complete the class MyStack.java and write most of the class Calc.java. If you take a look at Calc.java, you will see that it is set up to take the expression as the program arguments. So, once you have it written and compiled, you should be able to evaluate expressions with commands such as

java Calc 2.0 3.0 - 4.0 x 6.0 +

Your calculator should recognize the four operators + - x /. Notice that the method evaluate() is passed an array of strings; each of those strings should be either an operator or numeric literal. The precondition for this method does not require that you do anything elegant if you are presented a bad expression.

Tips:

There is a method Double.parseDouble(String) that you can use to convert from String to double.
You probably want to write some additional methods in Calc, in order to keep evaluate() simple. Be sure to document them properly.

3. Extras

If you have time and interest, feel free to extend your calculator with additional operations. Here are some possibilities:

exponentiation
unary negation (for which you would need to use a symbol other than -).
square root

You'll find the methods for doing fancier math in the class Math.

You could also modify the main() method so that if the program is run with no command-line arguments, it goes into an interactive mode, reading values and operators from the keyboard. If you do that, you might want to add some additional operators:

clear the top item (pop it)
clear the whole stack
print the top item (you'll have to decide whether that removes it or not)
swap (to reorder the top two elements on the stack)
quit the program

4. Turn in

Prepare a typescript that shows your programs running on several expressions.

Also hand in your source files and the typescript as lab10.

Cary Gray

Last modified: Fri Mar 4 11:17:20 CST 2011