Как сделать программу вычисления выражения

Добавил пользователь Евгений Кузнецов
Обновлено: 05.10.2024

В нашей славной компании есть очень хорошая, стимулирующая система т.н. грейдов: раз в полгода, любой разработчик может повысить свой грейд, что влечет за собой увеличение зарплаты. Другими словами, грейд — это аттестация. Хочешь увеличить зарплату? Раз в полгода можешь аттестоваться на следующую ступень, и расти от джуна до сеньора (за один раз можно перепрыгнуть не более, чем на две ступени). Аттестация проходит в дружелюбной форме, вопросы выложены в базе знаний, никакой бюрократической волокиты нет. Условием для допуска к аттестации служит решение алгоритмической задачи.

И вот я аттестовываюсь, и мне дают задачу: вычислить арифметическое выражение в виде строки. Да фигня вопрос, скажете вы (как и я в начале). Все это давно описано, и ничего сложного здесь нет. Вы будете одновременно правы и неправы. Вопрос то, конечно фигня, но это алгоритмическая задача. Готовые библиотеки использовать нельзя, нужно написать именно алгоритмическое решение. И окунулся я в мир операндов, операторов, как бинарных, так и унарных. И как все это красиво распарсить, как не запутаться со скобками, и… самым коварным оказался унарный минус.

Решение писать будем на php.

Чего-то нового в этой задаче, конечно же, нет. После недолгого гугления мы находим, что для разбора арифметического выражения в виде строки, машиной, лучше всего подходит Обратная польская запись. Материалов по ОПЗ много, разбирать её подробно смысла нет. Например, ссылка на вики.

Пример записи в ОПЗ: 3 4 2 + *

В упрощенном виде можно сказать, что ОПЗ — это запись арифметического выражения, в котором операторы записываются после операндов, и в котором нет скобок.
Под операндами мы понимаем вещественные числа, под операторами — символы арифметических операций +, -, *, /, ^

Почему ОПЗ так хороша для машинных вычислений?

Да потому, что в выражении нет скобок, и машине не надо производить лишних действий. Есть только операнды и операторы. Причем операторы всегда пишутся после операндов (постфиксная запись).
Машина линейно идет по строке, если попалось число, то кладем его в стек, иначе, если оператор бинарный, берем из стека правый операнд, берем из стека левый операнд, вычисленное значение кладем в стек. Когда дойдем до конца строки, достаем из стека результат вычислений.

В упрощенном виде (без проверок) это выглядит так:

Все вроде просто, понятно, пока мы не продолжим читать про ОПЗ дальше. Цитата из вики:

В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций

Т.е. знак - (минус) мы можем использовать только как оператор вычитания. Для обозначения унарного минуса в ОПЗ, мы его использовать не можем.
Нам прямо предписывается использовать для обозначения унарного минуса любой свой придуманный символ. Давайте договоримся, что это будет тильда ~ .
Более того — унарный оператор в ОПЗ имеет наивысший приоритет (в данной статье мы будем говорить про унарный минус)!

Что за нафиг? Почему какому-то несчастному оператору (унарный минус), уделяется столько внимания? Мы должны придумать для него специальный символ, и вдобавок ко всему у него еще и наивысший приоритет при разборе выражения?

Ну, с приоритетом понятно — действительно, прежде чем вычислять выражение, мы, в первую очередь, должны разобраться с положительными и отрицательными числами.

Разбираемся дальше. Для этого примем (вспомним) два постулата:

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

Что из этого следует? Давайте рассмотрим простейший пример:
$a = -2
Что происходит в данном примере, с точки зрения машины?
Переменной $a необходимо присвоить отрицательное значение числа 2.
Для машины минус — это оператор вычитания. Операция бинарная. Справа 2, а слева ничего нет. Т.е. слева 0.
Т.е. в $a попадет результат вычисления выражения 0 - 2 . Вычитать машина умеет прекрасно, в память машины будет записано верное отрицательное число.

Смотрим дальше. Есть выражение с двумя унарными минусами, например --2 .
Как его должна считать машина? Если следовать нашей логике, то так: 0 - (0 - 2) .
Т.е. унарный минус — это не просто вычитание операнда из ноля, но еще и правоассоциативная арифметическая операция, как и оператор возведения в степень.

Прежде чем идти дальше, давайте дадим определение унарному минусу в инфиксном арифметическом выражении:

