Здравствуйте , подскажите пожалуйста как решить вот эту задачу :
Создать приложение для вычисления значения арифметического выражения, которое может включать в себя действительные числа, а также круглые скобки и следующие операции: +, -, *, /, ^ (возведение в степень). Вычисления должны производиться с учетом скобок и приоритетов используемых операций.
lazybiz
Бинарные деревья тебе в помощь:
Ссылка скрыта от гостей
Guest
Вот готовый код этой программы
#include #include #include using namespace std; double expression(); double term(); double power(); double factor(); double number(); int main() < double n; cout double expression() < double result; char operation; result = term(); while (true) < operation = cin.get(); switch (operation) < case ‘+’: result += term(); break; case ‘-‘: result -= term(); break; default: cin.putback(operation); return result; >> > double term() < double result; char operation; double temp; result = power(); while (true) < operation =cin.get(); switch (operation) < case ‘*’: result *= power(); break; case ‘/’: temp = power(); if (temp == 0.0) < cout result /= temp; break; default: cin.putback(operation); return result; > > > double power() < double result; char operation; vector < double >args; args.push_back(factor()); while (true) < operation = cin.get(); while (operation == ‘ ‘) operation = cin.get(); if (operation == ‘^’) args.push_back(factor()); else < cin.putback(operation); break; >> for (int i = args.size() — 1; i > 0; i—) args[i — 1] = pow(args[i — 1], args[i]); return args[0]; > double factor() < double result; char bracket; int sign = 1; bracket = std::cin.get(); while (bracket == ‘ ‘) bracket = cin.get(); switch (bracket) < case ‘-‘: sign = -1; case ‘+’: bracket = cin.get(); break; >while (bracket == ‘ ‘) bracket = cin.get(); if (bracket == ‘(‘) < result = expression(); bracket = std::cin.get(); if (bracket != ‘)’) < cout > else < cin.putback(bracket); result = number(); >return sign * result; > double number() < double result = 0.0; char digit; double k = 10.0; int sign = 1; digit = cin.get(); switch (digit) < case ‘-‘: sign = -1; break; default: if (digit != ‘+’) cin.putback(digit); break; >while (true) < digit =cin.get(); while (digit == ‘ ‘) digit = cin.get(); if (digit >= ‘0’ digit > digit = cin.get(); if (digit == ‘.’) < while (true) < digit =cin.get(); while (digit == ‘ ‘) digit = cin.get(); if (digit >= ‘0’ digit else < cin.putback(digit); break; >> > else cin.putback(digit); return sign * result; >
можете пожалуйста объяснить зачем и что делают вот эти строчки :
Операторы. Арифметические операции с числами. C++ для начинающих. Урок #8.
double expression(); double term(); double power(); double factor(); double number();
Источник: codeby.net
ОПЕРАТОРЫ. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ С ЧИСЛАМИ В C# | C# ОТ НОВИЧКА К ПРОФЕССИОНАЛУ | Урок # 8
Алгоритм вычисления арифметического выражения в виде строки
В нашей славной компании есть очень хорошая, стимулирующая система т.н. грейдов: раз в полгода, любой разработчик может повысить свой грейд, что влечет за собой увеличение зарплаты. Другими словами, грейд — это аттестация. Хочешь увеличить зарплату?
Раз в полгода можешь аттестоваться на следующую ступень, и расти от джуна до сеньора (за один раз можно перепрыгнуть не более, чем на две ступени). Аттестация проходит в дружелюбной форме, вопросы выложены в базе знаний, никакой бюрократической волокиты нет. Условием для допуска к аттестации служит решение алгоритмической задачи.
И вот я аттестовываюсь, и мне дают задачу: вычислить арифметическое выражение в виде строки. Да фигня вопрос, скажете вы (как и я в начале). Все это давно описано, и ничего сложного здесь нет. Вы будете одновременно правы и неправы. Вопрос то, конечно фигня, но это алгоритмическая задача.
Готовые библиотеки использовать нельзя, нужно написать именно алгоритмическое решение. И окунулся я в мир операндов, операторов, как бинарных, так и унарных. И как все это красиво распарсить, как не запутаться со скобками, и… самым коварным оказался унарный минус.
Решение писать будем на php.
Чего-то нового в этой задаче, конечно же, нет. После недолгого гугления мы находим, что для разбора арифметического выражения в виде строки, машиной, лучше всего подходит Обратная польская запись. Материалов по ОПЗ много, разбирать её подробно смысла нет. Например, ссылка на вики.
Пример записи в ОПЗ: 3 4 2 + *
В упрощенном виде можно сказать, что ОПЗ — это запись арифметического выражения, в котором операторы записываются после операндов, и в котором нет скобок.
Под операндами мы понимаем вещественные числа, под операторами — символы арифметических операций +, -, *, /, ^
Почему ОПЗ так хороша для машинных вычислений?
Да потому, что в выражении нет скобок, и машине не надо производить лишних действий. Есть только операнды и операторы. Причем операторы всегда пишутся после операндов (постфиксная запись).
Машина линейно идет по строке, если попалось число, то кладем его в стек, иначе, если оператор бинарный, берем из стека правый операнд, берем из стека левый операнд, вычисленное значение кладем в стек. Когда дойдем до конца строки, достаем из стека результат вычислений.
В упрощенном виде (без проверок) это выглядит так:
$right = array_pop($stack); $left = array_pop($stack); switch ($item) < case ‘-‘: $stack[] = $left — $right; break; case ‘+’: $stack[] = $left + $right; break; case ‘*’: $stack[] = $left * $right; break; case ‘/’: $stack[] = $left / $right; break; case ‘^’: $stack[] = $left ** $right; break; >> // результат вычисления арифметического выражения echo $stack[0] . PHP_EOL;
Все вроде просто, понятно, пока мы не продолжим читать про ОПЗ дальше. Цитата из вики:
В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций
Т.е. знак — (минус) мы можем использовать только как оператор вычитания. Для обозначения унарного минуса в ОПЗ, мы его использовать не можем.
Нам прямо предписывается использовать для обозначения унарного минуса любой свой придуманный символ. Давайте договоримся, что это будет тильда ~ .
Более того — унарный оператор в ОПЗ имеет наивысший приоритет (в данной статье мы будем говорить про унарный минус)!
Что за нафиг? Почему какому-то несчастному оператору (унарный минус), уделяется столько внимания? Мы должны придумать для него специальный символ, и вдобавок ко всему у него еще и наивысший приоритет при разборе выражения?
Ну, с приоритетом понятно — действительно, прежде чем вычислять выражение, мы, в первую очередь, должны разобраться с положительными и отрицательными числами.
Разбираемся дальше. Для этого примем (вспомним) два постулата:
- Любое число, в памяти машины, хранится в виде байт-кода. Отрицательное число определяется значением старшего бита
- Для машины символ минус — это всегда оператор вычитания. Ни о каких унарных минусах машина не знает
Что из этого следует? Давайте рассмотрим простейший пример:
$a = -2
Что происходит в данном примере, с точки зрения машины?
Переменной $a необходимо присвоить отрицательное значение числа 2.
Для машины минус — это оператор вычитания. Операция бинарная. Справа 2, а слева ничего нет. Т.е. слева 0.
Т.е. в $a попадет результат вычисления выражения 0 — 2 . Вычитать машина умеет прекрасно, в память машины будет записано верное отрицательное число.
Смотрим дальше. Есть выражение с двумя унарными минусами, например —2 .
Как его должна считать машина? Если следовать нашей логике, то так: 0 — (0 — 2) .
Т.е. унарный минус — это не просто вычитание операнда из ноля, но еще и правоассоциативная арифметическая операция, как и оператор возведения в степень.
Прежде чем идти дальше, давайте дадим определение унарному минусу в инфиксном арифметическом выражении:
- Унарный минус — это оператор — (минус), перед которым в арифметическом выражении всегда стоит не число, и не закрывающая скобка
Подведем промежуточные итоги
- Мы выяснили, что для машинного разбора строки с арифметическим выражением необходимо его привести к ОПЗ (постфиксная запись)
- Мы разобрались почему у унарного минуса наивысший приоритет, и мы запомнили, что у него должен быть свой символ (у нас это тильда ~)
Нам осталось разобрать алгоритм приведения инфиксного арифметического выражения к постфиксному
Опять же всё давно изобретено до нас, использовать мы будет классический алгоритм сортировочной станции. Просто распишем его максимально подробно и понятно.
Прежде чем приступить к описанию алгоритма уточним давно известный алгоритм приоритета стековых операций.
В нашем случае операторы и приоритеты стековых операций будут выглядеть так:
private const UNARY_MINUS = ‘~’; private const OPEN_BRACKET = ‘(‘; private const CLOSE_BRACKET = ‘)’; private const MINUS = ‘-‘; private const PLUS = ‘+’; private const DIVISION = ‘/’; private const MULTIPLICATION = ‘*’; private const EXPONENTIATION = ‘^’; private const PRIORITY = [ self::OPEN_BRACKET => 0, self::CLOSE_BRACKET => null, self::PLUS => 2, self::MINUS => 2, self::MULTIPLICATION => 3, self::DIVISION => 3, self::EXPONENTIATION => 4, self::UNARY_MINUS => 5 ];
Также необходимо определить правоассоциативные арифметические операции:
private const RIGHT_ASSOCIATIVE_EXPRESSION = [ self::EXPONENTIATION, self::UNARY_MINUS ];
В процессе разбора строки мы будем использовать понятие выходная строка (постфиксное выражение) и стек.
Алгоритм приведения инфиксной записи к постфиксной
Если при разборе строки нам встретилось число, то помещаем его в выходную строку
Иначе
- Если в стеке пусто, или нам попалась открывающая скобка — помещаем оператор в стек
- Если нам попался правоассоциативный оператор, и на вершине стека лежит такой же оператор, то ничего не делаем, просто добавляем оператор в стек
Иначе
- Если нам попалась не закрывающая скобка, то выталкиваем из стека, в выходную строку, операторы с бОльшим, или равным приоритетом. Если, при выталкивании из стека, нам попался оператор с мЕньшим приоритетом — останавливаемся.
Добавляем оператор на вершину стека. - Если нам попалась закрывающая скобка, то выталкиваем из стека, в выходную строку, все операторы до первой открывающей скобки. Открывающую скобку из стека удаляем
- Если строка закончилась — выталкиваем все операторы из стека в строку вывода
Собственно всё. Данный алгоритм можно реализовать на любом ЯП.
Давайте приведём «вручную» выражение 2 * (2 + -2 ^ 2 ^ 3) — 1 к ОПЗ, и вычислим его
Приводим к постфиксной записи
Определим переменные для вычисления
$stack = []; $outString = [];
Разбираем строку 2 * (2 + -2 ^ 2 ^ 3) — 1
-
Первый символ в строке 2, это число — помещаем его в выходную строку
$outString = [2];
$outString = [2]; $stack = [‘*’];
$outString = [2]; $stack = [‘*’, ‘(‘];
$outString = [2, 2]; $stack = [‘*’, ‘(‘];
$outString = [2, 2]; $stack = [‘*’, ‘(‘, ‘+’];
$outString = [2, 2]; $stack = [‘*’, ‘(‘, ‘+’, ‘~’];
$outString = [2, 2, 2]; $stack = [‘*’, ‘(‘, ‘+’, ‘~’];
$outString = [2, 2, 2, ‘~’]; $stack = [‘*’, ‘(‘, ‘+’, ‘^’];
И так далее… — если число, то помещаем в строку вывода, если оператор, то пытаемся вытолкнуть из стека, в строку вывода, другие операторы, сам оператор ставим на вершину стека. Всё согласно алгоритму выше.
Открывающая скобка имеет наименьший приоритет, её вытолкнуть нельзя, она должна быть уничтожена закрывающей скобкой. Приоритеты операторов мы также определили.
В конечном итоге мы получаем постфиксное выражение 2 2 2 ~ 2 3 ^ ^ + * 1 —
Ну, дальше, как было написано выше, дело техники.
- Мы идем по строке с постфиксным выражением.
- Если нам попалось число, то кладём его в стек.
- Если нам попался унарный минус, то приводим число на вершине стека, к отрицательному значению (0 минус операнд).
Если нам попался бинарный оператор
- берем с вершины стека число — это правый операнд
- берем с вершины стека число — это левый операнд
- вычисляем выражение, кладем его в стек
Если строка закончилась, возвращаем вычисленное значение из стека (если арифметическое выражение верно, то в стеке останется один элемент).
Полное решение на языке php
Спойлер
Пример использования класса Calculate
postfixString) < echo ‘Исходное выражение: ‘ . $expression; echo ‘Строка в постфиксной записи (~ — это унарный минус): ‘ . $calc->postfixString . PHP_EOL; echo ‘Результат вычисления постфиксной записи: ‘ . $calc->result . PHP_EOL; > else < echo $calc->result . PHP_EOL; >
Листинг класса Calculate
Подведем итоги
Для красивого вычисления арифметического выражения в виде строки необходимо:
- Разобраться что такое Обратная польская запись, и почему она идеально подходит для машинных вычислений
- Привести арифметическое выражение к ОПЗ, и вычислить его
И для первого, и для второго пункта ключевым понятием является стек — последовательность, организованная по принципу — последний зашел, первый вышел. На вершине стека всегда находится его последний элемент.
Источник: habr.com
Вопрос Составить программу вычисления значения арифметического выражения!!
Требования к программе:
— Числовые значения переменных ввести с клавиатуры;
— Значения входных переменных и окончательные результаты напечатать.
alexvip2008
Регистрация 2 Фев 2013 Сообщения 73 Репутация 0 Спасибо 0 Монет 0
Саша, на каком языке программирования? Напечатать на экране или на принтере? Уже из-за этих косяков не помогу
dark
Регистрация 8 Мар 2013 Сообщения 46 Репутация 0 Спасибо 0 Монет 0
Всё очень плохо, судя по коду
Похожие темы
- gaaa
- 17 Фев 2023
- Общение Python мододелов
Ответы 4 Просмотры 316
Ответы 6 Просмотры 682
- 4eJIoBe4eHa
- 23 Окт 2016
- Компьютерные вопросы
Ответы 0 Просмотры 371
Ответы 5 Просмотры 378
- alkatraz
- 27 Июл 2017
- Компьютерные вопросы
Ответы 4 Просмотры 839
Поделиться:
- Крипта, интернет, софт
- Разработка игрового ПО
- Компьютерные вопросы
О нас
4cheaT один из старейших форумов рунета. Мы работаем, чтобы вы могли отдыхать с комфортом. Наш форум посвящён онлайн играм, игровым разработкам и модификациям. На нашем онлайн рынке вы можете купить и продать любые онлайн ценности и услуги. Гейминг объединяет криптанов, программистов и вебмастеров!
Разделы форума
Важное
Мы в соц. сетях
- Обратная связь
- Условия и правила
- Политика конфиденциальности
- Помощь
- RSS
На данном сайте используются файлы cookie, чтобы персонализировать контент и сохранить Ваш вход в систему, если Вы зарегистрируетесь.
Продолжая использовать этот сайт, Вы соглашаетесь на использование наших файлов cookie.
Источник: 4cht.com