Первым шагом является анализ строки, которую вы получили от пользователя. Это включает проверку ошибок ввода и предоставление полезных / описательных сообщений об ошибках (например, «Извините, я не знаю, что означает символ ^»), чтобы пользователь мог знать, что не так, и исправить свою ошибку. Результатом этого должен быть набор токенов; где токен представлен структурой, содержащей идентификатор (например, константа, переменная, левая скобка, правая скобка, сложение, вычитание, умножение, деление, ...) и некоторые данные при необходимости (значение для константы или имя переменной ).
Второй шаг - организовать токены в виде дерева; таким образом, что у токенов оператора есть дочерние элементы, и эти дочерние элементы являются значениями, с которыми работает токен оператора. Это, вероятно, потребует использования правил приоритета операторов (таких как «BEDMAS» - скобки, экспоненты, деление, умножение, сложение, затем вычитание), так что «f(x) = x + 1 * 2» обрабатывается как «f(x) = x + (1 *2)» и не обрабатывается как « f(x) = (x + 1) *2». Это также будет включать в себя предоставление полезных / описательных сообщений об ошибках (например, «Извините, у вас слишком много левых скобок и недостаточно правых скобок»), чтобы пользователь мог знать, в чем дело, и исправить свою ошибку. Например, «f(x) = x * (2 + x) + 1» будет выглядеть примерно так:
[+]
/ \
[*] [1]
/ \
[+] [x]
/ \
[2] [x]
Третий шаг (необязательный в теории) - это оптимизация дерева. Операторы, которые имеют константы, могут быть предварительно вычислены (например, «f(x) = x * (1 + 2)» может стать «f(x) = x * 3»). Сложение или вычитание нуля может быть отброшено (например, «f(x) = x * 2 + 0)» может стать «f(x) = x * 2»). Умножение на ноль можно отбросить (например, «f(x) = x + (x * 0)» может стать «f(x) = x»). Умножение или деление на единицу может быть отброшено (например, «f(x) = x + (x * 1)» может стать «f(x) = x + x»). Деление на ноль может либо стать бесконечностью, либо стать полезным / описательным сообщением об ошибке. Деление на константу может стать умножением на константу (например, «f(x) = x / 4» может стать «f(x) = x * 0.25»).
Четвертый шаг - выполнить дерево каким-либо образом. Самый простой способ - это интерпретировать дерево самостоятельно. За это; начиная с токена на root дерева; если токен является константой, вернуть ее значение, в противном случае вычислить значение для дочерних токенов / с, затем использовать тип токена оператора, чтобы выяснить, что с ними делать, и вернуть это значение. Это естественно рекурсивно. Для высокой производительности вы можете преобразовать дерево в собственный машинный код (JIT-компилятор).
Обратите внимание, что компьютеры не могут правильно выполнять простые математические операции. Например, если вы используете данные напечатайте, что компьютер понимает (например, double) для чего-то типа "((x + 3) / 3 - x) * 100000 - 100000", вы получите очень неправильные результаты. Проблемы заключаются в округлении (из-за недостатка точности и / или иногда необходимости в бесконечной точности) и переполнении. Чтобы исправить это, я бы рекомендовал использовать рациональные числа, где число представляется как 3 целых числа в форме "numerator / denominator * 2**exponent" (например, так что значение 10 будет представлено как 5 / 1 * 2**1, а 10/3 станет 5 / 3 * 2**1 ). С «большими целыми числами» переменного размера в качестве целых чисел это становится невосприимчивым ко всем проблемам (за исключением «нехватки памяти», которая может произойти, только если входная строка от пользователя также чрезвычайно велика).