Унарный минус — это оператор - (минус), перед которым в арифметическом выражении всегда стоит не число, и не закрывающая скобка

Подведем промежуточные итоги

Мы выяснили, что для машинного разбора строки с арифметическим выражением необходимо его привести к ОПЗ (постфиксная запись)
Мы разобрались почему у унарного минуса наивысший приоритет, и мы запомнили, что у него должен быть свой символ (у нас это тильда ~)

Нам осталось разобрать алгоритм приведения инфиксного арифметического выражения к постфиксному

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

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

В нашем случае операторы и приоритеты стековых операций будут выглядеть так:

Также необходимо определить правоассоциативные арифметические операции:

В процессе разбора строки мы будем использовать понятие выходная строка (постфиксное выражение) и стек.

Алгоритм приведения инфиксной записи к постфиксной

Если при разборе строки нам встретилось число, то помещаем его в выходную строку

Иначе

Если в стеке пусто, или нам попалась открывающая скобка — помещаем оператор в стек

Если нам попался правоассоциативный оператор, и на вершине стека лежит такой же оператор, то ничего не делаем, просто добавляем оператор в стек

Иначе

Если нам попалась не закрывающая скобка, то выталкиваем из стека, в выходную строку, операторы с бОльшим, или равным приоритетом. Если, при выталкивании из стека, нам попался оператор с мЕньшим приоритетом — останавливаемся.
Добавляем оператор на вершину стека.
Если нам попалась закрывающая скобка, то выталкиваем из стека, в выходную строку, все операторы до первой открывающей скобки. Открывающую скобку из стека удаляем
Если строка закончилась — выталкиваем все операторы из стека в строку вывода

Собственно всё. Данный алгоритм можно реализовать на любом ЯП.

Давайте приведём "вручную" выражение 2 * (2 + -2 ^ 2 ^ 3) - 1 к ОПЗ, и вычислим его

Приводим к постфиксной записи

Определим переменные для вычисления

Разбираем строку 2 * (2 + -2 ^ 2 ^ 3) - 1

Первый символ в строке 2, это число — помещаем его в выходную строку

Следующий символ — это оператор * — помещаем его в стек

Следующий символ — это оператор ( — помещаем его в стек

Следующий символ — это число 2 — помещаем его в выходную строку

Следующий символ — это оператор + — помещаем его в стек

Следующий символ — это оператор унарный минус ~ — помещаем его в стек

Следующий символ — это число 2 — помещаем его в выходную строку

Следующий символ — это оператор ^ — выталкиваем из стека унарный минус, помещаем ^ в стек

И так далее… — если число, то помещаем в строку вывода, если оператор, то пытаемся вытолкнуть из стека, в строку вывода, другие операторы, сам оператор ставим на вершину стека. Всё согласно алгоритму выше.
Открывающая скобка имеет наименьший приоритет, её вытолкнуть нельзя, она должна быть уничтожена закрывающей скобкой. Приоритеты операторов мы также определили.

В конечном итоге мы получаем постфиксное выражение 2 2 2 ~ 2 3 ^ ^ + * 1 -

Ну, дальше, как было написано выше, дело техники.

Мы идем по строке с постфиксным выражением.
Если нам попалось число, то кладём его в стек.
Если нам попался унарный минус, то приводим число на вершине стека, к отрицательному значению (0 минус операнд).

Если нам попался бинарный оператор

берем с вершины стека число — это правый операнд
берем с вершины стека число — это левый операнд
вычисляем выражение, кладем его в стек

Если строка закончилась, возвращаем вычисленное значение из стека (если арифметическое выражение верно, то в стеке останется один элемент).

Полное решение на языке php

Пример использования класса Calculate

Листинг класса Calculate

Подведем итоги

Для красивого вычисления арифметического выражения в виде строки необходимо:

Разобраться что такое Обратная польская запись, и почему она идеально подходит для машинных вычислений
Привести арифметическое выражение к ОПЗ, и вычислить его

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

Требуется написать программу, вычисляющую значение какой-либо функции у = f(x). Допустим, такой:

у = x – 2, если x > 0,
y = 0, если x = 0,
y = |x|, если x y вычисляется по-разному (по разным формулам) в зависимости от значения x .

Такие задачи решаются с помощью конструкции условного оператора if - else . Поскольку в данном случае мы имеем три условия ( x > 0 , x = 0 и x 0 ), то потребуется использование еще вложенной конструкции if - else , т. к. в языке Pascal нет оператора множественного ветвления (оператор case в данном случае не подходит).

В языке программирования Паскаль (да и в других тоже) желательно вложенные конструкции if - else помещать во внешнюю ветку else , а не if . Так проще не запутаться.

Таким образом, алгоритм вычисления значения функции может быть таким:

Если x > 0, то у = x - 2
Иначе (ниже идет вложенная конструкция)
Если x = 0, то y = 0
Иначе y = |x|.

В последнем пункте можно опустить оператор if с проверкой, что x 0 , так как если ход выполнения программы дошел до этого пункта, то x уже другим быть и не может (варианты, когда он больше или равен нулю, уже были исключены).

Для определения модуля (абсолютного значения) переменной можно использовать встроенную функцию abs ( ) языка Pascal. В данном случае можно обойтись и без нее: поскольку уже известно, что x отрицателен, то, чтобы получить положительное число (модуль), нужно его умножить на -1.

%write("расчет первого числа X расчет второго числа Y введите первое число X введите второе число Y расчет первого числа X расчет второго числа Y расчет первого числа X расчет второго числа Y ",Y),nl.

write(Y," Идет за Клинским "),nl,

write(Y1," Идет за Чипсами "),nl,

write(Y2," Идет за Раками "),nl,

write(Y3," Обладает машиной BMW "),nl.

3) По имеющейся схема рассчитать параллельные узлы и общий узел

