在不评估的情况下验证后缀表达式

Question

我正在尝试设计一个程序来检查给定表达式是否是有效的后缀。我不希望它在任何时候将表达式作为过程的一部分进行评估。

我检查的每一种方法都涉及在堆叠数字之后评估表达式，然后在遇到运算符时评估表达式。这对我来说不是必需的。

我不知道如何在没有评估的情况下做到这一点

Answer 1

像这样使用正则表达式

"Somestring with postfix -text".matches("-test$");

Answer 2

你不说什么样的表达是有效的。提供适当的解决方案需要知道将使用哪些函数（基本上是它们有多少参数以及它们 return 到堆栈的参数）。

但是，假设 "usual" 是一个简单计算器的情况，这可以通过运行通过线性输入标记来完成。您只需要计算堆栈中参数的数量。如果我们知道函数的数量（参数数量）和 return 到堆栈的结果数量，则没有必要评估函数。

final static Map<String, Integer> arity = new HashMap<String, Integer>() {{
    put("*", 2);
    put("/", 2);
    put("+", 2);
    put("-", 2);
    put("neg", 1);
    put("inv", 1);
    // etc...
}};

static boolean isConstant(String token) {
    return Pattern.matches("^[0-9]+$", token);
}

static boolean valid(String postfix) {
    int availableArguments = 0;
    for(final String token: postfix.split(" +")) {
        if(isConstant(token)) {
            availableArguments += 1;
        } else if(arity.containsKey(token)) {
            final int argumentsRequired = arity.get(token);
            if(argumentsRequired > availableArguments) {
                // argument required
                return false;
            } else {
                availableArguments -= argumentsRequired;
                // not all functions must stack only one result
                availableArguments += 1;
            }
        } else {
            // wrong token
            return false;
        }
    }
    // other values than 1 could be valid
    return availableArguments == 1;
}

public static void main(String... args) {
    for(final String expr: asList("3 4 + *", "3 neg 2 + 5 * neg 4 +")) {
        System.out.printf("'%s' is %svalid%n", expr, valid(expr) ? "": "not ");
    }
}

有输出

'3 4 + *' is not valid
'3 neg 2 + 5 * neg 4 +' is valid

在不评估的情况下验证后缀表达式

Validate postfix expression without evaluation

java

postfix-mta