Программируем калькулятор со скобками и приоритетами действий, используя стек
ฝัง
- เผยแพร่เมื่อ 24 ส.ค. 2024
- Меня попросили помочь разобраться с реализацией калькулятора, который понимает приоритеты операций и вложенные скобки. В этом видео я рассказываю о подходе к этой задаче, описываю алгоритм, по которому должна работать такая программа.
В результате получилось понятное объяснение, по которому ученик успешно выполнил задание.
Кроме основной темы, в видео даётся рекомендация о реализации структуры данных "стек" на языке Python.
И да. Когда пишешь эту программку самый первый раз, то можно считать, что все числа и знаки разделены пробелом, это проще парсить. Тогда можно просто разбить строку в массив подстрок командой split.
---------------------------
Моя основная тема - программирование для начинающих. Я рассказываю о том, как решать задачки и делать проекты. Также даю советы об изучении английского языка, математики и развитии других навыков, полезных для ребёнка.
Подписывайтесь на меня в:
* ВК: progsch...
* Фейсбуке: / eduoja.ru
* Инстаграме: / eduoja
Ставьте лайки и оставляйте комментарии. Ведь чем больше будет комментариев, тем интереснее и полезнее смогу делать следующие выпуски.
#python #programming #programmingforchildren #программирование #учимсяпрограммировать #программированиедетям #калькулятор #стек #алгоритм #питон
большое спасибо! устаканилось вроде в голове. сейчас буду реализовывать на СИ.
дай Бог Вам здоровья!
Супер. Понятное сведение в одном коротком видео объяснения стека, польской нотациии алгоритма калькулятора
Боже, чувак, ты добавляешь в стэк кругляшочки и вычисляешь штуки из стрОки, но это максимально простой, понятный, без всякой лишней трепни урок - учителям всяких гикбрэйнс у тебя бы поучиться.
от плавца школы 21 оффициальное спасибо
UPD 2020 Kazan
да прибудет с вами eval_expr
А что делать тем, кому любопытно, а как же написан eval?
@@obrazovaja ы
@@obrazovaja каждый решит для себя сам
Спасибо огромное, с помощью этого алгоритма наконец-то смог собрать сложное дерево из плоских значений
Благодарю за информацию о подобном алгоритме и Вашу работу
Уже пересмотрел все видео с обратной польской нотацией что сумел найти. Но это видео объясняет её лучше всех.
Офигенный видос, мне очень помог
благодарен вам. алгоритм оказался довольно несложным а реализации с такими подробными обьяснениями.
Шикарно! Т.е. здесьпо сути преобразование в обратную польскую нотацию.
Спасибо за видео, я второй день работаю с питоном и смог написать калькулятор, благодаря Вашему объяснению.
Теперь пиши калькулятор матричных выражений)
В python есть готовая функция eval, которая выполняет выражение из строки
@@dowlso Интересно было бы посмотреть, как этим методом вы реализуете поддержку выражений отличных от выражений языка питон. Например, определить операцию ^ как возведение в степень, или запретить синусы, и т.д.
Спасибо тебе Добрый человек!!!!
Очень классное объяснение!
Спасибо! Очень качественный урок!))
От имени 1ой группы 1ого потока 1 ого курса ВМК МГУ большое спасибо
ЧУВАК, СПАСИБО ОГРОМНОЕ!
Огонь, спасибо большое!
Случайно набрел на видео. Автор - мы мой кумир. Все рассказал за один заход. Пример супер удачный - выловил кучу багов на нем!
Замечу, что т.к. стека два, то функция top(a) не нужна, можно в лоб смотреть operations_stack[-1]
top() - это интерфейс стека. Абстрактный стэк не предполагает возможность обращаться к произвольному элементу по индексу, потому что стэк может быть реализован поверх структуры, в которой обращение по индексу неэффективно.
Поэтому алгоритм, который использует стэк, должен пользоваться функцией top, не завязываясь на её реализацию.
Красавчик, очень эффективно объяснил
Как я понимаю, это можно сделать одним стеком, а так урок великолепен
Решал совершенно по другому. У меня идет разбитие на отдельные строчки в список того что в скобках, и назначения приоритета в зависимости от вложенности скобок. Потом считаются в обратном порядке вложенности и приоритета.
За то сам придумал. =)
Теперь хочу выяснить какой алгоритм будет быстрее работать =)
like по-любому
мда целую неделю это видео вгоняло меня в черную тоску пока не удалось это реализовать))
учитель красавчик
Какой алгоритм действий будет если в выражении присутствуют числа с унарным минусом?
Допустим, что мы пока не хотим переходить к формальной грамматике. Тогда просто заметим, что унарный минус не может появиться абы где. Он появляется только в том месте, где мы ждём открывающую скобку или число. Таким образом мы не можем его спутать с обычным минусом. Придумываем ему обозначение, под которым будем класть унарный минус в стек операций. Тогда прежде, чем положить очередное число в стек чисел (прочитанное или после вычислений), мы сначала проверяем, нет ли на вершине стека операций унарного минуса. Если есть, то забираем его оттуда, а число меняем на противоположное по знаку.
Но на данном этапе можно уже задуматься о формальной грамматике, почитать что-нибудь про это, и тогда вопросов станет меньше... или больше.
спасибобобобобобо
Интересно посмотреть реализацию в Python
Согласен! С нетерпением ждём ссылки на ваш код ;-)
@@obrazovaja ахахаха
Кстати, на: eval - встроенная функция)
А если кто сделал таки на C++, то скиньте пожалуйста
Премия учитель года!
Это мы всегда рады. Спасибо!
спасибо!
Поучительно, но в примере показан вариант, когда в строке символов, все числа занимают 1 байт(всего 1 цифра). А как быть, когда числа состоят из двух и более цифр?
Самый простой способ - это отделять всё друг от друга пробелами. Пока не встретите следующий пробел, считаете, что продолжаете читать цифры того же самого числа. Тогда можно будет даже воспользоваться стандартной функцией scanf или sscanf для Си или их аналогами в других языках.
В общем виде эта задача называется «лексический анализ», в видео об этом упоминается вскольз. Нужно из сплошного текста выделить единицы смысла - так называемые токены - числа, знаки и скобки.
Первый способ - это если вы скармливаете строку с текстом некоторой функции и она разбивает её на токены. В итоге у вас получается массив, в котором уже не буковки, а сущности для работы калькулятора: числа, знаки и скобки. Думаю, для начала - этот способ реализовать проще вего. (кстати, если всё разделено пробелами, то можно сделать строке банальный split)
Либо можно совместить процесс чтения строки и выделения лексем. Например, сделать функцию, которая принимает на вход строку str и позицию, где вы остановились, и отдаёт вам очередной токен и позицию следующего за ним токена. Т.е. что-то вида: getTokenAt(str, position) -> [value, next_position], где value - это число или знак, а next_position - это позиция следующего токена, которую вы отправите в функцию getTokenAt в следующий раз, "str" у вас всегда одна и та же. Этот способ хорош тем, что его можно доработать для потокового ввода, когда можно читать со входа в реальном режиме.
Для создания токенайзера нашего калькулятора достаточно базовых навыков программирования и это полезное упражнение.
В реальном мире для лексического анализа есть универсальные анализаторы, в которых допустимые лексемы задаются регулярными выражениями. Например, лексемы нашего языка можно описать так: Num(\d+(\.\d+)?), Op([+-*/()])
Не понятно с момента второй скобки. Почему мы просто вычисляем, пока не встретим скобку? А если бы там было (1+2/2)?
Тогда бы в тот момент, когда бы мы добрались до закрывающей скобки, то в стеке с числами было бы: ...,1, 2, 2; а в стеке со знаками было бы: ..., (, +, /;
И значит нам пришлось бы взять из стека две двойки и последнее деление, поделить, положить единицу обратно в стек, потом взять две единицы и плюсик, сложить и положить двойку обратно в стек, потом увидеть скобочку и просто её выкинуть вместе с закрывающей парной.
См. картинку: take.ms/W9ZEM
@@obrazovaja спасибо!
Игрокам GM привет. Не ожидал увидеть здеся знакомый ник из 2014 года
Спасибо за видео, я всё понял. Как можно это сделать с одним стеком?
Это вам упражнение для самостоятельной работы
как добавить приоритет операций в программму?
Я не уверен, что правильно понял ваш вопрос, но попробую ответить как понял.
В видео на 2:12 оформился объект с приоритетами. Записываете его в переменную: p = {'+': 1, '*': 2}.
Тогда p['+'] - это 1, а p['*'] - это 2. Допустим, вы берёе операцию из стэка (переменная a) и хотите сравнить её со следующей операцией из выражения (переменная b), тогда вы сравниваете p[a] и p[b]. Какое число выше, та операция имеет больший приоритет.
С П А С И Б О !
топ!
Это двухстековый алгоритм Дейкстры или как это официально назвать? Похоже на алгоритм сортировочной станции, только мы на ходу вычисления делаем, а не переписываем все выражение в обратную польскую нотацию и только потом вычисляем.
Два стека здесь лишь для удобства рассказа. Можно всё то же через один стек сделать. Т.е. по сути стек один.
а что делать если в строке встретилось несколько знаков умножить подряд, два, три? Или несколько знаков плюс и минус подряд - ++ -? А если несколько чисел подряд без операций между ними - 12 56 65? Каким образом это проверять, программ допустим, должна выдать сообщение об ошибке, но как проверить то? Причём второй знак может быть минусом или плюсом, типо 4 * - 6 или 2 - + 2?
Обычно считается, что если дано задание, то ввод при проверке гарантировано соостветствет заданию. Если согласно заданию программа должна поддерживать обработку ошибок, то должны быть прописаны требования по обработке. Что должна делать программа, если встретила строку "2 ++ 2" или "22 22" - это должно быть частью задания. А если в строке несколько ошибок, то программа должна выдать только первую или все, которые там есть? Это тоже должно быть указано в задании. В зависимости от задания примеяется тот или иной подход.
Запрограммирован какой-то алгоритм: он ожидает, что после операции будет число, после числа - операция, и т.д. Соответственно на очередном шаге алгоритм берёт следующий токен, а там не то, что ожидалось. Алгоритм не может дальше выполянться и переходит в фазу обработки ошибки: либо просто падает с сообщением, либо пытается как-то восстановиться и продолжить работу.
В простейшем случае, для проверки даже ничего не надо делать, он сам свалится. Вспомните, когда мы писали свою первую простейшую программу, где нужно было сложить два числа, мы не делали никаких специальных проверок, мы просто просили ввести два числа. Если пользователь вводит не числа, а буквы, то программа не работает, и нам с этим ничего не надо делать, по заданию корректный ввод - это числа.
почему всем понятное слово не было дописано до конца *опа, забыл в стек сначала треугольник поместить . получилось бы ☼○□∆
Я пытался сделать так в C#, но там выходит, что все числа заполняются в стек как символы, а не числа и вдобавок вбиваются раздельно все цифры
Я в C# полный ноль. Но думаю, вам может помочь комбинация Substring и Int32.Parse
Substring: msdn.microsoft.com/ru-ru/library/aka44szs(v=vs.110).aspx
Parse: msdn.microsoft.com/ru-ru/library/b3h1hf19(v=vs.110).aspx
И да. Когда пишешь эту программку самый первый раз, то можно считать, что все числа и знаки разделены пробелом, это проще парсить. Тогда можно просто воспользоваться методом Split:
msdn.microsoft.com/ru-ru/library/b873y76a(v=vs.110).aspx
Обычно стэковый калькулятор дают ученикам, которые сначала научились работать со строками, извлекать из них подстроки, находить какой-нибудь символ, конвертировать в числа и так далее. Тем, кто с этим ещё не разобрался, дают много других интересных заданий на соответствующие темы.
Спасибо, я попробую
using System.Data;
string exp = "3 + 4 - 5 * 8/2 + 13";
Console.WriteLine("{0} = {1}", exp, new DataTable().Compute(exp,""));
пользуйся
@@en_li_85 Интересно было бы посмотреть, как этим методом переопределить, запретить, добавить какие-нибудь операции. Например, переопределить операцию ^ с побитового XOR на возведение в степень, запретить синусы, и т.д.
@@en_li_85 Пожалуйста объясни вкратце как это работает
На операциях с несколькими минусами всё ломается(
По типу -1 -2 -3
Можно сделать скобкам приоритет = 0, тогда будет проще алгоритм
В чём-то проще, а в чём-то сложнее. В текущей версии алгоритм может ожидать, что числа стоят рядом со знаками, а знаки рядом с числами, у скобок особая роль, они как и числа могут идти после знаков. Если приравнять скобки к обычным операциям, то придётся учить программу тому, какая операция после какой может стоять: скобка после умножения может, а деление после умножения - нет, к тому же открывающая и закрывающая скобки ведут себя по разному. Это усложнение алгоритма. Можно перейти на формальные грамматики, но это качественно другой уровень подхода к задаче, и в данном контексте это тоже будет усложнением.
Помогите пожалуйста, бывает так, что не всегда возможно отследить синтаксис. Все же я делаю распарс, и иногда лишний символ , под конец вычислений,операции застревает в буфере. Как это можно отслеживать, и стоит ли добавлять попытки (например 20 попыток) вычислить выражение в буфере, а если не получилось, сделать брейк циклу?
Здравствуйте. Откуда вы читаете? Из файла, с клавиатуры? У вас винда? Как выглядит лишний символ: он лишний в том смысле, что вы всё полезное прочитали, а там какой-то лишний взялся, или, наоборот, нужный символ застрял там и вы не можете его извлечь для анализа?
@@obrazovaja пишу под андройд. Сначала посмотрел ваше видео, нарисовал в программе схему алгоритма. Ограничение на ввод символов сделал с помощью кастомных кнопок, но бывает так, что можно ввести лишний минус. И когда происходит распарс текста, то этот лишний символ застревает в буфере и программа, как бы зацикливается. Затем я переделал программу, и в таких случаях возвращает ноль.
Но меня интересует вопрос, как можно написать анализ синтаксиса? Если после ввода проверить на синтаксис, и вдруг он не правильный, то и считать ничего не нужно. Поэтому мой вопрос относится к вопросу контроля синтаксиса путем анализа токенов.
@@obrazovaja но моя проблема еще в том, что я добавляю функционал. Я функции поделил на бинарные и унарные.
Например, вы в видео приводите только бинарные. В унарных операциях, например при извлечении корня, нужно брать только одно значение. Тригонометрические функции -- это тоже пример унарных операций.
Вообщем, проблемы начинаются в двух вещах:
1) при добавлении нового функционала, сложнее обрабатывать исключения в буфере на выход за пределы массива. Джава, в отличие от С++, это контролирует.
2) Я не понимаю, как после разбиение на токены, контролировать синтаксические ошибки
Спасибо
@@user-tq3zn1wm1k Здравствуйте, прошу прощения за долгий ответ.
Правильно ли я понимаю, что у вас нет проблемы со стандартным/файловым вводом и иными капризами операционной системы? Иногда бывает, что EOF потока обнаруживается сразу после чтения последнего символа, а иногда только после попытки считать несуществующий. Насколько я понял, раз вы пишите под андроид, то вы сами контролируете ввод и проблемы связаны именно с алгоритмом.
> то этот лишний символ застревает в буфере и программа, как бы зацикливается
Надо разбираться. Создать простейший пример, например "2 + 2 -" (насколько я понял у вас там что-то такое) и смотреть что происходит в алгориме, и держать в голове то, а чего бы мы в этом месте, собственно, хотели добиться, какое ожидаемое поведение.
> как можно написать анализ синтаксиса
Фазы обычно такие:
- лексический разбор превращает текст в токены: числа, слова, операции, управляющие конструкции и тому подобные.
- синтаксический разбор превращает поток токенов в абстрактное синтаксическое дерево.
- интерпретатор производит вычисление дерева, вычисляя значение (наш случай), транслируя в другой язык, или иным образом.
Фазы могут либо идти друг за другом, либо входящий поток проходит сквозь все фазы сразу. Таким образом на моём видео получились слиты вместе синтаксический разбор и вычисление. Если вы делаете что-то сложное, то стоит подумать о том, чтобы сделать всё по науке (хотя если речь идёт только об унарных минусах, то можно и так заколхозить). Посмотрите соответсвующие материалы про компиляторы. Если коротко обратиться к пробелме унарных операций, то я бы предложил вам научиться строить формальную грамматику вашего языка.
Честно скажу, я не специалист по компиляторам, поэтому и не стал развивать эту тему в своих видео.
@@obrazovaja спасибо за ответ. Прошло достаточно времени с момента, когда я задал вопрос.
С того момента, я уже выпустил свое приложение в release.
Хотел бы поделиться, как лично я сделал условие выхода из цикла расчетов.
Во первых, я заметил, что неважно какой длины выражение, если оно написано грамотно, то так или иначе оно дойдет до финала и даст ответ пользователю. В случае если, встретиться какой-то странный знак в буфере, который не уходит на протяжении определенного числа иттераций (условился 200), то означает, мы в бесконечном цикле, и нужно выходить из него, а на экран выдать результат, который лежит первым в буфере чисел, и, в случае, если таковых нет, выдать 0.
Во-вторых, я написал парсинг, по контролю токенов до начала расчетов. Он не идеальный, но позволяет приблизительно оценить, насколько правильно написано. Ключевой проблемой является знак минус, тк иногда может быть рассталкован не верно. Если этот парсинг не верно истолкует, и где окажется два дублированных знака и тому подобное, то см.п.1. где говорится об ограничении на 200 иттераций, которые начинают действовать в тот момент, где у нас конец строки, а буфер еще не пустой.
Также, если вы не против, я хотел бы поделиться графическим рисунком алгоритма, который я сделал. Я думаю, что он поможет многим начинающим писать код визуально, правда я не уверен, что ютуб разрешит внешнюю ссылку в комментариях. Если вы не против, вы бы могли оставить её у себя в описании под видео. Спасибо.
А какие ещё есть способы?
Наша программа - это интерпретация текстового выражения, написанного на простом, но формальном языке. Соответственно, есть теория компиляторов, которая описывает то, как строить компиляторы и интерпретаторы. Поизучав немного эту теорию, можно написать более общую программу, для которой язык калькулятора будет лишь частным случаем. По сути, данный алгоритм - это и есть упрощение более общего алгоритма, в котором мы выкинули этап построения дерева, а производим вычисления одновременно с синтаксическим разбором.
кек
БОЛЬШАЯ ПРОСЬБА выполнить такое выражение с помощью вашего алгоритма, хоть на бумаге: 0-1*0-6. Итог: неужели выйдет ПРАВИЛЬНЫЙ ОТВЕТ?
Почему вы в этом сомневаетесь?
@@obrazovaja Я воплотил идею на языке c++
@@obrazovaja Программа извлекает из строки символы и решает выражения любой длины на операторах + - * / с числами float, но пока без скобок. обрабатывает ввод (т.е. не допускает влияние его корректности на результат), а до начала ввода следующего выражения очищает все переменные и массивы.
@@vladislavbutkobvo2699
разбираем выражение 0-1*0-6.
Кладём первый 0 в стэк. Берём первый минус, смотрим в стэке с операциями ничего нет, кладём его в стэк. Кладём 1 в стэк. Берём умножение, смотрим на вершине стэка минус, у него приоритет меньше, поэтому кладём умножение в стэк. Кладём второй ноль в стэк.
В стэках сейчас: [0, 1, 0], [-, *]. Берём второй минус, смотрим на вершине стэка умножение, приортет выше, поэтому надо сначала умножить. Выкидываем умножение из стэка на помойку, умножаем 0 на 1, кладём результат в стэк. Получилось: [0, 0], [-] . Всё-таки пытаемся взять второй минус, смотрим на вершине стэка тоже минус, приоритеты одинаковые, поэтому выполняем сначала тот, что в стэке. Убираем из стэка минус, вычисляем ноль минус ноль, ответ кладём в стэка. Получилось: [0], []. Берём второй минус, смотрим в стэке ничего нет, кладём минус в стэк. Кладём 6 в стэк. Выражение закончилось, в стэках: [0, 6], [-]. Вычисляем вершину стэка: там минус, убираем его из стэка вычитаем 0-6, кладём ответ в стэк: [-6], []. Видим в стэке с операциями больше ничего нет, значит в стэке с числами ответ: -6.
@@obrazovaja Ошибки в алгоритме нет. Моя программа не умела вычислять два действия последовательно, т.е. когда предполагался минус она выполняла умножение и не ставала разбираться с тем что там дальше - ложила минус. Спасибо вам за проявленное внимание. Я друга прошу отлаживать мою программу, но вышло так что у меня получилось быстрее найти этот недочёт, только в третьей "версии" программы. Вы сэкономили мне много времени, за что я вам благодарен.