элемент (symbol, symbol, integer, integer)

общий_узел (symbol, symbol, integer)

паралельное_соединение (symbol, symbol, integer, integer)

элемент (l1, катушка, 1, 12).

элемент (r1, резистор, 1, 11).

элемент (p3, лампочка, 1, 15).

элемент (i1, источник, 1, 12).

элемент (r5, резистор, 14, 9).

элемент (r3, резистор, 11, 9).

элемент (l3, катушка, 11, 9).

элемент (r4, резистор, 14, 11).

элемент (r2, резистор, 12, 8).

элемент (c2, конденсатор, 12, 14).

элемент (p2, лампочка, 12, 9).

элемент (с1, конденсатор, 14, 15).

элемент (p1, лампочка, 8, 14).

паралельное_соединение (Э1, Э2, Узел1, Узел2) :-

элемент (Э1,_,Узел1,Узел2), элемент(Э2,_,Узел1,Узел2), Э1<>Э2;

элемент (Э1,_,Узел1,Узел2), элемент(Э2,_,Узел2,Узел1), Э1<>Э2.

элемент (Э1,_,Узел1,_), элемент(Э2,_,Узел1,_), Э1<>Э2;

элемент (Э1,_,Узел1,_), элемент(Э2,_,_,Узел1), Э1<>Э2;

элемент (Э1,_,_,Узел1), элемент(Э2,_,Узел1,_), Э1<>Э2;

элемент (Э1,_,_,Узел1), элемент(Э2,_,_,Узел1), Э1<>Э2.

паралельное_соединение (Э1, Э2, Узел1, Узел2).

4) А) Какие ответы даст программа, содержащая следующие факты и правила:

Цели: р(Х); р(Х), р(У); р(Х), !, р(У).

Б) Составить программу решения двухступенчатой функции, используя бинарное отношение f(X,Y) , без применения отсечений; применив зеленые отсечения в двух первых правилах; используя красные отсечения.

Правило 1: если X 3 и X =6, то Y=4.

В)Составить программу определения наименьшего (наибольшего) из двух чисел (X,Y) без применения отсечений и с применением зеленых и красных отсечений.

Г)Выполнить задания согласно вариантам, используя предикаты fail, cut (!).

р(Х), !, р(У)

f(X,Y):-X Y,write(X, "больше чем ",Y,"\n").

сравнение(X,Y):-Y>X,write(Y, " больше чем ",X,"\n").

сравнение(X,Y):-X=Y,write(X, " и ",Y," - равны").

сравнение(X,Y):-X>Y. write(X, "больше чем ",Y,"\n").

сравнение(X,Y):-Y>X. write(Y, "больше чем",X,"\n").

сравнение(X,Y):-write(X, " и ",Y," - равны").

Г) Составить расписание всех игр (дома и в гостях) для группы из 4-х футбольных команд.

write("команда",A,"играет с командой",B,"\n"),

5)А) По заданному взаимоотношению или объекту составить модель знаний в виде семантической сети и изобразить ее графически. В семантической сети должно быть не менее 7-и элементов. Каждый элемент должен характеризоваться свойствами или функциями (3 и больше).

