java如何使用递归方法查找前缀表达式的值？

Question

我有以下伪代码，需要编写一个java方法来计算前缀表达式：

prefixExpression（prefixExpression）的算法值
输入：前缀形式的有效正整数算术表达式
返回值：前缀表达式的值

如果下一个标记是整数
返回整数
否则
读一个操作符，说op
第一个操作数获取prefixexpression（remainingExpression）的值
第二个操作数获取Prefixexpression（remainingExpression）的值
返回第一个操作数操作第二个操作数
恩迪夫

如何编写此方法？我尝试了这个，我认为它可能是正确的，但我得到了一个“缺少返回语句”错误，所以我无法编译。假设仅当args有1个或多个元素时才调用方法。（无空数组）

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 1

您的编译问题是因为您没有从该方法得到保证的返回。如果arg[i]不是整个数组所需的四个字符之一，则只需从函数的底部运行

您可能认为输入将始终符合预期，但编译器知道最好不要相信人类。：-）

Answer 2

带输入和扫描程序的前缀赋值器：

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);
        }
    }
}

不带输入和队列的前缀赋值器：

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示例：

This program evaluates prefix expressions

for operators +, -, *, / and %

expression? - * + 4 3 2 5

value = 9.0

文档：

队列：Queue (Java Platform SE 7 )

模式：Pattern (Java Platform SE 7 )