Validating an expression

Question

Given an expression with operators, functions, and operands, such as:

2 + sin ( max ( 2, 3 ) / 3 * 3.1415 )

How can I programmatically validate the expression, such that any functions must have the correct number of parameters? For example abs,sin,cos must have exactly 1 parameter, whereas sum,avg,max,min have 2 or more.

Given that each parameter can itself be a very complicated expression, it seems non-trivial to programmatically determine this. I have already written a lexical tokenizer (lexer), and I've managed to convert the expression to postfix/RPN. (Which is: 2 3 max 3 / 3.1415 * sin 2 +). I am still no closer to a solution.

I would appreciate some code or pseudocode that will guide me in writing something from scratch. Java would be great.

Below is my lexer code:

    public static List<Token> shunt(List<Token> tokens) throws Exception {
    List<Token> rpn = new ArrayList<Token>();
    Iterator<Token> it = tokens.iterator();
    Stack<Token> stack = new Stack<Token>();
    while (it.hasNext()) {
        Token token = it.next();
        if (Type.NUMBER.equals(token.type))
            rpn.add(token);
        if (Type.FUNCTION.equals(token.type) || Type.LPAREN.equals(token.type)) 
            stack.push(token);
        if (Type.COMMA.equals(token.type)) {
            while (!stack.isEmpty() && !Type.LPAREN.equals(stack.peek().type))
                rpn.add(stack.pop());
            if (stack.isEmpty()) 
                throw new Exception("Missing left parenthesis!");
        }
        if (Type.OPERATOR.equals(token.type)) {
            while (!stack.isEmpty() && Type.OPERATOR.equals(stack.peek().type))
                rpn.add(stack.pop());
            stack.add(token);
        }
        if (Type.RPAREN.equals(token.type)) {
            while (!stack.isEmpty() && !Type.LPAREN.equals(stack.peek().type))
                rpn.add(stack.pop());
            if (stack.isEmpty()) 
                throw new Exception("Missing left parenthesis!");
            stack.pop();
            if (!stack.isEmpty() && Type.FUNCTION.equals(stack.peek().type))
                rpn.add(stack.pop());
        }
    }
    while (!stack.isEmpty()) {
        if (Type.LPAREN.equals(stack.peek().type) || Type.RPAREN.equals(stack.peek().type))
            throw new Exception("Mismatched parenthesis!");
        rpn.add(stack.pop());
    }

    return rpn;
}

Answer 1

You either need to detect it during the Shunting Yard. A quick idea would be on the operator stack, keep a counter against each element. Count the number of commas detected. Then either on a close parenthesis or just at the end, check the number of arguments against each function entry.

An alternative might be to keep some more of the information as additional values for your RPN. e.g. keep the commas, you then get:

2 , 3 max 3 / 3.1415 * sin 2 +

When processing a function, it not only must eat values from the stack it must also eat the correct number of ,s. And too many will show itself later on.

I fear that way has some edge cases though like this; so probably better a precise parser.

sin(1,2) * max (3)

1 , 2 sin 3 max *

Answer 2

What you want to do is implement a precise parser, that knows the exact syntax of your language (that includes "how many operators does a function have").

It is easy to write such a parser for expressions. See https://stackoverflow.com/a/2336769/120163