парсинг математических выражений

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

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

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

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

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

stmt => expr <operator> stmt

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

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

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

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

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

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

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

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

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

Возможно, проще всего использовать встроенный язык, такой как 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, но вам придется прочитать о них самостоятельно.