Java 使用前缀表示法计算数学表达式

Question

使用以下输入字符串* + 16 4 + 3 1和这些说明:

A prefix expression is where the operator comes first. For example, + 5 7 would be 12.

我能够使用当前代码成功生成 80 的预期输出，我将在下面发布该代码。然而，使用另一个输入字符串 * + 16 * + 16 4 + 3 1 + 3 1 我的输出是 576，预计是 384。我不太确定我哪里出了问题我的算法。

public class QueueUtils {

    public static Queue<String> build(String line) {
        Queue<String> queue = new LinkedList<>();
        Scanner scanner = new Scanner(line);
        while (scanner.hasNext())
        {
            String token = scanner.next();
            queue.add(token);
        }
        return queue;
    }

    public static int eval(Queue<String> s)
    {
        List<String> list = new ArrayList<>(s);
        List<String> operators = new ArrayList<>();
        operators.add("+");
        operators.add("-");
        operators.add("*");
        int n = eval(list, operators);
        return n;
    }

    private static Integer eval(List<String> list, List<String> operators)
    {
        for (int i = 0; i < list.size(); i++)
        {
            String current = list.get(i);
            String prev = null;
            String next = null;
            String nextNext = null;

            if (i != 0)
            {
                prev = list.get(i - 1);
            }
            if (i != list.size() - 1)
            {
                next = list.get(i + 1);
            }
            if (i < list.size() - 2)
            {
                nextNext = list.get(i + 2);
            }

            if (operators.contains(prev) && prev != null)
            {
                if (!operators.contains(current)) {
                    int a = Integer.parseInt(current);
                    if (!operators.contains(next) && next != null) {
                        int b = Integer.parseInt(next);
                        Integer result = doOperation(prev, a, b);
                        list.remove(current);
                        list.remove(next);
                        list.add(i, result.toString());
                        eval(list, operators);
                    }
                    if (next == null)
                    {
                        list.remove(prev);
                    }
                }
                else
                {
                    if (!operators.contains(next))
                    {
                        if (operators.contains(nextNext))
                        {
                            list.remove(current);
                            eval(list, operators);
                        }
                    }
                }
            }
            else
            {
                if (operators.contains(current))
                {
                    if (!operators.contains(next))
                    {
                        if (operators.contains(nextNext) || nextNext == null)
                        {
                            if (prev != null)
                            {
                                list.remove(current);
                                eval(list, operators);
                            }
                        }
                    }
                }
            }
        }

        return Integer.parseInt(list.get(0));
    }

    private static int doOperation(String operator, int a, int b)
    {
        int n = 0;
        if (operator.equals("+"))
        {
            n = a + b;
        }
        else if (operator.equals("-"))
        {
            n = a - b;
        }
        else if (operator.equals("*"))
        {
            n = a * b;
        }
        return n;
    }
}

调用代码:

public class Demo2 {
    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Enter an expression in prefix form (operator comes first)");
        String line = keyboard.nextLine();
        Queue<String> q = QueueUtils.build(line);
        int result = QueueUtils.eval(q);
        System.out.println(result);
    }
}

Answer 1

因此，为了解决这个问题，您首先需要反转您的输入(因此 * + 16 * + 16 4 + 3 1 + 3 1 将变为 1 3 + 1 3 + 4 16 + * 16 + *)，然后使用一点递归来以三个为一组进行操作。

所以

1 3 + 1 3 + 4 16 + * 16 + *
4 4 20 * 16 + *
4 [80 16 + *]  // we can't do anything with 4 4 20, so we just move on one.
4 [96 *]
4 96 *
384

代码如下:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class InputFunction {

  private int doOperation(int a, int b, String operator) throws Exception {
    int result;
    if("+".equals(operator)){
      result = a + b;
    } else if("-".equals(operator)){
      result = a - b;
    } else if("*".equals(operator)){
      result = a * b;
    } else {
      throw new Exception("Unsupported operator \"" + operator + "\"");
    }
    return result;
  }

  private List<String> evaluate(List<String> function) throws Exception {
    List<String> processed = new ArrayList<>();
    if(function.size() <= 2) {
      return function;
    } else {
      for (int i = 0; i < function.size(); i += 3) {
        String a = function.get(i);
        if ((i + 1) < function.size()) {
          String b = function.get(i + 1);
          if ((i + 2) < function.size()) {
            String c = function.get(i + 2);
            if (a.matches("\\d+") && b.matches("\\d+") && !c.matches("\\d+")) {
              processed.add(String.valueOf(doOperation(Integer.valueOf(a), Integer.valueOf(b), c)));
            } else {
              processed.add(a);
              if(c.matches("\\d+")) {
                processed.addAll(evaluate(function.subList(i + 1, function.size())));
                break;
              } else {
                processed.add(b);
                processed.add(c);
              }
            }
          } else {
            processed.add(a);
            processed.add(b);
          }
        } else {
          processed.add(a);
        }
      }
    }
    return evaluate(processed);
  }

  private void doFunction(String input) throws Exception{
    List<String> function = Arrays.asList(input.split(" "));
    Collections.reverse(function);
    System.out.println(evaluate(function));
  }

  public static void main(String ... args) {
    InputFunction inputFunction = new InputFunction();
    try {
      inputFunction.doFunction("+ + 5 5 + 5 5");
      inputFunction.doFunction("* + 16 * + 16 4 + 3 1 + 3 1");
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

}

...诚然，我没有尝试过任何带有“-”的示例，但您应该明白了。