Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 79 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
Продолжение.
Символ Действие
Состояние
выходной
строки
Состояние стека
)
')' – закрывающая скобка.
Извлекаем из стека в вы-
ходную строку все симво-
лы, пока не встретим
открывающую скобку. За-
тем уничтожаем обе скоб-
ки.
a b c - +
*
'*' – знак операции, кото-
рый имеет приоритет 3.
Проверяем стек: на верши-
не находится символ '+',
приоритет которого равен
2, т.е. меньший, чем прио-
ритет '*'. Следовательно,
мы должны поместить те-
кущий символ '*' в стек.
a b c -
*
+
d
'd' – переменная. Помещаем
ее в выходную строку.
a b c - d
*
+
Теперь вся входная строка разобрана, но в стеке еще остаются знаки опе-
раций, которые мы должны просто извлечь в строку-результат. Итак, мы по-
лучили конечный результат: «a b c - d * +».
11. Дана символьная строка, содержащая постфиксную форму правильно
записанного арифметического выражения, операндами которого являются
цифры. Написать функцию вычисления этого выражения.
Можно использовать следующий алгоритм. Выражение просматривается
слева направо. Если встречается цифра, то она заносится в стек. Если встреча-
ется знак операции, то из стека извлекаются два операнда, над ними выполня-
ется операция и ее результат записывается в стек. Когда выражение заканчи-
вается, в стеке остается одно число – значение выражения.
12. Решить задачу 7 при условии, что операндами выражения являются
натуральные числа.
79
             .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
                                                                     Продолжение.
                                                  Состояние
    Символ                 Действие               выходной       Состояние стека
                                                   строки
                  ')' – закрывающая скобка.
                  Извлекаем из стека в вы-
                  ходную строку все симво-
       )          лы, пока не встретим               abc-                +
                  открывающую скобку. За-
                  тем уничтожаем обе скоб-
                  ки.

                  '*' – знак операции, кото-
                  рый имеет приоритет 3.
                  Проверяем стек: на верши-
                  не находится символ '+',
                                                                         *
       *          приоритет которого равен           abc-
                                                                         +
                  2, т.е. меньший, чем прио-
                  ритет '*'. Следовательно,
                  мы должны поместить те-
                  кущий символ '*' в стек.

                  'd' – переменная. Помещаем                             *
       d                                            abc-d
                  ее в выходную строку.                                  +


    Теперь вся входная строка разобрана, но в стеке еще остаются знаки опе-
раций, которые мы должны просто извлечь в строку-результат. Итак, мы по-
лучили конечный результат: «a b c - d * +».

    11. Дана символьная строка, содержащая постфиксную форму правильно
записанного арифметического выражения, операндами которого являются
цифры. Написать функцию вычисления этого выражения.
    Можно использовать следующий алгоритм. Выражение просматривается
слева направо. Если встречается цифра, то она заносится в стек. Если встреча-
ется знак операции, то из стека извлекаются два операнда, над ними выполня-
ется операция и ее результат записывается в стек. Когда выражение заканчи-
вается, в стеке остается одно число – значение выражения.

    12. Решить задачу 7 при условии, что операндами выражения являются
натуральные числа.



                                       79

Страницы