По заданной строке арифметического выражения найдите десятичное значение выражения.

Question

Вопрос для интервью.

По заданной строке арифметического выражения найдите десятичное значение выражения.

например.учитывая

 30*(5+10) is a string, its value is 450. 

Моя идея:

анализировать каждый символ один за другим и перестраивать строку как выражение с приоритетом операторов.Но это не эффективно, это O (n ^ 2) или даже хуже.

Лучшие идеи?

спасибо

Answer 1

Вы можете преобразовать выражение в постфикс, используя стек за время O (n).

Затем оцените постфиксное выражение со стеком за O (n) раз.

Преобразование в Postfix требуется для определения приоритета операторов во время вычисления выражения.

См. Оценку арифметических выражений со стеком http://www.cs.wcupa.edu/~rkline/DS/deque-stack-algorithms.html

Answer 2

Добавьте строку "print " перед выражением, заключенным в дополнительную пару скобок, поставьте точку с запятой в конце и передайте ее perl -e, то есть в C:

system("perl -e 'print (30*(5+10));'");

Answer 3

Опишите операцию в терминах сделки: создайте или найдите анализатор для арифметических выражений, проанализируйте строку, оцените абстрактное синтаксическое дерево (AST) и верните результат. Поскольку арифметические выражения являются контекстно-свободными языками и в LL(1), это возможно в O(n). Создание парсера дешево с Boost.Spirit или yacc.

Answer 4

разбирает и маркирует строку с помощью автомата конечного состояния:

integer -> integer-token

operator -> token оператора

открывающая скобка -> state -новое выражение

закрывающая скобка -> состояние - выражение закрытия

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