Recursive prefix parser factorial Java

I recently started learning java in uni and a task we had to do is to understand recursion and add factorial function to this Polish notation code. I have tried various methods, and this is the latest one:

public class PolishNotation {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.println("Please enter the operators");
            System.out.println("for operators +, -, *, and !");
            System.out.println("Leave spaces between all operators and digits");
            System.out.print("expression: ");
            System.out.println("value = " + evaluateEXP(scanner));
        }
    }

    //input contains the expression user has entered
    public static int evaluateEXP(Scanner scanner) {
        //checks if there is another digit after current one
        //allows expression to be looked at from right to left
        if (scanner.hasNextInt())
            return scanner.nextInt();

        //if there is another digit after current one then
        //operands and operators are established
        char operator = scanner.next().charAt(0);
        int operand1 = evaluateEXP(scanner);
        int operand2 = evaluateEXP(scanner);
        return evaluateOP(operator, operand1, operand2);
    }

    //operator has to be one of +, - , * or ! otherwise error is given
    private static int evaluateOP(char operator, int operand1, int operand2) {
        if (operator == '+')
            return operand1 + operand2;
        if (operator == '-')
            return operand1 - operand2;
        if (operator == '*')
            return operand1 * operand2;
        if (operator == '/')
            return operand1 / operand2;
        if (operator == '!')
            //if ! used then uses factorial method
            return factorial(operand1);
        //RunTimeException allows to return an error string in a int "type" method
        throw new RuntimeException("operator not allowed for this language");
    }

    private static int factorial(int n) {
        return n == 1 ? 1 : factorial(n - 1) * n;
    }

}

There are no errors, but a result does not come out so I am guessing that it's stuck on an infinite loop. The idea of this code is that if I did ! + 3 2 it should do !5 so return 120 and I cannot use while or for loops. The rest of the operands work, it's just the factorial that doesn't.

3 answers

  • answered 2018-10-11 19:38 RedDeckWins

    public static int factorial(int n) {
        if(n==1){
            return 1;
        }
        // the next line is wrong.  I've removed a set of parentheses to make it more clear 
        int output =  factorial((n-1)*n);
        return output;
    }
    

    If would highly recommend running through your code in your head. If I pass 2 to your method what value is factorial() called with recursively? Hint: it isn't 1.

  • answered 2018-10-11 19:56 oleg.cherednik

    public static long fact(int n) {
        return n == 0 ? 1L : n * fact(n - 1);
    }
    

    It is better to use long as return type, because 17! is greater than Integer.MAX_VALUE

  • answered 2018-10-11 21:04 Max Vollmer

    The problem is that in evaluateEXP your code always expects 2 operands. However ! only takes one operand, so if you enter something like ! 5 it will wait for more input.

    The solution is to check if the operator is unary or binary, and only accept one operand if it is unary. Here are a few ways to refactor your code to achieve this:

    1) Check the operator in the evaluateEXP method and only get the second operand if it's binary (in your case not !):

    //input contains the expression user has entered
    public static int evaluateEXP(Scanner scanner) {
        //checks if there is another digit after current one
        //allows expression to be looked at from right to left
        if (scanner.hasNextInt())
            return scanner.nextInt();
    
        //if there is another digit after current one then
        //operands and operators are established
        char operator = scanner.next().charAt(0);
        int operand1 = evaluateEXP(scanner);
        int operand2 = 0;
        //only take second operand if operator is not unary
        if (operator != '!') {
            operand2 = evaluateEXP(scanner);
        }
        return evaluateOP(operator, operand1, operand2);
    }
    

    2) Pass the scanner to evaluateOP and let it take the operands directly:

    //input contains the expression user has entered
    public static int evaluateEXP(Scanner scanner) {
        //checks if there is another digit after current one
        //allows expression to be looked at from right to left
        if (scanner.hasNextInt())
            return scanner.nextInt();
    
        //if there is another digit after current one then
        //operands and operators are established
        char operator = scanner.next().charAt(0);
        return evaluateOP(operator, scanner);
    }
    
    //operator has to be one of +, - , * or ! otherwise error is given
    private static int evaluateOP(char operator, Scanner scanner) {
        if (operator == '+')
            return evaluateEXP(scanner) + evaluateEXP(scanner);
        if (operator == '-')
            return evaluateEXP(scanner) - evaluateEXP(scanner);
        if (operator == '*')
            return evaluateEXP(scanner) * evaluateEXP(scanner);
        if (operator == '/')
            return evaluateEXP(scanner) / evaluateEXP(scanner);
        if (operator == '!')
            //if ! used then uses factorial method
            return factorial(evaluateEXP(scanner));
        //RunTimeException allows to return an error string in a int "type" method
        throw new RuntimeException("operator not allowed for this language");
    }
    

    3) Building up on the 2nd solution you could also merge the 2 methods as they are so closely linked anyways:

    //input contains the expression user has entered
    public static int evaluateEXP(Scanner scanner) {
        //checks if there is another digit after current one
        //allows expression to be looked at from right to left
        if (scanner.hasNextInt())
            return scanner.nextInt();
    
        //if there is another digit after current one then
        //operands and operators are established
        char operator = scanner.next().charAt(0);
    
        if (operator == '+')
            return evaluateEXP(scanner) + evaluateEXP(scanner);
        if (operator == '-')
            return evaluateEXP(scanner) - evaluateEXP(scanner);
        if (operator == '*')
            return evaluateEXP(scanner) * evaluateEXP(scanner);
        if (operator == '/')
            return evaluateEXP(scanner) / evaluateEXP(scanner);
        if (operator == '!')
            //if ! used then uses factorial method
            return factorial(evaluateEXP(scanner));
        //RunTimeException allows to return an error string in a int "type" method
        throw new RuntimeException("operator not allowed for this language");
    }