Главная->Інформатика та програмування->Содержание->Разбор арифметических выражений

ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В 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 () извлекает их.

 

45