Разбор математических выражений

Ответ 1

Вам нужно написать лексический анализатор чтобы токенизировать вход (разбить его на его составные части - операторы, пунктуаторы, идентификаторы и т.д.).). Неизбежно, вы получите некоторую последовательность токенов.

После этого существует несколько способов оценки ввода. Один из самых простых способов сделать это - преобразовать выражение в постфикс, используя алгоритм shunting yard (оценка постфиксного выражения легко с капиталом Е).

Ответ 2

Вы должны искать "абстрактные деревья синтаксиса" и "деревья выражений", а также "лексический анализ", "синтаксис", "синтаксический анализ" и "теория компилятора". Чтение ввода текста и получение смысла от него довольно сложно для большинства вещей (хотя мы часто стараемся убедиться, что у нас простой ввод).

Первым шагом при создании парсера является запись грамматики для вашего языка ввода. В этом случае ваш язык ввода - это некоторые математические выражения, поэтому вы бы сделали что-то вроде:

expr => <function_identifier> ( stmt )
        ( stmt )
        <variable_identifier>
        <numerical_constant>

stmt => expr <operator> stmt

(Я не написал грамматику, подобную этой {look up BNF и EBNF} через несколько лет, поэтому я, вероятно, сделал некоторые вопиющие ошибки, которые кто-то еще любезно отметим) Это может значительно усложниться в зависимости от того, как вы обрабатываете приоритет оператора (умножить и на устройство до добавления и вычитания типа), но точка грамматики в этом случае поможет вам написать парсер.

Есть инструменты, которые помогут вам сделать это (yacc, bison, antlr и другие), но вы можете сделать это и вручную. Есть много способов сделать это, но все они имеют одну общую черту - стек. Для обработки такого языка требуется нечто, называемое push down automaton, что является просто причудливым способом сказать что-то, что может принимать решения на основе нового ввода, текущего состояния и верхнего элемента стека. Решения, которые он может сделать, включают в себя толкание, выскакивание, изменение состояния и объединение (поворот 2+3 в 5 является формой объединения). Комбинация обычно называется производством, потому что она дает результат.

Из разных распространенных типов парсеров вы почти наверняка начнете с рекурсивного приличного парсера. Обычно они записываются непосредственно на языке программирования общего назначения, таком как C. Этот тип анализатора состоит из нескольких (часто многих) функций, которые вызывают друг друга, и они в конечном итоге используют системный стек в качестве пускового автомата.

Еще одна вещь, которую вам нужно будет сделать, - записать различные типы слов и операторов, которые составляют ваш язык. Эти слова и операторы называются лексемами и представляют собой токены вашего языка. Я представлял эти токены в грамматике <like_this>, за исключением скобок, которые представляли себя.

Скорее всего, вы захотите описать свои лексемы набором регулярных выражений. Вы должны быть знакомы с ними, если используете grep, sed, awk или perl. Это способ описания того, что известно как обычный язык, который может обрабатываться чем-то известным как конечный автомат. Это просто фантастический способ сказать, что это программа, которая может принять решение об изменении состояния, рассматривая только свое текущее состояние и следующий вход (следующий символ ввода). Например, часть вашего лексического описания может быть:

[A-Z]   variable-identifier
sqrt    function-identifier
log     function-identifier
[0-9]+  unsigned-literal
+       operator
-       operator

Существуют также инструменты, которые могут генерировать код для этого. lex, который является одним из них, очень интегрирован с программой генерации парсера yacc, но поскольку вы пытаетесь узнать, вы также можете написать свой собственный код токенизатора/лексического анализа в C.

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

Затем после того, как вы прочитаете значения переменных, вы можете пересечь дерево и вычислить фактическое число.

Ответ 3

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

Если вы просто хотите вывести результат на консоль, это очень просто, и вам даже не придется слишком глубоко вникать в внедрение Python. Так как тогда вы должны написать только одну строку в Python для вывода значения.

Вот код Python, который вы могли бы использовать:

exec "import math;A=<vala>;B=<valb>;C=<valc>;D=<vald>;print <formula>".replace("^", "**").replace("log","math.log").replace("ln", "math.log").replace("sin","math.sin").replace("sqrt", "math.sqrt").replace("cos","math.cos")

Обратите внимание, что замены выполняются в Python, так как я уверен, что это проще сделать в Python, а не C. Также обратите внимание, что если вы хотите использовать xor ('^'), вам нужно будет удалить .replace("^","**") и используйте ** для включения питания.

Я не знаю достаточно C, чтобы узнать, как сгенерировать эту строку на C, но после этого вы можете использовать следующую программу для ее запуска:

#include <Python.h>

int main(int argc, char* argv[])
{
  char* progstr = "...";
  Py_Initialize();
  PyRun_SimpleString(progstr);
  Py_Finalize();
  return 0;
}

Вы можете найти дополнительную информацию о вложении Python в C здесь: Документация по расширению и встраиванию Python

Если вам нужно использовать результат вычисления в вашей программе, есть способы прочитать это значение с Python, но вам придется самим прочитать их.

Ответ 4

Кроме того, вы должны просмотреть свои сообщения в SO и другие сообщения, касающиеся двоичных деревьев. Реализуйте это, используя древовидную структуру. Пройдите в качестве инфикса для оценки. Были замечательные ответы на вопросы дерева.

Если вам нужно сохранить это (для сохранения, как в файле), я предлагаю XML. Анализ XML должен заставить вас по-настоящему оценить, насколько легко ваше назначение.

Ответ 5

Отправляй сообщение: http://blog.barvinograd.com/2011/03/online-function-grapher-formula-parser-part-2/ Он использует библиотеку ANTLR для синтаксического анализа математического выражения, который специально использует выход JavaScript, но ANTLR имеет много выходных данных, таких как Java, Ruby, С++, С#, и вы должны иметь возможность использовать грамматику в сообщении для любого языка вывода.