Your task: write a calculator program that is able to process a term in Reverse

Question

Your task: write a calculator program that is able to process a term in Reverse Polish Notation (postfix notation).

RPN: in contrast to the "classic" notation of mathematical terms (infix notation), postfix notation puts the operator (e.g. +,-,*,/) behind the two operands (numbers). The infix-term "3+4" becomes "3 4 +", the term

"7*(8+9)*(4-6)" becomes "7 8 9 + * 4 6 - *". The way to process RPN terms is very simple:

? go through your term from left to right

? whenever you find an operator, apply it to the 2 operands left from it.

? replace the 2 operands and the operator in your term by the result of the operation.

? continue going right until the end.

This algorithm requires a data structure, that offers a convenient replacement. Guess which one that is: yes, a stack. Replacement of 2 operands and the operator with the result translates to: pop the operands from a stack, apply the operation, push the result. It's that simple. So here is the algorithm:

In the following, I will call operands and operators "tokens". I will assume a string that contains an RPN term. Operators/operands (tokens) are separated by space, "7 8 9 + * 4 6 - *" is an example term.

Task in detail:

? create a calculator. Input for the basic, non-bonus version is a string read from the keyboard.

? the calculator has to understand the operations: +(plus), ?-(minus), *(times), /(division), %(modulus)

? the calculator has to deal with wrong user input. If the term is not a valid RPN term, it must output "Invalid Input", and return to the user input.


thank you

Explanation / Answer

import java.util.Stack;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;

// ==============================================================
public class infix2postfix
{
    public static String[] operators = {"+", "-", "*", "/", "^"};
// --------------------------------------------------------------
    protected static int operator (String n)
    {
        for (int i = 0; i < operators.length; i++)
        {
            if (n.equals (operators[i])) { return i; }
        }
        return operators.length;
    }
// --------------------------------------------------------------
    public static float evalPostfix (String s)
    {
    String n;                            // next token
    Float f = null;            // temporary floating point object
    int i;                                    // counter for operators
    Float op1;                        // first operand
    Float op2;                        // second operand
    StringTokenizer parser = new StringTokenizer (s);
    Stack stack = new Stack();

    try
    {
        while (parser.hasMoreTokens ())
        {
            n = parser.nextToken();
            i = operator (n);
            if (i < operators.length)
            {
// Pop enough operands for the operators (exactly two in this case)
                op2 = (Float) stack.pop();
                op1 = (Float) stack.pop();
// Apply the appropriate operator to the operands
                switch (i)
                {
                    case 0:
                        f = new Float (op1.floatValue() + op2.floatValue());
                        break;
                    case 1:
                        f = new Float (op1.floatValue() - op2.floatValue());
                        break;
                    case 2:
                        f = new Float (op1.floatValue() * op2.floatValue());
                        break;
                    case 3:
                        f = new Float (op1.floatValue() / op2.floatValue());
                        break;
                    case 4:
                        f=new Float(Math.pow(op1.floatValue(),op2.floatValue()));
                        break;
                }
// Push the result
                stack.push (f);
            }
// Push the token if it's a number (operand)
            else
            {
                try
                {
                    f = new Float (n);
                    stack.push (f);
                }
                catch (NumberFormatException e)
                    { System.out.println ("Bad number"); }
            }
        }
    }    catch (NoSuchElementException e)
        { System.out.println ("Bad token"); }
   
// Pop off the result for return
    f = (Float) stack.pop();

// if stack is not empty now, expression was in error
    if (stack.empty()) { return f.floatValue(); }
    else { return 0.0f; }
    }
    public static int[] precedences = {1, 1, 2, 2, 3};
// --------------------------------------------------------------
public static String infixToPostfix (String s)
    {
    String p = "";                    // postfix expression
    String n;                            // next token
    String t;                            // token on top of stack
    Float f = null;                    // temporary floating point object
    int i;                                // counter for operators
    int j;                                // counter for operator on stack
    StringTokenizer parser = new StringTokenizer (s);
    Stack stack = new Stack();

    try
    {
        while (parser.hasMoreTokens ())
        {
            n = parser.nextToken();
            i = operator (n);
            if (i < operators.length)
            {
                while (!stack.empty())
                {
                    j = operator ((String) stack.peek());
                    if (precedences[i] <= precedences[j])
                    {
                        p = p + " " + (String) stack.pop();
                    }
                    else break;
                }
                stack.push(n);
            }
// Output the token in the postfix expression
// if it's a number (operand)
            else
            {
                try
                {
                    f = Float.valueOf (n);
                    p = p + " " + n;
                }
                catch (NumberFormatException e)
                    { System.out.println ("Bad number"); }
            }
        }
    }    catch (NoSuchElementException e)
        { System.out.println ("Bad token"); }

// after the input tokens are exhausted,
// pop off the remaining operators
    while (!stack.empty())
    {
        p = p + " " + (String) stack.pop();
    }
    return p;
}
public static void main (String[] Args)
{
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter the equation : ");
    String A = sc.nextLine();
    System.out.println (A + " = " + infixToPostfix (A));
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.