Управляет двумя стеками. В одном стеке записываются текущие опера торы (например, +), а в другом — текущие операн ды (например, 3.141). Временные результаты вычисляются по мере отправки новых операторов из CalcGui и помещаются на стек операндов.
Из этого можно сделать вывод, что механизм вычисления выражений сводится к жонглированию стеками операторов и операндов. В некотором смысле, для вычисления выражений калькулятор реализует простой язык про грам миро ва ния на основе стеков. При сканировании строк выражений слева направо во время ввода операнды попутно помещаются на стек; при этом операторы служат разделителями операндов и могут вызывать вычисление промежуточных результатов перед помещением на стек. Поскольку этот механизм выполняет запись информации о состоянии и производит переходы, для описания реализации языка калькулятора можно было бы использовать термин ко неч ный ав то мат.
Ниже описывается общий сценарий:
1. Когда обнаруживается новый оператор (то есть когда нажимается кнопка или клавиша, соответствующая оператору), предыдущий операнд в поле ввода помещается на стек операндов.
2. Затем в стек операторов добавляется введенный оператор, но только после того, как все незавершенные операторы с более высоким старшинством вытолкнуты со стека и применены к ожидающим обработки операндам (например, нажатие + вызывает срабатывание всех невыполненных операторов * в стеке).
3. При нажатии eval (вычислить) все оставшиеся операторы выталкиваются со стека и применяются к оставшимся операндам, и результатом является последнее значение, оставшееся в стеке операндов.
В завершение последнее значение в стеке операндов отображается в поле ввода калькулятора в готовности для использования в другой операции. Этот алгоритм вычислений лучше всего, вероятно, описать на примерах. Введем несколько выражений и посмотрим, как заполняются стеки вычислений.
Трассировка стека калькулятора PyCalc включается с помощью флага debugme в модуле — если он имеет значение True, стеки операторов и операндов выводятся в stdout каждый раз, когда класс Evaluator собирается применить оператор и вы толк нуть элементы со стеков. Чтобы увидеть эту информацию, запустите PyCalc в окне консоли. При каждом выталкивании элементов из стека выводится кортеж, содержащий списки стеков (оператор ы, опер анд ы) — вершины стеков находятся в концах списков. Например, ниже приводится вывод в консоли после ввода и вычисления простой строки:
1) Нажатые клавиши: "5 * 3 + 4 <eval>" [результат = 19]
([‘*’], [‘5’, ‘3’]) [по нажатию ‘+’: выведет "15"]
([‘+’], [’15’, ‘4’]) [по нажатию ‘eval’: выведет "19"]
Обратите внимание, что ожидающее обработки (находящееся в стеке) подвыражение * вычисляется при нажатии +: операторы * имеют более высокий приоритет, чем +, поэтому вычисления выполняются сразу, перед проталкиванием оператора +. При нажатии кнопки + поле ввода содержит число 3 — мы помещаем 3 на стек операндов, вычисляем подвыражение (5*3), помещаем результат на стек операндов, помещаем оператор + на стек операторов и продолжаем сканировать ввод пользователя. Когда в конце нажимается кнопка eval (вычислить), на стек операндов помещается число 4 и к оставшимся операндам на стеке применяется оператор +.
Поле ввода, находящееся в верхней части главного окна, также играет определенную роль в этом алгоритме. Поле ввода и стеки выражения объединяются классом калькулятора. Вообще говоря, поле ввода всегда содержит предыдущий операнд, когда нажимается кнопка оператора (например, при вводе последовательности 5 *). Значение текстового поля должно быть помещено на стек операндов до того, как будет опознан оператор. Поэтому мы должны вытолкнуть результаты, прежде чем отобразить их после нажатия кнопки eval (вычислить) или ввода символа «)» (в противном случае результаты будут помещены на стек дважды) — они находились бы на стеке и отображались в поле ввода, откуда они немедленно будут помещены на стек еще раз, при вводе следующего оператора.
Для удобства и обеспечения точности вычислений после ввода оператора и перед вводом очередного операнда необходимо также стереть содержимое поля ввода (например, перед вводом 3 и 4 в выражении 5 * 3 + 4). Подобное стирание прежних значений выполняется также при нажатии кнопки eval (вычислить) или вводе символа «)» исходя из предположения, что следующее нажатие кнопки или клавиши изменит предыдущий результат — чтобы дать возможность ввести новое выражение после нажатия кнопки eval (вычислить) и новый операнд, следующий за оператором после ввода символа «)». Например, чтобы стереть 12, результат подвыражения в круглых скобках, при вводе 2 в выражении 5 + (3 * 4) * 2. Без этого стирания новые операнды просто добавлялись бы в конец текущего отображаемого значения. Данная модель также позволяет заменять промежуточный результат на операнд после ввода символа «)» вводом операнда вместо оператора.
Стеки выражений также задерживают выполнение операций с более низким приоритетом в процессе сканирования ввода. В следующем примере ожидающий оператор + не выполняется, пока не будет нажата кнопка * : поскольку оператор * имеет более высокий приоритет, нам необходимо отложить выполнение оператора +, пока не будет выполнен оператор *. Оператор * не выталкивается со стека, пока не будет получен его правый операнд 4. По нажатию кнопки eval (вычислить) со стека выталкиваются и применяются к элементам стека операндов два оператора — оператор *, находящийся на вершине стека операторов, применяется к операндам 3 и 4, находящимся на вершине стека операндов, а затем оператор + применяется к числу 5 и к числу 12, помещенному на стек оператором *:
2) Нажатые клавиши: "5 + 3 * 4 <eval>" [результат = 17]
([‘+’, ‘*’], [‘5’, ‘3’, ‘4’]) [по нажатию клавиши ‘eval‘] ([‘+’], [‘5′, ’12’]) [выведет "17"]
Для выражений, содержащих операторы с одинаковым приоритетом, как показано ниже, выталкивание и вычисление выполняется сразу при сканировании слева направо без откладывания вычисления. Это приводит к линейному вычислению слева направо, если отсутствуют скобки: выражение 5+3+4 вычисляется как ((5+3)+4). Для операций + и * порядок не имеет значения:
3) Нажатые клавиши: "5 + 3 + 4 <eval>" [результат = 12]
([‘+’], [‘5’, ‘3’]) [по нажатию второго оператора ‘+’] ([‘+’], [‘8’, ‘4’]) [по нажатию клавиши ‘eval’]
Ниже приводится более сложный пример. В данном случае все операторы и операнды помещаются на стек (откладываются), пока не будет введен символ «)» в конце. Чтобы обеспечить такую работу со скобками, открывающей скобке «(» присвоен наивысший приоритет и она помещается на стек операторов, чтобы отсрочить выполнение операторов, находящихся на стеке ниже, пока не будет введен символ «)». При вводе символа «)» подвыражение, заключенное в круглые скобки, выталкивается со стека и вычисляется, и в поле ввода выводится число 13. При нажатии кнопки eval (вычислить) вычисляется оставшаяся часть выражения ((3 * 13), (1 + 39)) и отображается окончательный результат (40). Этот результат в поле ввода превращается в левый операнд другого оператора.
4) Нажатые клавиши: "1 + 3 * ( 1 + 3 * 4 ) <eval>" [результат = 40] ([‘+’, ‘*’, ‘(‘, ‘+’, ‘*’], [‘1’, ‘3’, ‘1’, ‘3’, ‘4’]) [по нажатию клавиши ‘)’] ([‘+’, ‘*’, ‘(‘, ‘+’], [‘1’, ‘3’, ‘1’, ’12’]) [выведет "13"] ([‘+’, ‘*’], [‘1’, ‘3’, ’13’]) [по нажатию
клавиши ‘eval‘] ([‘+’], [‘1′, ’39’])
В действительности можно снова использовать любой временный результат: если снова нажать кнопку оператора, не вводя новых операндов, он применяется к результату предыдущего нажатия — значение в поле ввода дважды помещается на стек и выполняется оператор. Нажмите кнопку * множество раз после ввода 2, чтобы увидеть, как это действует (например, 2***). Первое нажатие *, поместит 2 на стек операндов и * на стек операторов. Следующее нажатие * опять поместит 2 из поля ввода на стек операндов, вытолкнет и вычислит выражение на стеке (2 * 2), поместит результат обратно на стек и отобразит его. Каждое последующее нажатие * повторно будет помещать на стек текущее отображаемое значение и выполнять операцию, последовательно вычисляя квадраты чисел.
На рис. 19.6 показано, как выглядят оба стека в самой верхней точке во время сканирования выражения при трассировке предыдущего примера. Верхний оператор применяется к двум верхним операндам, и результат возвращается обратно для следующего оператора. Поскольку в работе участвуют два стека, результат напоминает преобразование выражения в строку вида +1*3(+1*34 и вычисление ее справа налево. Однако в других случаях производится вычисление частей выражений и отображение промежуточных результатов, поэтому данный процесс не является простым преобразованием строки.
Наконец, следующий пример возбуждает ошибку. Программа PyCalc довольно небрежно относится к обработке ошибок. Многие ошибки оказываются невозможными благодаря самому алгоритму, но на таких ошибках, как непарные скобки, реализация алгоритма вычисления все же спотыкается. Вместо того чтобы пытаться явно обнаруживать все возможные случаи ошибок, в методе reduce используется общая инструкция try, которая перехватывает все ошибки: ошибки выражений, числовые ошибки, ошибки неопределенных имен, синтаксические ошибки и так далее.
|
|
Рис. 19.6. Стеки вычисления: 1 + 3 * (1 + 3 * 4)
Операнды и временные результаты всегда помещаются на стек в виде строк, а все операторы применяются путем вызова функции eval. Если ошибка происходит внутри выражения, на стек операндов проталкивается результат *ERROR*, в результате чего все оставшиеся операторы также не смогут выполниться в eval. Вследствие этого операнд *ERROR* распространяется до вершины выражения и в конце оказывается последним операндом, который выводится в поле ввода, извещая о допущенной ошибке:
5) Нажатые клавиши: "1 + 3 * ( 1 + 3 * 4 <eval>" [результат = *ERROR*] ([‘+’, ‘*’, ‘(‘, ‘+’, ‘*’], [‘1’, ‘3’, ‘1’, ‘3’, ‘4’]) [по нажатию eval] ([‘+’, ‘*’, ‘(‘, ‘+’], [‘1’, ‘3’, ‘1’, ’12’]) ([‘+’, ‘*’, ‘(‘], [‘1’, ‘3’, ’13’])
([‘+’, ‘*’], [‘1’, ‘*ERROR*’])
([‘+’], [‘*ERROR*’])
([‘+’], [‘*ERROR*’, ‘*ERROR*’])
Проследите в программном коде калькулятора, как выполняется этот и другие примеры, чтобы получить представление, как производятся вычисления с применением стеков. Как только вы поймете принцип действия механизма работы со стеками, вычисление выражений станет для вас простой задачей.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