Например, при построении семантической сети арки рассматривать свойства колон (опора 1 сделана из кирпича, опора 2 – металл, перекладина деревянная). Тогда в разделе цели возможно определить материалы требуемые для построения арки.

Б)Полученную модель знаний реализовать в виде программы на языке Prolog.

В)Составить цели (не менее 4 шт.), которые можно достигнуть по вашей модели знаний. При реализации цели должно быть задействовано как можно большее количество связей сети.

Cоставьте программу для решения задачи: вычислите площадь поверхности прямоугольного параллелепипеда, если длины его ребер а, b, с вводятся с клавиатуры и а=9, b=7,5, с=5.

Вариант 2

Самостоятельно найдите примеры из Help для реализации трех математических функций pow, sin, logl0. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 14,26, у = -1,22, z =3,510- 2 .

Cоставьте программу для решения задачи: вычислите площадь поверхности прямоугольного параллелепипеда, если даны длины его ребер а, b, с (вводятся с клавиатуры).

Вариант 3

Составьте программу для вычисления выражения:

при х= 3,74∙10 -2 , у = 0,825, z=0,16∙10 -2 .

Составьте программу для решения задачи: введите длины сторон треугольника a, b, c c клавиатуры и найдите длины его медиан по формуле , где т_ь — это медиана, проведенная из вершины В.

Вариант 4

Самостоятельно найдите примеры из Help для реализации трех математических функций cosh, exp, fabs. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 0,4∙10 4 , у = -0,875, z=0,475∙10 -3 .

Составьте программу для решения задачи: введите длины сторон треугольника а, b, с с клавиатуры и найдите длины высот треугольника по формуле

, где h_b – это высота, проведенная из вершины B, p –это полупериметр.

Вариант 5

Самостоятельно найдите примеры из Help для реализации трех математических функций fmod, log, logl0. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= -15,246, у = 4,642, z =20,001∙10 2 .

Составьте программу для решения задачи: введите длины сторон треугольника а, b, с с клавиатуры и найдите длины его биссектрис по формуле

где l_а — это биссектриса, проведенная из вершины А, р — полупериметр

Вариант 6

Самостоятельно найдите примеры из Help для реализации трех математических функций pow, pow10, sin. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 16,55∙10 -3 , у = -2,75, z=0,15.

Составьте программу для решения задачи: введите с клавиатуры координаты точки А(х₁ у₁ z₁),которая лежит на поверхности шара, и координаты точки В(х₂, у₂, z₂), которая является центром шара. Найдите объем шара.

Вариант 7

Самостоятельно найдите примеры из Help для реализации трех математических функций sinh, sqrt, tan. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 0,1722, у = 6,33, z=3,2510 -4 .

Составьте программу для решения задачи: найдите периметр трапеции с вершинами в точках А(х₁,0), В(х₂,0), С(х₂,y_з), D(x₁,y₄). Значения х₁ х₂, у₃, у₄введите с клавиатуры.

Вариант 8

Самостоятельно найдите примеры из Help для реализации трех математических функций pow10, exp, asin. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= -2,235∙10 -2 , у = 2,23, z=15,221.

Составьте программу для решения задачи: найдите длину окружности, которая проходит через точку А(х₁ у₁) и центр которой находится в точке В(х₂, у₂). Значения х₁ у₁ х₂, у₂ введите с клавиатуры.

Вариант 9

Самостоятельно найдите примеры из Help для реализации трех математических функций gloor, ceil, tanh. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 1,825∙10 -2 , у = 18,225, z=-3,298∙10 -2 .

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

Вариант 10

Составьте программу для вычисления выражения:

при х= 3,251, у = 0,225, z =0,4660 -4 .

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

Вариант 11

Самостоятельно найдите примеры из Help для реализации трех математических функций ceil, cos, fmod.

Составьте программу для вычисления выражения:

при x=17,421, y=10,365∙10 -3 , z =0,828∙10 5 .

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

Вариант 12

Самостоятельно найдите примеры из Help для реализации трех математических функций sin, log, abs. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 12,3∙10 -1 , у= 15,4, z = 0,252∙10 3 .

Составьте программу для решения задачи: найдите объем шара, если задан его радиус. Значение радиуса введите с клавиатуры.

Вариант 13

