Рубрики

Структуры данных | Стек | Вопрос 6

Следующее постфиксное выражение с однозначными операндами оценивается с помощью стека:

              8 2 3 ^ / 2 3 * + 5 1 * - 

Обратите внимание, что ^ является оператором возведения в степень. Два верхних элемента стека после первого * оцениваются:
(А) 6, 1
(Б) 5, 7
(С) 3, 2
(D) 1, 5

Ответ: (А)
Объяснение: Алгоритм вычисления любого постфиксного выражения довольно прост:

1. While there are input tokens left
    o Read the next token from input.
    o If the token is a value
       + Push it onto the stack.
    o Otherwise, the token is an operator 
      (operator here includes both operators, and functions).
       * It is known a priori that the operator takes n arguments.
       * If there are fewer than n values on the stack
        (Error) The user has not input sufficient values in the expression.
       * Else, Pop the top n values from the stack.
       * Evaluate the operator, with the values as arguments.
       * Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
    o That value is the result of the calculation.
3. If there are more values in the stack
    o (Error)  The user input has too many values.

Источник для алгоритма: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm

Запустим приведенный выше алгоритм для данного выражения.
Первые три токена являются значениями, поэтому они просто выдвигаются. После нажатия 8, 2 и 3 стек выглядит следующим образом

    8, 2, 3

Когда ^ читается, верхние два выталкиваются и вычисляется мощность (2 ^ 3)

    8, 8

Когда / читается, верхние два выталкиваются и выполняется деление (8/8)

    1

Следующие два токена являются значениями, поэтому они просто выдвигаются. После нажатия 2 и 3 стек выглядит следующим образом

    1, 2, 3

Когда * приходит, две верхние появляются и умножение выполняется.

    1, 6

Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Стек | Вопрос 6

0.00 (0%) 0 votes