Каков алгоритм анализа выражений в нотации infix?

Рекурсивные парсеры спуска – забава писать и легко читать . Первый шаг – написать грамматику.

Возможно, это грамматика, которую вы хотите.

 expr = and_expr ('or' and_expr)* and_expr = not_expr ('and' not_expr)* not_expr = simple_expr | 'not' not_expr simple_expr = term | '(' expr ')' 

Включение этого в парсер рекурсивного спуска очень просто. Просто напишите одну функцию в нетерминале.

 def expr(): x = and_expr() while peek() == 'or': consume('or') y = and_expr() x = OR(x, y) return x def and_expr(): x = not_expr() while peek() == 'and': consume('and') y = not_expr() x = AND(x, y) return x def not_expr(): if peek() == 'not': consume('not') x = not_expr() return NOT(x) else: return simple_expr() def simple_expr(): t = peek() if t == '(': consume('(') result = expr() consume(')') return result elif is_term(t): consume(t) return TERM(t) else: raise SyntaxError("expected term or (") 

Это не полно. Вы должны предоставить немного больше кода:

• Входные функции. consume , peek и is_term – это функции, которые вы предоставляете. Они будут легко реализованы с использованием регулярных выражений. consume(s) читает следующий токен ввода и выдает ошибку, если он не соответствует s . peek() просто возвращает peek в следующем токене, не потребляя его. is_term(s) возвращает true, если s является термином.

• Функции вывода. OR , AND , NOT и TERM вызываются каждый раз, когда часть выражения успешно анализируется. Они могут делать все, что захотят.

• Функция обертки. Вместо того, чтобы просто вызывать expr напрямую, вам нужно написать небольшую функцию-обертку, которая инициализирует переменные, используемые consume и peek , затем вызывает expr и, наконец, проверяет, нет ли оставшихся входов, которые не потреблялись.

Даже при этом все еще крошечный код. В Python полная программа – 84 строки , и это включает в себя несколько тестов.

Почему бы не использовать парсер PHP?

  $terms=array('and','or','not','A','B','C','D'...); $values=array('*','+','!',1,1,0,0,1....); $expression="A and B or C and (D or F or not G)"; $expression=preg_replace($terms, $values,$expression); $expression=preg_replace('^(+|-|!|1|0)','',$expression); $result=eval($expression); ,  $terms=array('and','or','not','A','B','C','D'...); $values=array('*','+','!',1,1,0,0,1....); $expression="A and B or C and (D or F or not G)"; $expression=preg_replace($terms, $values,$expression); $expression=preg_replace('^(+|-|!|1|0)','',$expression); $result=eval($expression); 

На самом деле, это второе регулярное выражение неверно (и требуется только, если вам нужно предотвратить инъекцию кода), но вы получаете идею.

C.

Я бы пошел с парсером Пратта. Это почти похоже на рекурсивный спуск, но умнее. Порядочное объяснение Дугласа Крокфорда (славы JSLint) здесь .

Алгоритм маятникового двора Дейкстры является традиционным для перехода от infix к postfix / graph.

Я реализовал алгоритм маневрового двора, предложенный плинтом. Тем не менее, этот алгоритм просто дает вам постфиксную нотацию, так называемую обратную польскую нотацию (RNP). Вы все равно должны его оценить, но это довольно легко, как только вы получите выражение в RNP (описано здесь здесь ).

Код ниже может не быть хорошим PHP-стилем, мои знания PHP несколько ограничены. Этого должно быть достаточно, чтобы получить эту идею.

 $operators = array("and", "or", "not"); $num_operands = array("and" => 2, "or" => 2, "not" => 1); $parenthesis = array("(", ")"); function is_operator($token) { global $operators; return in_array($token, $operators); } function is_right_parenthesis($token) { global $parenthesis; return $token == $parenthesis[1]; } function is_left_parenthesis($token) { global $parenthesis; return $token == $parenthesis[0]; } function is_parenthesis($token) { return is_right_parenthesis($token) || is_left_parenthesis($token); } // check whether the precedence if $a is less than or equal to that of $b function is_precedence_less_or_equal($a, $b) { // "not" always comes first if ($b == "not") return true; if ($a == "not") return false; if ($a == "or" and $b == "and") return true; if ($a == "and" and $b == "or") return false; // otherwise they're equal return true; } function shunting_yard($input_tokens) { $stack = array(); $output_queue = array(); foreach ($input_tokens as $token) { if (is_operator($token)) { while (is_operator($stack[count($stack)-1]) && is_precedence_less_or_equal($token, $stack[count($stack)-1])) { $o2 = array_pop($stack); array_push($output_queue, $o2); } array_push($stack, $token); } else if (is_parenthesis($token)) { if (is_left_parenthesis($token)) { array_push($stack, $token); } else { while (!is_left_parenthesis($stack[count($stack)-1]) && count($stack) > 0) { array_push($output_queue, array_pop($stack)); } if (count($stack) == 0) { echo ("parse error"); die(); } $lp = array_pop($stack); } } else { array_push($output_queue, $token); } } while (count($stack) > 0) { $op = array_pop($stack); if (is_parenthesis($op)) die("mismatched parenthesis"); array_push($output_queue, $op); } return $output_queue; } function str2bool($s) { if ($s == "true") return true; if ($s == "false") return false; die('$s doesn\'t contain valid boolean string: '.$s.'\n'); } function apply_operator($operator, $a, $b) { if (is_string($a)) $a = str2bool($a); if (!is_null($b) and is_string($b)) $b = str2bool($b); if ($operator == "and") return $a and $b; else if ($operator == "or") return $a or $b; else if ($operator == "not") return ! $a; else die("unknown operator `$function'"); } function get_num_operands($operator) { global $num_operands; return $num_operands[$operator]; } function is_unary($operator) { return get_num_operands($operator) == 1; } function is_binary($operator) { return get_num_operands($operator) == 2; } function eval_rpn($tokens) { $stack = array(); foreach ($tokens as $t) { if (is_operator($t)) { if (is_unary($t)) { $o1 = array_pop($stack); $r = apply_operator($t, $o1, null); array_push($stack, $r); } else { // binary $o1 = array_pop($stack); $o2 = array_pop($stack); $r = apply_operator($t, $o1, $o2); array_push($stack, $r); } } else { // operand array_push($stack, $t); } } if (count($stack) != 1) die("invalid token array"); return $stack[0]; } // $input = array("A", "and", "B", "or", "C", "and", "(", "D", "or", "F", "or", "not", "G", ")"); $input = array("false", "and", "true", "or", "true", "and", "(", "false", "or", "false", "or", "not", "true", ")"); $tokens = shunting_yard($input); $result = eval_rpn($tokens); foreach($input as $t) echo $t." "; echo "==> ".($result ? "true" : "false")."\n"; 

Вы можете использовать парсер LR для построения дерева синтаксического анализа и затем оценить дерево для получения результата. Подробное описание, включая примеры, можно найти в Википедии . Если вы еще не закодировали это, я напишу небольшой пример сегодня вечером.

Самый простой способ – использовать регулярные выражения, которые преобразуют ваше выражение в выражение в синтаксисе php, а затем используют eval, как это было предложено symcbean. Но я не уверен, хотите ли вы использовать его в производственном коде.

Другим способом является кодирование собственного простого рекурсивного анализатора спуска . Это не так сложно, как может показаться. Для простой грамматики, такой как ваши (логические выражения), вы можете легко закодировать ее с нуля. Вы также можете использовать генератор синтаксического анализатора, аналогичный ANTLR для php, возможно, поиск генератора парсера php может вызвать что-то.