Validate postfix expression without evaluation

Question

I am trying to design a program that just checks whether a given expression is a valid postfix one or not. I do not want this to evaluate the expression as a part of the process at any point.

Every approach that I checked involves evaluating the expression after stacking the numbers and then when an operator is encountered. This is not necessary for me.

I am clueless about how to do this without evaluation

Answer 1

You don't say what kind of expressions are valid. Providing an adequate solution requires knowing which functions will be used (basically what arity they have and how many arguments they return to the stack).

However, assuming the "usual" case of a simple calculator, this can be done by running through the input tokens linearly. You only need to count the number of arguments in the stack. It is not necessary to evaluate the functions if we know their arity (number of arguments) and number of results that return to the stack.

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 ");
    }
}

With output

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