Написание выражений:Инфикс, Постфикс и Префикс

Question

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

например:

3*(A+B)-(-2-78)*2+(0* А)

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

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

Какую нотацию выбрать в качестве основы дерева?

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

Ваше здоровье,

Answer 1

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

Если вы настаиваете на том, чтобы написать свой собственный,

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

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

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

Answer 2

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

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

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