验证表达式

Question

给定一个包含运算符、函数和操作数的表达式，例如：

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

如何以编程方式验证表达式，以便任何函数都必须具有正确数量的参数？例如 abs,sin,cos 必须正好有 1 个参数，而 sum,avg,max,min 有 2 个或更多。

考虑到每个参数本身可以是一个非常复杂的表达式，以编程方式确定这一点似乎很重要。我已经编写了一个词法分词器 (lexer)，并且我已经设法将表达式转换为 postfix/RPN。（即：2 3 max 3 / 3.1415 * sin 2 +）。我离解决方案还差得很远。

我希望能有一些代码或伪代码指导我从头开始编写一些东西。 Java 会很棒。

下面是我的词法分析器代码：

    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

你要么需要在调车场检测到它。一个快速的想法是在运算符堆栈上，对每个元素保持一个计数器。计算检测到的逗号数。然后在右括号或末尾检查每个函数条目的参数数量。

另一种方法可能是保留更多信息作为您的 RPN 的附加值。例如保留逗号，然后您将得到：

2 , 3 max 3 / 3.1415 * sin 2 +

在处理一个函数时，它不仅必须从堆栈中获取值，还必须获取正确数量的 ,。稍后会出现太多。

虽然像这样，但我担心这种方式有一些边缘情况；所以可能更好的是一个精确的解析器。

sin(1,2) * max (3)

1 , 2 sin 3 max *

Answer 2

你想要做的是实现一个精确的解析器，它知道你的语言的确切语法（包括 "how many operators does a function have"）。

编写这样的表达式解析器很容易。参见

验证表达式

Validating an expression

java

parsing

expression

lexical-analysis