Проверка выражения

Question

Учитывая выражения с операторами, функции и операндами, такие как:

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

Как можно программно проверить выражение, таким образом, что любые функции должны иметь правильное количество параметров? Например, abs, sin, cos должен иметь ровно один параметр, тогда как сумма, 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

То, что вы хотите сделать, это осуществить точный анализатор, который знает точный синтаксис языка (который включает в себя «сколько операторов делает функция есть»).

Легко написать такой синтаксический разбор для выражений. См. https://stackoverflow.com/a/2336769/120163