java - 使用堆栈从算术表达式中删除不必要/重复的括号

Question

编写一个程序来查找表达式中重复的括号。 例如:

(( a + b ) + (( c + d ))) = a + b + c + d
(( a + b ) * (( c + d ))) = (a + b) * (c + d)

我知道的一种方法涉及以下两个步骤:

1. 将给定的中缀表达式转换为后缀表达式。
2. 将后缀转换回中缀

我不想执行从一种表示形式转换为另一种表示形式，然后再将其转换回来的整个过程。

我想使用堆栈来完成此操作，但一次完成。可能吗？

请推荐算法或分享代码。

Answer 1

您可以使用 recursive descent parser .这隐式地使用函数调用堆栈，而不是显式地使用 Java 堆栈。可以按如下方式实现:

public class Main {

    public static void main(String[] args) {
        System.out.println(new Parser("(( a + b ) + (( c + d )))").parse());
        System.out.println(new Parser("(( a + b ) * (( c + d )))").parse());
    }
}

public class Parser {
    private final static char EOF = ';';
    private String input;
    private int currPos;

    public Parser(String input) {
        this.input = input + EOF; // mark the end
        this.currPos = -1;
    }

    public String parse() throws IllegalArgumentException {
        nextToken();
        Result result = expression();
        if(currToken() != EOF) {
            throw new IllegalArgumentException("Found unexpected character '" + currToken() + "' at position " + currPos);
        }
        return result.getText();
    }

    // "expression()" handles "term" or "term + term" or "term - term"
    private Result expression() throws IllegalArgumentException {
        Result leftArg = term();

        char operator = currToken();
        if (operator != '+' && operator != '-') {
            return leftArg; // EXIT
        }
        nextToken();

        Result rightArg = term();

        if(operator == '-' && (rightArg.getOp() == '-' || rightArg.getOp() == '+')) {
            rightArg = encloseInParentheses(rightArg);
        }

        return new Result(leftArg.getText() + " " + operator + " " + rightArg.getText(), operator);
    }

    // "term()" handles "factor" or "factor * factor" or "factor / factor"
    private Result term() throws IllegalArgumentException {
        Result leftArg = factor();

        char operator = currToken();
        if (operator != '*' && operator != '/') {
            return leftArg; // EXIT
        }
        nextToken();

        Result rightArg = factor();

        if(leftArg.getOp() == '+' || leftArg.getOp() == '-') {
            leftArg = encloseInParentheses(leftArg);
        }
        if(rightArg.getOp() == '+' || rightArg.getOp() == '-' || (operator == '/' && (rightArg.getOp() == '/' || rightArg.getOp() == '*'))) {
            rightArg = encloseInParentheses(rightArg);
        }

        return new Result(leftArg.getText() + " " + operator + " " + rightArg.getText(), operator);
    }

    // "factor()" handles a "paren" or a "variable"
    private Result factor() throws IllegalArgumentException {
        Result result;
        if(currToken() == '(') {
            result = paren();
        } else if(Character.isLetter(currToken())) {
            result = variable();
        } else {
            throw new IllegalArgumentException("Expected variable or '(', found '" + currToken() + "' at position " + currPos);
        }
        return result;
    }

    // "paren()" handles an "expression" enclosed in parentheses
    // Called with currToken an opening parenthesis
    private Result paren() throws IllegalArgumentException {
        nextToken();
        Result result = expression();
        if(currToken() != ')') {
            throw new IllegalArgumentException("Expected ')', found '" + currToken() + "' at position " + currPos);
        }
        nextToken();
        return result;
    }

    // "variable()" handles a variable
    // Called with currToken a variable
    private Result variable() throws IllegalArgumentException {
        Result result = new Result(Character.toString(currToken()), ' ');
        nextToken();
        return result;
    }

    private char currToken() {
        return input.charAt(currPos);
    }

    private void nextToken() {
        if(currPos >= input.length() - 1) {
            throw new IllegalArgumentException("Unexpected end of input");
        }
        do {
            ++currPos;
        }
        while(currToken() != EOF && currToken() == ' ');
    }

    private static Result encloseInParentheses(Result result) {
        return new Result("(" + result.getText() + ")", result.getOp());
    }

    private static class Result {
        private final String text;
        private final char op;

        private Result(String text, char op) {
            this.text = text;
            this.op = op;
        }

        public String getText() {
            return text;
        }

        public char getOp() {
            return op;
        }
    }
}

如果您想使用显式堆栈，您可以将算法从递归算法转换为迭代算法，使用类似于 Result 内部类的堆栈。 事实上，Java 编译器/JVM 将每个递归算法转换为基于堆栈的算法，将局部变量放入堆栈。

但递归体面的解析器很容易被人类阅读，因此我更喜欢上面提出的解决方案。