Обратная польская нотация

Передо мной стояли задачи:

  • перевести выражение в обратную польскую нотацию;
  • посчитать значение выражения.

Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10().

Выражение Обратная польская нотация Результат
15 * -(3 — 4) 15 3 4 — u- * 15
sqrt(4) + (8 * 0.5) 4 sqrt 8 0.5 * + 6
-cube(-3) 3 u- cube u- 27
92 / 10 92 10 / 9.2
pow10(2) — 95 + 4 * 8 2 pow10 95 — 4 8 * + 37

Алгоритм перевода в обратную польскую запись:

  • считываем поочерёдно все лексемы, попутно убирая пробелы;
  • если лексема — это число или переменная, то добавляем её в результирующий список;
  • если лексема — это функция, то добавляем её в стэк;
  • если лексема — это открывающая скобка, то добавляем её в стэк;
  • если лексема — это закрывающая скобка, то:
    • помещаем элементы из стэка в результирующую строку пока не встретим открывающую скобку, притом открывающая скобка удаляется из стэка, но в результирующую строку не добавляется;
    • если на вершине стэка оказывается символ функции, то мы помещаем его из стэка в результирующую строку;
    • если открывающая скока не была встречена, то скобки не согласованы.
  • если лексема — это оператор, то:
    • если это последний символ выражения, то выражение некорректно;
    • если это унарный минус, то добавляем его в стэк;
    • иначе:
      • выталкиваем верхние элементы стэка в результирующую строку, пока приоритет текущего оператора меньше либо равен приоритету оператора, находящегося на верине стэка;
      • помещаем текущий оператор в стэк;
  • когда все данные считаны, выталкиваем все элементы стэка в результирующую строку; если в стэке оказались символы не операторов, то скобки не согласованы.

Алгоритм вычисления значения выражения в обратной польской нотации:

  • если в записи встретили число, то кладём его в стэк;
  • если в записи встретили функцию или унарный минус, то :
    • вытаскиваем из стэка верхний элемент;
    • применяем функцию к нему;
    • кладём элемент обратно в стэк;
  • если в записи встретили бинарный оператор, то:
    • вытаскиваем из стэка два верхних элемента;
    • выполняем над ними операцию;
    • кладём в стэк результат выполнения операции;
  • выводим последний элемент стэка.

Код программы (http://ideone.com/c69iJg):

 

 

5 thoughts on “Обратная польская нотация

  1. Решение, в общем, верное! Вообще то, задание специально подстроено для целочисленных вычислений, указано «sqrt – квадратный корень, округленный до целого,» и целочисленное деление — но Вы решили реализовать вещественные операции, тогда замените «целочисленное деление» в Вашем задании просто на деление (чтобы не переделывать всю программу).

    Немного удивил факт, что calc — это метод класса Ideone, а не ExpressionParser.
    И то, что вычисление функции не выведено в отдельный метод (а если еще парочку функций от одной переменной добавить — calc тогда разрастется).

    Ну и главное, а что если будет задано некорректное выражение? Например, вот так. Возникает необработанная исключительная ситуация. Самое интересное, что на этапе вычисления, а на этапе перевода в обратную польскую запись вроде все ОК. Так что, пока, максимальный балл поставить не могу.

    • 1) Деление исправила.
      2) Я посчитала, что выражение всегда корректное. Исправлено.

  2. Очень сложно читать из-за большой вложенности и тем более написанных в одну строку if. Нет отделения блоков по смыслу. Возможно некоторые куски стоит переписать с switch.
    А так, молодец. ) Всегда перерабатывай посты с течением времени, поможет в профессиональном росте. Старый код всегда хочется переписать когда приходит понимание как сделать лучше.

    • На этом сайте студенты выкладывают свои индивидуальные задания для проверки их преподавателями. Большинство работ поторяют работы с cpp.mazurok.com.
      Не следует ожидать, что студенты будут откликаться на просьбы рассмотреть что-либо интересное вам. Тем более через 5 лет после сдачи экзамена.
      Просто поищмие в мнтернете, в документации по API или посмотрите исходники.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *