java - 将表达式反转为 Java 中的波兰表示法

Question

我想制作反向波兰表示法算法（从简单的表达式），但我的代码不起作用。谁能解释我为什么？

首先，我将 a 拆分String expression为array String[]这样：

String[] arraySymbols = expression.split(REGEX_SPLIT_EXPRESSION_BY_ONE_CHARACTER);

下一步：

private final ArrayDeque<Expression> stackExpression = new ArrayDeque<>();
private final List<String> polishNotation = new ArrayList<>();

@Override
    public List<String> interpret(String expression) {
        final String REGEX_SPLIT_EXPRESSION_BY_ONE_CHARACTER = "(?<=\\D)(?=\\d|\\D)|(?<=\\d|\\D)(?=\\D)";

        String[] arraySymbols = expression.split(REGEX_SPLIT_EXPRESSION_BY_ONE_CHARACTER);

        for(String oneSymbolFormatString: arraySymbols) {
            char oneSymbolFormatChar = oneSymbolFormatString.charAt(0);
            Expression currentExpression;

            switch (oneSymbolFormatChar) {
                case '(':
                    currentExpression = new TerminalExpressionParenthesisOpen();
                    comparePriority(currentExpression);
                    break;
                case ')':
                    currentExpression = new TerminalExpressionParenthesisClosing();
                    comparePriority(currentExpression);
                    break;
                case '+':
                    currentExpression = new TerminalExpressionPlus();
                    comparePriority(currentExpression);
                    break;
                case '-':
                    currentExpression = new TerminalExpressionMinus();
                    comparePriority(currentExpression);
                    break;
                case '*':
                    currentExpression = new TerminalExpressionMultiply();
                    comparePriority(currentExpression);
                    break;
                case '/':
                    currentExpression = new TerminalExpressionDivide();
                    comparePriority(currentExpression);
                    break;
                default:
                    polishNotation.add(oneSymbolFormatString);
            }
        }

        while (!stackExpression.isEmpty()) {
            polishNotation.add(stackExpression.pop().getName());
        }

        return polishNotation;
    }

private void comparePriority(Expression currentExpression) {
        if(stackExpression.isEmpty() | currentExpression.getName().equals(TypeExpression.PARENTHESIS_OPEN.getName())) {
            stackExpression.push(currentExpression);
        } else if(currentExpression.getName().equals(TypeExpression.PARENTHESIS_CLOSING.getName())) {
            while (true) {
                if(!stackExpression.getFirst().getName().equals(TypeExpression.PARENTHESIS_OPEN.getName())) {
                    polishNotation.add(stackExpression.pop().getName());
                } else {
                    stackExpression.pop();
                    break;
                }
            }
        } else if(stackExpression.getFirst().getPriority() >= currentExpression.getPriority()) {
            polishNotation.add(stackExpression.pop().getName());
            stackExpression.push(currentExpression);
        } else if(stackExpression.getFirst().getPriority() < currentExpression.getPriority()) {
            stackExpression.push(currentExpression);
        }
    }

它包含一个操作列表、它们的名称、名称和优先级：

public enum TypeExpression {
    NON_TERMINAL('\0',0),
    PARENTHESIS_OPEN('(',1),
    PARENTHESIS_CLOSING(')', 4),
    MINUS('-', 2),
    PLUS('+', 2),
    DIVIDE('/', 3),
    MULTIPLY('*', 3);

    private final char name;
    private final int priority;

    public String getName() {
        return String.valueOf(this.name);
    }

    public int getPriority() {
        return this.priority;
    }

    TypeExpression(char name, int priority) {
        this.priority = priority;
        this.name = name;
    }
}

---

• 例如。对于这个表达式：

(6+10-4)/(1+1*2)+1

我的代码返回正确的结果：

[6, 10, +, 4, -, 1, 1, 2, *, +, /, 1, +]

---

• 但是对于这个表达式：

(8+2*5)/(1+3*2-4)

我的代码返回不正确的结果：

[8, 2, 5, *, +, 1, 3, 2, *, 4, -, +, /]

应该工作（正确）是：

8, 2, 5, *, +, 1, 3, 2, *, +, 4, -/

标签： javapolish-notation