When we write out a mathematical expression we normally we write the operators between the operands, like so: $"3+4".$ We call this an 'infix' notation $($my personal mnemonic is that the operators are in$-$between the numbers$).$

In Reverse Polish NotationLinks to an external site. the operators follow the operands, like so: $"34+".$ We call this a 'postfix' notation.

One of the nice features of postfix notation is that the order of operations is determined by the expression itself, unlike infix notation which forces you to memorize PEMDAS, etc. This is accomplished by immediately applying any operators that we see, as we read the expression from left to right.

So how do we keep track of what we should be applying the operators to$?$ By pushing operands $($numbers$)$ onto a stack as we read from left to right. That way, when we encounter an operator we can pop as many operands off the stack as we need, apply the operator to the numbers, and then push the result back onto the stack.

Here is some resources explaining Reverse Polish Notation:

Wolfram Mathworld entry on RPNLinks to an external site.

Interesting historical info plus an emphasis on not needing PEMDAS for RPNLinks to an external site.

Wikipedia entry on RPNLinks to an external site.

You can find RPN calculators for free online $($such as this oneLinks to an external site.$).$

Be warned that they don't work exactly like ours will $($they typically ask you to type a number, then press Enter, then type another number, then press Enter, then you press the $+$ key to do the addition.

Our program lets the user type in the entire expression on a single line and then evaluates the whole thing.

Still, these calculators may be useful for getting the overall idea of how RPN works.

Task:

This assignment will give you practice with the classes and interfaces that we've been examining in the Java Collections Framework, specifically the Stack class.

Here's a link to the starter file for this assignment.Download Here's a link to the starter file for this assignment.

Here's a brief explanation of how to extract the files into a folder so you can work with them on your computer.

You MUST build on the provided starter project $($you will be penalized for starting a new Java file from scratch$).$ You may find it useful to look up 'labeled continue' statements before digging into the provided starter code.

The program has been started for you $($so that you can focus more on the data structures and algorithms and less on the user interface code$).$ Your program needs to provide the RPN calculator functionality $($as described in the 'Background' section$)$ AND it needs to produce output that is the same as what's listed in the 'Example Transcript' section, below.

Notice that the program can run in one of two modes: an 'explaining' mode where it shows the user exactly how it's evaluating the expression at each step and a 'brief' mode where it just shows the end result $($without showing any intermediate steps$).$ Your program must be able to do the same.

Note that there is now a video that walks you through the sample code, giving you a high level overview of what different parts of the code are intended to doLinks to an external site..

Example Transcript

User input is listed in large, bold underlined, highlighted text.

Note that the menu options for the main menu are case INsensitive. For example, you should be able to type in upper case A or lower case a in order to choose the 'Add a new student' menu option.

IMPORTANT NOTE: If your program is given the following input exactly then your program should reproduce the following output exactly. One way to test this would be to type in all the example inputs yourself. This is a great way to test specific scenarios $($such as "Does $12+$ work correctly?"$)$ but is slow and error$-$prone for testing everything below. A much faster way is to type all the inputs into a separate text file, and then copy and paste the entire file into your terminal window. For example, if you create a new text file $($in VSCode you can do this using Control$+$N $($Command$+$N on a Mac$)),$ and then typing the following into the file:

$12+$

y

y

$12+$

n

y

$123++$

n

y

Now, any time that you want to test these inputs you can copy the entire file, run your program, and paste it into the program $($using Control$-$V or Command$-$V$,$ or using VSCode's Edit $->$ Paste menu option$)$

IMPORTANT NOTE #$2$: Your instructor will test your program by pasting all the inputs listed below into your program. For full credit your program must reproduce the following output exactly. $($And in addition, your program must of course also work correctly with any other expressions even if they're not listed in the example transcript$)$

Here's the example transcript:

RPN calculator

Supported operators: $+-*/$

Type your RPN expression in so that it can be evaluated: $12+$

Would you like me to explain how to expression is eval