Какой самый простой способ вычислить инфиксное выражение, используя язык Си?

Question

Предположим, пользователь вводит инфиксное выражение в виде строки? Что может быть самым простым ( Под самым простым я имею в виду сокращенный t) способ оценки результата этого выражения с использованием языка Си?

Возможные способы преобразования его в постфикс с использованием стеков. Но это довольно длительный процесс. Можно ли использовать такие функции, как atoi () или eval () , которые могут упростить работу?

Answer 1

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

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

Answer 2

C не имеет встроенной функции eval, но есть библиотеки, которые предоставляют ее.

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

Вот полный пример его использования, который должен продемонстрировать, насколько это просто:

#include "tinyexpr.h"
#include <stdio.h>

int main(int argc, char *argv[])
{
    printf("%f\n", te_interp("5 * 5", 0)); //Prints 25
    return 0;
}

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

Answer 3

нужно разобрать строку. в C нет eval() (как в большинстве статических языков), поэтому вам нужно либо написать собственный анализатор, либо найти какую-нибудь библиотеку, чтобы помочь.

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

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

Answer 4

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

Взгляните на статью в Википедии Обратная польская запись . Он показывает, как сделать преобразование и расчет.

Answer 5

Вам необходимо встроить интерпретатор некоторого языка сценариев.

Answer 6

Под самым простым, под которым вы подразумеваете самый короткий, вы имеете в виду самый быстрый код? Если это так, создайте строку и передайте ее другому процессу с помощью popen или подобного. Если вам не нужен внешний процесс, вставьте интерпретатор lua, как предложил Хавьер. +1 Хавьеру, так как это, вероятно, то, что вы хотите.

Answer 7

Один чистый (возможно, не короткий) способ сделать это - построить дерево, как это делает компилятор.

Например, скажем, у вас есть выражение "2 + 3". «+» Будет головой. «2» будет левый ребенок, а «3» будет правый ребенок.

Поскольку каждое выражение оценивается как значение, это дерево можно расширять для бесконечно сложных выражений: его просто нужно отсортировать в порядке приоритета для каждого оператора. Операторы с низким приоритетом (например, «+» идут вверху, а операторы с высоким приоритетом (например, *) - снизу. Затем вы будете оценивать выражения в дереве снизу вверх.