Rpn Calculator Java Program Without Stack Class

Introduction

Reverse Polish Notation (RPN) is a postfix notation where each operator follows its operands. Unlike infix notation (standard arithmetic notation), RPN doesn't require parentheses and can be evaluated using a simple algorithm without a stack.

In this implementation, we'll use an array to store operands and process them in the order they appear. This approach is more efficient than using a stack for simple calculations but has limitations for complex expressions.

Algorithm Explanation

The algorithm for evaluating RPN expressions without a stack is based on the following principles:

1. Initialize an array to store operands
2. Process each token in the input expression:
   • If the token is a number, add it to the array
   • If the token is an operator, remove the top two numbers from the array, apply the operator, and store the result back in the array
3. After processing all tokens, the remaining value in the array is the result

Java Implementation

The complete Java program for the RPN calculator without a stack class is shown below:

public class RPNCalculator {
    public static double evaluateRPN(String expression) {
        String[] tokens = expression.split(" ");
        double[] operands = new double[tokens.length];
        int operandIndex = 0;

        for (String token : tokens) {
            if (isNumber(token)) {
                operands[operandIndex++] = Double.parseDouble(token);
            } else {
                if (operandIndex < 2) {
                    throw new IllegalArgumentException("Invalid RPN expression");
                }
                double b = operands[--operandIndex];
                double a = operands[--operandIndex];
                double result = applyOperator(a, b, token);
                operands[operandIndex++] = result;
            }
        }

        if (operandIndex != 1) {
            throw new IllegalArgumentException("Invalid RPN expression");
        }

        return operands[0];
    }

    private static boolean isNumber(String token) {
        try {
            Double.parseDouble(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }

    private static double applyOperator(double a, double b, String operator) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/":
                if (b == 0) throw new ArithmeticException("Division by zero");
                return a / b;
            default: throw new IllegalArgumentException("Unknown operator: " + operator);
        }
    }

    public static void main(String[] args) {
        String expression = "3 4 + 2 * 5 -";
        double result = evaluateRPN(expression);
        System.out.println("Result: " + result);
    }
}

The program consists of three main methods:

1. evaluateRPN - The main method that processes the RPN expression
2. isNumber - Helper method to check if a token is a number
3. applyOperator - Applies the specified operator to two operands

Worked Example

Let's evaluate the RPN expression "3 4 + 2 * 5 -":

1. Push 3 to the array: [3]
2. Push 4 to the array: [3, 4]
3. Encounter '+': pop 4 and 3, compute 3+4=7, push 7: [7]
4. Push 2 to the array: [7, 2]
5. Encounter '*': pop 2 and 7, compute 7*2=14, push 14: [14]
6. Push 5 to the array: [14, 5]
7. Encounter '-': pop 5 and 14, compute 14-5=9, push 9: [9]

The final result is 9.