Написание выражений: Infix, Postfix и Prefix

Question

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

например:

3 * (А + В) - (- 2-78) * 2 + (0 * А)

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

Вопрос: Каков наилучший способ сделать это? (С оптимизацией и проверкой)

Какие обозначения для выбора в качестве основы дерева?

Должен ли я представлять выражение в виде дерева? Если это так, я могу легко оптимизировать его (просто отбросить узлы, которые возвращают 0 или что-то еще).

Приветствия

Answer 1

Ссылка, предложенная в комментарии Грега Хьюгилла выше, содержит всю необходимую информацию:

Если вы настаиваете на написании своего,

• a парсер рекурсивного спуска , вероятно, самый простой способ сделать это вручную.
• В противном случае вы можете использовать такой инструмент, как Bison (поскольку вы работаете в C). Этот урок - лучшее, что я видел для работы с Flex и Bison (или Lex / Yacc)

Вы также можете найти "выражение оценки" в Codeproject - у них много статей по теме.

Некоторое время назад я столкнулся с оценщиком выражений программы M4. Вы можете изучить его код, чтобы увидеть, как он работает. Я думаю эта ссылка в Google Codesearch является версией, которую я видел.

Answer 2

Ваш вопрос указывает на требования, предъявляемые к вашему решению:

к сожалению на C

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