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

Question

编写一个程序,用于在表达式中查找重复的括号.例如 :

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

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

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

我不想完成从一个表示转换为另一个表示的整个过程,然后将其转换回来.

我想使用堆栈,但只需一次通过.可能吗 ？

请建议算法或共享代码.

Answer 1

您可以使用递归下降解析器.这隐式使用函数调用堆栈,但不显式使用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将每个递归算法转换为基于堆栈的算法,将局部变量放入堆栈.

但递归正常的解析器很容易被人类读取,因此我更喜欢上面提到的解决方案.