Самостоятельно найдите примеры из Help для реализации трех математических функций cos, atan, ceil. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 2,444, у = 0,869∙10 -2 , z=-0,13∙10 -2 .

Cоставьте программу для решения задачи: вычислите площадь поверхности шара, если задан его радиус.Значение радиуса введите с клавиатуры.

Вариант 14

Самостоятельно найдите примеры из Help для реализации трех математических функций pow, ceil, logl0. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 14,26, у = -0,92, z=3,510- 2 .

Cоставьте программу для решения задачи: вычислите длину ребра куба имеющего объем равный объему прямоугольного параллелепипеда. Длины его ребер а, b, с вводятся с клавиатуры.

Вариант 15

Составьте программу для вычисления выражения:

при х= 3,251, у = 0,225, z =0,46.

Cоставьте программу для решения задачи: вычислите на сколько больше объем шара радиуса R объема куба с такойже длиной ребра. Величина Rвводятся с клавиатуры.

Вариант 16

Самостоятельно найдите примеры из Help для реализации трех математических функций pow, cos, lnl0. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 1,23, у= 15,4, z = 0,252∙10 3 .

Введите два положительных числа, которые соответствуют размерам диагоналей ромба. Найти периметр P и площадь S.

Вариант 17

Самостоятельно найдите примеры из Help для реализации трех математических функций ceil, cos, fmod. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при x=17,421, y=10,365∙10 -3 , z =0,828∙10 5 .

Введите три положительных числа, которые соответствуют размерам сторон треугольника. Найти периметр P и площадь S.

Вариант 18

Самостоятельно найдите примеры из Help для реализации трех математических функций log10, exp, fabs. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= -2,23∙10 -2 , у = 2,23, z=15,21.

Введите три положительных числа, которые соответствуют размерам сторон трапеции. Вычислите допустимые размеры четвертой стороны.

Вариант 19

Самостоятельно найдите примеры из Help для реализации трех математических функций pow, abs, sin. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 2,351, у = 0,265, z =4,46.

Введите три положительных числа, которые соответствуют размерам катетов прямоугольного треугольника. Найти его площадь и гипотенузу.

Вариант 20

Самостоятельно найдите примеры из Help для реализации трех математических функций pow, cos, ln. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 14,26, у = -1,22, z =3,510 -2 .

Cоставьте программу для решения задачи: вычислите площадь поверхности прямоугольного параллелепипеда, если длины его ребер а, b, с вводятся с клавиатуры

Вариант 21

Самостоятельно найдите примеры из Help для реализации трех математических функций cosh, log, exp. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 0,4∙10 4 , у = -0,875, z=0,475∙10 -3 .

Найти среднее арифметическое трех вещественных чисел, заданных с клавиатуры.

Вариант 22

Самостоятельно найдите примеры из Help для реализации трех математических функций ceil, cos, fmod.

Составьте программу для вычисления выражения:

при x=17,421, y=10,365, z =8,28.

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

Вариант 23

Самостоятельно найдите примеры из Help для реализации трех математических функций acos, tan, ceil. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 2,444, у = 0,869∙10 -2 , z=-0,13∙10 -2 .

Cоставьте программу для решения задачи: вычислите площадь поверхности шара, если задан его радиус. Значение радиуса введите с клавиатуры.

Вариант 24

Самостоятельно найдите примеры из Help для реализации трех математических функций atan2, tan, fabs. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 0,444, у = 0,869∙10 -2 , z=-0,13∙10 -2 .

Cоставьте программу для решения задачи: вычислите площадь поверхности шара, если задан его радиус. Значение радиуса введите с клавиатуры.

Вариант 25

Самостоятельно найдите примеры из Help для реализации трех математических функций atan2, tan, ceil. Создайте программу в которой используются эти функции.

Составьте программу для вычисления выражения:

при х= 2,444, у = 0,869∙10 -2 , z=-0,13∙10 -2 .

Cоставьте программу для решения задачи: вычислите площадь боковой поверхности конуса, если изкестны его высота и радиус основания. Параметры конуса вводятся с клавиатуры.

Контрольные вопросы

Что такое линейный алгоритм? Приведите пример.

Какая программа называется программой с линейной структурой?

Что представляет собой программа на языке C++?

С какой целью используются заголовочные файлы в программе на языке C++?

Какие операторы и функции C++ вы использовали при выполнении индивидуального задания?

Как было выполнено тестирование корректности формирования (вычисления) результативного значения работы разработанного приложения?

Читайте также: