moist_beetle moist_beetle - 25 days ago 12
Java Question

How to find value of prefix expression using a recursive method?

I have the following pseudocode and need to write a java method to evaluate a prefix expression:

Algorithm valueOfPrefixExpression(prefixExpression)

Input: a valid positive-integer arithmetic expression in prefix form

Return value: the value of the prefix expression

if next token is an integer

return the integer

else

Read an operator, say op

firstOperand gets valueOfPrefixExpression(remainingExpression)

secondOperand gets valueOfPrefixExpression(remainingExpression)

return firstOperand op secondOperand

endif

How can I write this method? I tried this and I think it could be right but I am getting a "missing return statement" error so I can't compile. Assume method is only called if args has 1 or more elements. (no empty arrays)

public static int prefixAlgorithm(String[] args) {
for (int i = 0; i < args.length; i++) {
if (!args[i].equals("+") && !args[i].equals("-")
&& !args[i].equals("*") && !args[i].equals("/")) {
int operand = parseInt(args[i]);
return operand;
} else {
int firstOperand = prefixAlgorithm(Arrays.copyOfRange(args, i, (args.length - 1)));
int secondOperand = prefixAlgorithm(Arrays.copyOfRange(args, i, (args.length - 1)));
if (args[i].equals("+")) {
return firstOperand + secondOperand;
} else if (args[i].equals("-")) {
return firstOperand - secondOperand;
} else if (args[i].equals("*")) {
return firstOperand * secondOperand;
} else if (args[i].equals("/")) {
return firstOperand / secondOperand;
}
}
}
}

Answer

PrefixEvaluator with input and Scanner:

import java.util.*;

public class PrefixEvaluator {
    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        System.out.println("This program evaluates prefix expressions");
        System.out.println("for operators +, -, *, / and %");
        System.out.print("expression? ");
        System.out.println("value = " + evaluate(console));
    }

    // pre : input contains a legal prefix expression
    // post: expression is consumed and the result is returned
    public static double evaluate(Scanner input) {
        if (input.hasNextDouble()) {
            return input.nextDouble();
        } else {
            String operator = input.next();
            double operand1 = evaluate(input);
            double operand2 = evaluate(input);
            return evaluate(operator, operand1, operand2);
        }
    }

    // pre : operator is one of +, -, *, / or %
    // post: returns the result of applying the given operator to
    //       the given operands
    public static double evaluate(String operator, double operand1,
                                  double operand2) {
        if (operator.equals("+")) {
            return operand1 + operand2;
        } else if (operator.equals("-")) {
            return operand1 - operand2;
        } else if (operator.equals("*")) {
            return operand1 * operand2;
        } else if (operator.equals("/")) {
            return operand1 / operand2;
        } else if (operator.equals("%")) {
            return operand1 % operand2;
        } else {
            throw new RuntimeException("illegal operator " + operator);
        }
    }
}

PrefixEvaluator with no input and queue:

import java.util.*;

public class PrefixEvaluator {
    public static void main(String[] args) {
        String input = "- * + 4 3 2 5";
        String[] expression = input.split ( " " );

        Queue<String> expressionQueue = new LinkedList<String>();

        for (String element : expression)
        {
            expressionQueue.add ( element );
        }

        System.out.println("value = " + evaluate(expressionQueue));
    }

    // pre : input contains a legal prefix expression
    // post: expression is consumed and the result is returned
    public static double evaluate(Queue <String> input) {
        if(input.peek ( ) != null && input.peek ( ).matches ( "^(-?)\\d+$" ))
        {
            return Long.parseLong ( input.poll ( ) );
        }
        else 
        {
            String operator = input.poll();
            double operand1 = evaluate(input);
            double operand2 = evaluate(input);
            return evaluate(operator, operand1, operand2);
        }
    }

    // pre : operator is one of +, -, *, / or %
    // post: returns the result of applying the given operator to
    //       the given operands
    public static double evaluate(String operator, double operand1,
                                  double operand2) {
        if (operator.equals("+")) {
            return operand1 + operand2;
        } else if (operator.equals("-")) {
            return operand1 - operand2;
        } else if (operator.equals("*")) {
            return operand1 * operand2;
        } else if (operator.equals("/")) {
            return operand1 / operand2;
        } else if (operator.equals("%")) {
            return operand1 % operand2;
        } else {
            throw new RuntimeException("illegal operator " + operator);
        }
    }
}

I/O Example:

This program evaluates prefix expressions

for operators +, -, *, / and %

expression? - * + 4 3 2 5

value = 9.0