Due 02/05/2016 Reverse Polish Calculator! Objective: Write a program that will t
ID: 3665403 • Letter: D
Question
Due 02/05/2016
Reverse Polish Calculator!
Objective:
Write a program that will take a string, parse it, and then calculate the value in post-fix (reverse polish) notation. To understand this mostly every expression you’ve seen in math is called in-fix notation.
In-fix Example:
3 + 2
However in post-fix notation the operator is at the end of the expression.
Post-fix Example:
3 2 +
A stack is used to calculate values in post-fix notation. Numbers are pushed onto the stack, and when an operator is reached it pops off the last two numbers and then pushes the resulting value back on the stack. See these EXAMPLE SLIDES for further information.
This program must:
Calculate values using the algorithm mentioned above and in the slides for addition, subtraction, multiplication, and division (+,-,*,/)
Error message if the user tries to divide by zero
Take in a string and process each digit and operator one at a time assuming white space delimits each
Make sure to check if there’s at least two items on the stack before when an operator is encountered or else it’s not a properly formatted post-fix expression
Finish when the program reaches the end of the string and it has only one value left on the stack, then that value is popped off and returned. Otherwise it was not properly formatted
Use your own created stack and not java’s built in stack
You may use any implementation so either an array or a linked structure.
HINTS! First when you’re processing the inputted string you can use a Scanner and call the method next() to get each token. From there you can evaluate if that token is an operator, numeric value, or an error. If it’s a numeric value then you may parse that string using Integer.parseInt() to get the integer value. You may also call Integer.parseInt()in a try-catch block. If the token is not an integer an exception will be raised and should be immediately halted.
Example Dialog:
Enter a reverse polish expression or "quit" to quit
3 2 +
5
Enter a reverse polish expression or "quit" to quit
5 1 2 + 4 * + 3 -
14
Enter a reverse polish expression or "quit" to quit
2 3 4 +
This was not properly formatted
0
Enter a reverse polish expression or "quit" to quit
quit
Goodbye
Explanation / Answer
import static java.lang.System.out;
import java.util.ArrayDeque;
import java.util.Scanner;
class Stack
{
private int sizeArray;
private long[] array;
private int empty;
private int topArray;
public Stack(int mentionSize)
{
sizeArray=mentionSize;
empty=-1;
array=new long[sizeArray];
topArray=empty;
}
public int size()
{
return (topArray+1);
}
public void push(long o)
{
array[++topArray]=o;
}
public long pop()
{
return array[topArray--];
}
public boolean isEmpty()
{
return(topArray==-1);
}
public long top()
{
return array[topArray];
}
}
public class RPNCalculator {
private static Stack stack = new Stack(1000);
private RPNCalculator() {}
public static Long evaluate(String expression) {
if (!(expression.matches("[ 0-9+\-\*/%]*")) || (expression.contains("."))) {
out.println("Invalid expression: only digits and operators are allowed");
return null;
}
Scanner parser = new Scanner(expression).useDelimiter(" ");
while (parser.hasNext()) {
String next = parser.next();
if ((next.length() == 1) && (next.matches("[+\-\*/%]"))) {
if (stack.size() < 2) {
out.println("This was not properly formatted");
while(!stack.isEmpty())
{
stack.pop();
}
//stack.clear();
return null;
}
long second = stack.pop();
long first = stack.pop();
if (next.equals("+")) {stack.push(first + second);}
if (next.equals("-")) {stack.push(first - second);}
if (next.equals("*")) {stack.push(first * second);}
if (next.equals("/")) {stack.push(first / second);}
if (next.equals("%")) {stack.push(first % second);}
}
else {
if (next.matches("[+\-\*/%]+")) {
out.println("This was not properly formatted: separate values and operators with spaces.");
return null;
}
if ((next.contains("+")) || (next.contains("-")) || (next.contains("*")) || (next.contains("/")) || (next.contains("%"))) { //I couldn't get a regular expression to work.
out.println("This was not properly formatted: separate values and operators with spaces.");
while(!stack.isEmpty())
{
stack.pop();
}
//stack.clear();
return null;
}
stack.push(new Long(next));
}
}
if (stack.size() > 1) {
out.println("This was not properly formatted");
while(!stack.isEmpty())
{
stack.pop();
}
//stack.clear();
return null;
}
return stack.pop();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for (;;) {
System.out.println("Enter a reverse polish expression or "quit" to quit");
System.out.print(">> ");
String next = "";
for (;;) {
next = scanner.nextLine().trim();
if (next.equals("")) {out.print(">> ");}
else {break;}
}
if (next.equals("quit"))
{
System.out.println("Goodbye");
return;
}
Long nextEvaluate = evaluate(next);
if (nextEvaluate != null)
{
out.println(nextEvaluate);
}
System.out.print(">> ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.