Решите уравнение из строки, чтобы привести к C

Question

Я хотел бы знать, есть ли у кого-то информация или опыт о том, как сделать что-то, что звучит просто, но не похоже на это при попытке его запрограммировать. Идея такова: дать строку, содержащую уравнение, например: «2 * x = 10» (это просто, но это может быть очень сложно, например sqrt (54) * 35 = x ^ 2; на ....) и программа вернет х = 5 и, возможно, выдаст журнал того, как он туда попал.

Это выполнимо? Если так, у кого-нибудь есть лидерство? Для информации есть этот сайт (http://www.numberempire.com/equationsolver.php), который делает то же самое в PHP, но не с открытым исходным кодом.

Спасибо за любую помощь!

Answer 1

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

В таких языках, как Ruby, однако, поскольку у вас есть такая тщательная поддержка для работы со строками и у вас есть такая огромная мощность во время выполнения, вы можете решить вашу проблему с помощью одной строки кода, например:

puts(eval($_)) while gets

Да, это покроет больше, чем вы просите.

Answer 2

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

Answer 3

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

Так, например, выражение:

 2 + 3x + 5x^2

Может быть представлен в виде массива или std::vector:

std::vector<int> expression;
expression[0] = 2; // 2 * x ^ 0
expression[1] = 3;
expression[2] = 5;

Написание оценочной функции становится тривиальным и оставляется читателю в качестве упражнения.

Решение нескольких уравнений становится более сложным. Существуют библиотеки и алгоритмы для этого. Поиск Google должен найти что-то хорошее. : -)

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

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

Answer 4

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

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

• Системы линейных уравнений: любой прямой линейный решатель. Если вы хотите показать шаги в явном виде, а число уравнений / неизвестных невелико, я бы порекомендовал что-то простое, например, неискаженное исключение Гаусса или правило Крамера.
• Система полиномиальных уравнений: после подстановки переменной эквивалентна нахождению корней единичных полиномов. Если они имеют степень <= 4, существуют формулы для точных решений. Примечание: для степеней 3 и 4 эти формулы не нравятся. </li>
• Рациональные решения системы полиномиальных уравнений с рациональным коэффициентом: делайте подстановку переменных, как указано выше. Затем перебор, используя тест рационального нуля.
• Другие виды уравнений: Удачи. Для более сложных [систем] нелинейных уравнений, если вы можете согласиться на численные (не аналитические) решения, посмотрите на метод Ньютона.

Answer 5

Вы можете попробовать связать SymPy с вашим кодом C (или C ++) и использовать его для решения ваших уравнений.

IIRC, SymPy обладает такой функциональностью. Кроме того, должно быть проще манипулировать входной строкой в ​​пригодном для использования уравнении внутри Python, а затем передать ее SymPy для решения.

Answer 6

Одна поправка: это не линейная алгебра, которая обычно означает матрицы из нескольких уравнений и неизвестных.

Ваш пример определенно не сложен.

Что вам нужно, это простая грамматика выражения и парсер. Разобрать уравнение в абстрактное синтаксическое дерево и пройтись по дереву, чтобы оценить его.

Если бы вы писали на Java, это могло бы выглядеть как this . Другой пример: symja . Возможно, вам будет достаточно вдохновения, чтобы придумать свой собственный для C ++.

Возможно, вы захотите заглянуть в Mathematica и Alpha Вольфрама. Стивен Вольфрам - один из лучших в мире математиков и компьютерщиков. У него есть много вещей, которые вы можете использовать с пользой, а не писать сами.

Вам нужно определить, что вы подразумеваете под «решить» и что вы ожидаете получить.

Существуют символические решения и численные решения. Какой ты имеешь в виду? Оба одинаково действительны, но они разные. В зависимости от вашего ответа вы будете применять разные приемы.

Еще один момент: существует много методов «решения» уравнений, которые сильно зависят от типа уравнения. Если вы дадите мне что-то вроде f(x) = 0, я подумаю об алгоритмах поиска корней, таких как метод Ньютона. Если вы дадите мне обыкновенное дифференциальное уравнение, я мог бы попробовать метод подстановки или численное интегрирование с использованием Рунге-Кутты. Если вы дадите мне уравнение в частных производных, я смогу применить метод конечных разностей, конечных элементов или граничных элементов. (Не заводите меня на эллиптические, параболические и гиперболические PDE.)

Суть в том, что ваш вопрос очень общий, и ответ во многом зависит от того, что вы пытаетесь сделать. Может помочь больше деталей.

Answer 7

Если уравнения усложняются, то, конечно, не будет нескольких строк кода C / C ++.

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