Как оценить выражение в префиксной нотации

Будет проще, если вы будете использовать постфикс вместо префикса. См. Обратная польская нотация (RPN) . Учитывая выражение в RPN, это легко оценить, используя всего один стек.

Но поскольку вы попросили способ оценивать выражения префикса без рекурсии и с использованием стеков (возможно, более простой способ см. EDIT: ниже), вот один способ:

Мы можем это сделать используя два стека.

Один стек (назовите его Evaluation) содержит операторы (например, +, sin и т. Д.) И операнды (например, 3,4 и т. Д.), А другой стек (назовите его Count) содержит кортеж количества операндов, оставшихся для просмотра. + количество операндов, ожидаемых оператором.

Каждый раз, когда вы видите оператор, вы помещаете его в стек оценки и помещаете соответствующий кортеж в стек счетчика.

Каждый раз, когда вы видите операнд (например, 3,5 и т. Д.), Вы проверяете верхний кортеж стека Count и уменьшаете количество операндов, оставшихся для просмотра в этом кортеже.

Если количество оставшихся операндов становится равным нулю, вы извлекаете кортеж из стека счетчика. Затем из стека оценки вы извлекаете необходимое количество операндов (вы знаете это из-за другого значения кортежа), извлекаете оператор и выполняете операцию для получения нового значения (или операнда).

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

Если счетчик операндов не становится равным нулю, вы продолжаете вводить следующий токен.

Например, вы должны были вычислить + 3 + 4/20 4

Стопки будут выглядеть так (слева - верх стека)

Count                  Evaluation                   Input
                                                   + 3 + 4 / 20 4

(2,2)                   +                            3 + 4 / 20 4

(2,1)                   3 +                            + 4 / 20 4

(2,2) (2,1)             + 3 +                            4 / 20 4

(2,1) (2,1)             4 + 3 +                            / 20 4

(2,2) (2,1) (2,1)       / 4 + 3 +                            20 4

(2,1) (2,1) (2,1)       20 / 4 + 3 +                            4

(2,0) (2,1) (2,1)       4 8 / 4 + 3 +                   

Since it has become zero, you pop off two operands, the operator / 
and evaluate and push back 5. You pop off (2,0) from the Count stack.

(2,1) (2,1)                5 4 + 3 +

Pushing back you decrement the current Count stack top.

(2,0) (2,1)               5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack.

(2,0)                          9 3 + 

                               12

РЕДАКТИРОВАТЬ:

Друг предложил способ сделать это без нескольких стеков:

Начать с конца, перейти к первому оператору. Токены справа от этого будут операндами. Оценить и повторить. Кажется, намного проще, чем делать это с двумя стеками. Мы можем использовать двусвязный список для представления входных данных, которые мы изменяем во время обработки. Когда вы оцениваете, вы удаляете узлы, а затем вставляете результат. Или вы могли бы просто использовать один стек.