ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В C++ (4-Е ИЗДАНИЕ) (часть 10) онлайн
Разбор арифметических выражений
Этот раздел посвящен разбору арифметических выражений. Начнем слева и рас- смотрим все символы по очереди. Это могут быть числа (от 0 до 9) или операции (знаки +, -, * и /).
Если символ представляет собой число, то мы помещаем его в стек. Туда же мы поместим первую из встретившихся нам операций. Вся хитрость заключает- ся в том, как составить последовательность операций. Заметим, что мы не вы- полняем действие текущей операции, так как мы еще не знаем, какое за ней сле- дует число. Найденная операция является сигналом, что мы можем выполнить предыдущую операцию, которая помещена в стек. Так, если в стеке последова- тельность 2 + 3, то перед выполнением сложения мы должны найти следующую операцию.
Таким образом, когда мы поняли, что текущий символ является операцией (за исключением первого), мы извлекаем из стека предыдущее число (3 в на- шем примере) и предыдущую операцию (+) и помещаем их в переменные Lastval и Lastop. Наконец мы извлекаем первое число (2) и выполняем арифметическую операцию с двумя числами (получая 5). Всегда ли мы можем выполнить преды- дущую операцию? Нет. Вспомним, что * и / имеют более высокий приоритет, чем + и -. В выражении 3+4/2 мы не можем выполнить сложение пока не про- изведено деление. Поэтому, когда мы встретим операцию / в этом выражении, то мы должны положить 2 и + обратно в стек до тех пор, пока не будет выполне- но деление.
С другой стороны, если текущая операция + или -, то мы всегда можем вы- полнить предыдущую операцию. Так, когда мы встретим + в выражении 4-5+6, то мы можем выполнить операцию -, а когда мы увидим - в выражении 6/2-3, то мы можем выполнить деление. В таблице 10.1 отражены четыре возможных случая.
Таблица 10.1. Операции при разборе выражений
|
Предыдущий оператор |
Текущий оператор |
Пример |
Действие1 |
|
+ или - |
* или /1 |
3+4/ |
Положить в стек предыдущий оператор и предыдущее число (+, 4) |
|
* или / |
* или / |
9/3* |
Выполнить предыдущий оператор, положить в стек результат (3) |
|
+ или - |
+ или - |
6+3+ |
Выполнить предыдущий оператор, положить в стек результат (9) |
|
* или / |
+ или - |
8/2- |
Выполнить предыдущий оператор, положить в стек результат (4) |
Метод parse() выполняет этот процесс, последовательно обрабатывая полу- ченное выражение и выполняя операции. Но здесь много работы. В стеке все еще содержится или одно число, или несколько последовательностей число- операция—число. Обрабатывая содержимое стека, мы выполняем операции этих последовательностей. Наконец в стеке останется одно число; оно будет значением первоначального выражения. Метод solve() выполняет все выше перечисленные
действия до тех пор, пока в стеке не останется одно число. Проще говоря, метод parse () помещает элементы выражения в стек, а метод solve () извлекает их.
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60