А816

Задача: Преобразовать выражение ( т. е. текст специального вида), составленное из цифр и знаков четырех арифметических операций ( сложения, вычитания, умножения, деления) в постфиксную форму. В постфиксной форме сначала записываются операнды, а затем знак операции.

Тесты*:

 Инфиксная форма Постфиксная форма Инфиксная форма Постфиксная форма
3+4 3 4 +   3+4*2/(1-5)^2  3 4 2 * 1 5 — 2 ^ / +
(5-4)+2 5 4 — 2 +  (1+2)*4+3  1 2 + 4 * 3 +
2*(3+4)*5 2 3 4 + * 5 *  78^6-3+9^(2-1)  78 6 ^ 3 — 9 2 1 — ^ +

*тесты взяты из примеров Абрамова, примеры из Википедии и немного собственных тестов.

Несколько оговорок по поводу программы:

1. Я расширил множество допустимых операторов добавив туда возведение в  степень

2. Программа предполагает, что в выражении согласованы все скобки, иначе она будет работать не правильно.

3. В реализации программы через массив символов я предположил что  вводимое выражение не будет превышать 50 символов. ( то есть, если учитывать пробелы, то финальная строка не будет превышать 100 символов)

4. Простите мне некоторое отклонение  от привычного порядка отчета. Я считаю более удобным выложить сначала  алгоритм, ибо он в обеих реализациях одинаков, а затем уже, показав код программы, комментировать детали каждой из реализаций.

Вообще постфиксная запись еще называется Обратной Польской Нотацией ( ОПН). За алгоритмом преобразования выражений из инфиксной ( привычной нам формы записи) в ОНП можно обратится к Википедии.

Алгоритм

  • Пока есть ещё символы для чтения:
  • Читаем очередной символ.
  • Если символ является числом, добавляем его к выходной строке..
  • Если символ является открывающей скобкой, помещаем его в стек.
  • Если символ является закрывающей скобкой:
До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.
  • Если символ является оператором о1, тогда:
1) пока приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека выталкиваем верхние элементы стека в выходную строку;
2) помещаем оператор o1 в стек.
  • Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении не согласованы скобки.

 

Собственно весь код программы — это всего лишь последовательная реализация данного алгоритма, с учетом некоторых тонкостей.

Реализация через <string>

ССЫЛКА

Моменты которые следовало бы объяснить:

1) Зачем мы проверяем, является ли предыдущий символ числом, если данный тоже число?

Эта проверка помогает нам определить, сколько цифр имело наше число. Без данной проверки, например, выражение: [latex]34*2-1[/latex]  будет иметь вид не  [latex]34 2 * 1 — [/latex] , а  [latex]3 4 2 * 1 — [/latex]. В этом случае возникает двоякость при чтении выражения. Преобразовывая обратно можно предположить, что исходное выражение было  [latex]3*42-1[/latex].

2) Зачем мы делаем замену символам умножения и вычитания, в случае когда читаемый символ это оператор?

Причина состоит в том, что нам требуется правильно контролировать приоритеты операций. Если распечатать  номера символов то мы увидим следующее:

А по своему приоритету, операции сортируются так:

Операция умножения по своему числу находится ниже плюса и минуса, хотя по приоритету она выше. И поэтому, гораздо проще заменить ее на точку, которая точно не встретится в математическом выражении, а закончив обработку, поменять обратно.
Менять минус на запятую мы вынуждены через то, что некоторые операции имеют попарно одинаковый приоритет. Мне показалось это выгодным вариантом, заменить минус запятой, и тем самым получить для каждой пары операций  ( аддитивной и мультипликативной) своеобразный «радиус приоритета», который не пересекается с другим, таким же «радиусом». В финале, мы заменяем запятую на минус, так же, как и в случае с умножением и точкой.
Поскольку операция возведения в степень находится гораздо выше остальных, и не имеет пару в  списке приоритетов ее изменения совсем не коснулись.

В общем, детали реализации состоят  в том, что к строке stack  мы обращаемся через функции, как к стеку символов. В общем — программа просто реализует описанный выше алгоритм.

Реализация через массив char

ССЫЛКА

В общем, реализация не особо отличается от предыдущей. Алгоритм тот же, детали и идеи те же. Разница лишь в используемых инструментах. Теперь, вместо строки типа string мы используем массив символов. И как следствие, нам требуется ввести переменную ( в нашей программе — n) которая будет контролировать номер ячейки в которую будет присваиваться символ. Так же, после все обработки, требуется вставить дополнительно символ окончания строки ».  После этого можно обращаться и форматировать строку, по нашей надобности.

Стэк здесь реализован через вектор символов. Тогда мы так же обращаемся  к нему через функции, и при этом мы не должны контролировать его размерность, она динамически изменяется по ходу выполнения программы. Комментарии к данной реализации такие же как и в первой. Поэтому можно смело рассматривать две реализации, как отдельные и полноценные программы.

Царев Николай Александрович
Царев Николай Александрович

Latest posts by Царев Николай Александрович (see all)

One thought on “А816