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

большое спасибо! устаканилось вроде в голове. сейчас буду реализовывать на СИ. дай Бог Вам здоровья!

Офигенный видос, мне очень помог

Супер. Понятное сведение в одном коротком видео объяснения стека, польской нотациии алгоритма калькулятора

Благодарю за информацию о подобном алгоритме и Вашу работу

Спасибо! Очень качественный урок!))

благодарен вам. алгоритм оказался довольно несложным а реализации с такими подробными обьяснениями.

Спасибо тебе Добрый человек!!!!

ЧУВАК, СПАСИБО ОГРОМНОЕ!

Спасибо огромное, с помощью этого алгоритма наконец-то смог собрать сложное дерево из плоских значений

Красавчик, очень эффективно объяснил

Уже пересмотрел все видео с обратной польской нотацией что сумел найти. Но это видео объясняет её лучше всех.

Огонь, спасибо большое!

от плавца школы 21 оффициальное спасибо

@danilvaliev9326

4 жыл бұрын

UPD 2020 Kazan

@DavletshinArtur

3 жыл бұрын

да прибудет с вами eval_expr

@obrazovaja

3 жыл бұрын

А что делать тем, кому любопытно, а как же написан eval?

@MrRinok15

3 жыл бұрын

@@obrazovaja ы

@DavletshinArtur

3 жыл бұрын

​@@obrazovaja каждый решит для себя сам

Шикарно! Т.е. здесьпо сути преобразование в обратную польскую нотацию.

Очень классное объяснение!

спасибо!

От имени 1ой группы 1ого потока 1 ого курса ВМК МГУ большое спасибо

учитель красавчик

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

@user-ed4kg6yq3p

Жыл бұрын

Теперь пиши калькулятор матричных выражений)

@dowlso

Жыл бұрын

В python есть готовая функция eval, которая выполняет выражение из строки

@obrazovaja

Жыл бұрын

@@dowlso Интересно было бы посмотреть, как этим методом вы реализуете поддержку выражений отличных от выражений языка питон. Например, определить операцию ^ как возведение в степень, или запретить синусы, и т.д.

Как я понимаю, это можно сделать одним стеком, а так урок великолепен

Случайно набрел на видео. Автор - мы мой кумир. Все рассказал за один заход. Пример супер удачный - выловил кучу багов на нем! Замечу, что т.к. стека два, то функция top(a) не нужна, можно в лоб смотреть operations_stack[-1]

@obrazovaja

3 жыл бұрын

top() - это интерфейс стека. Абстрактный стэк не предполагает возможность обращаться к произвольному элементу по индексу, потому что стэк может быть реализован поверх структуры, в которой обращение по индексу неэффективно. Поэтому алгоритм, который использует стэк, должен пользоваться функцией top, не завязываясь на её реализацию.

Премия учитель года!

@obrazovaja

5 жыл бұрын

Это мы всегда рады. Спасибо!

топ!

Решал совершенно по другому. У меня идет разбитие на отдельные строчки в список того что в скобках, и назначения приоритета в зависимости от вложенности скобок. Потом считаются в обратном порядке вложенности и приоритета. За то сам придумал. =) Теперь хочу выяснить какой алгоритм будет быстрее работать =)

спасибобобобобобо

Интересно посмотреть реализацию в Python

@obrazovaja

6 жыл бұрын

Согласен! С нетерпением ждём ссылки на ваш код ;-)

@user-oy7vn6mk1t

Жыл бұрын

@@obrazovaja ахахаха Кстати, на: eval - встроенная функция) А если кто сделал таки на C++, то скиньте пожалуйста

like по-любому

С П А С И Б О !

мда целую неделю это видео вгоняло меня в черную тоску пока не удалось это реализовать))

Какой алгоритм действий будет если в выражении присутствуют числа с унарным минусом?

@obrazovaja

4 жыл бұрын

Допустим, что мы пока не хотим переходить к формальной грамматике. Тогда просто заметим, что унарный минус не может появиться абы где. Он появляется только в том месте, где мы ждём открывающую скобку или число. Таким образом мы не можем его спутать с обычным минусом. Придумываем ему обозначение, под которым будем класть унарный минус в стек операций. Тогда прежде, чем положить очередное число в стек чисел (прочитанное или после вычислений), мы сначала проверяем, нет ли на вершине стека операций унарного минуса. Если есть, то забираем его оттуда, а число меняем на противоположное по знаку. Но на данном этапе можно уже задуматься о формальной грамматике, почитать что-нибудь про это, и тогда вопросов станет меньше... или больше.

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

@obrazovaja

3 жыл бұрын

Самый простой способ - это отделять всё друг от друга пробелами. Пока не встретите следующий пробел, считаете, что продолжаете читать цифры того же самого числа. Тогда можно будет даже воспользоваться стандартной функцией scanf или sscanf для Си или их аналогами в других языках. В общем виде эта задача называется «лексический анализ», в видео об этом упоминается вскольз. Нужно из сплошного текста выделить единицы смысла - так называемые токены - числа, знаки и скобки. Первый способ - это если вы скармливаете строку с текстом некоторой функции и она разбивает её на токены. В итоге у вас получается массив, в котором уже не буковки, а сущности для работы калькулятора: числа, знаки и скобки. Думаю, для начала - этот способ реализовать проще вего. (кстати, если всё разделено пробелами, то можно сделать строке банальный split) Либо можно совместить процесс чтения строки и выделения лексем. Например, сделать функцию, которая принимает на вход строку str и позицию, где вы остановились, и отдаёт вам очередной токен и позицию следующего за ним токена. Т.е. что-то вида: getTokenAt(str, position) -> [value, next_position], где value - это число или знак, а next_position - это позиция следующего токена, которую вы отправите в функцию getTokenAt в следующий раз, "str" у вас всегда одна и та же. Этот способ хорош тем, что его можно доработать для потокового ввода, когда можно читать со входа в реальном режиме. Для создания токенайзера нашего калькулятора достаточно базовых навыков программирования и это полезное упражнение. В реальном мире для лексического анализа есть универсальные анализаторы, в которых допустимые лексемы задаются регулярными выражениями. Например, лексемы нашего языка можно описать так: Num(\d+(\.\d+)?), Op([+-*/()])

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

@obrazovaja

4 жыл бұрын

Два стека здесь лишь для удобства рассказа. Можно всё то же через один стек сделать. Т.е. по сути стек один.

а что делать если в строке встретилось несколько знаков умножить подряд, два, три? Или несколько знаков плюс и минус подряд - ++ -? А если несколько чисел подряд без операций между ними - 12 56 65? Каким образом это проверять, программ допустим, должна выдать сообщение об ошибке, но как проверить то? Причём второй знак может быть минусом или плюсом, типо 4 * - 6 или 2 - + 2?

@obrazovaja

2 жыл бұрын

Обычно считается, что если дано задание, то ввод при проверке гарантировано соостветствет заданию. Если согласно заданию программа должна поддерживать обработку ошибок, то должны быть прописаны требования по обработке. Что должна делать программа, если встретила строку "2 ++ 2" или "22 22" - это должно быть частью задания. А если в строке несколько ошибок, то программа должна выдать только первую или все, которые там есть? Это тоже должно быть указано в задании. В зависимости от задания примеяется тот или иной подход. Запрограммирован какой-то алгоритм: он ожидает, что после операции будет число, после числа - операция, и т.д. Соответственно на очередном шаге алгоритм берёт следующий токен, а там не то, что ожидалось. Алгоритм не может дальше выполянться и переходит в фазу обработки ошибки: либо просто падает с сообщением, либо пытается как-то восстановиться и продолжить работу. В простейшем случае, для проверки даже ничего не надо делать, он сам свалится. Вспомните, когда мы писали свою первую простейшую программу, где нужно было сложить два числа, мы не делали никаких специальных проверок, мы просто просили ввести два числа. Если пользователь вводит не числа, а буквы, то программа не работает, и нам с этим ничего не надо делать, по заданию корректный ввод - это числа.

Не понятно с момента второй скобки. Почему мы просто вычисляем, пока не встретим скобку? А если бы там было (1+2/2)?

@obrazovaja

4 жыл бұрын

Тогда бы в тот момент, когда бы мы добрались до закрывающей скобки, то в стеке с числами было бы: ...,1, 2, 2; а в стеке со знаками было бы: ..., (, +, /; И значит нам пришлось бы взять из стека две двойки и последнее деление, поделить, положить единицу обратно в стек, потом взять две единицы и плюсик, сложить и положить двойку обратно в стек, потом увидеть скобочку и просто её выкинуть вместе с закрывающей парной. См. картинку: take.ms/W9ZEM

@CheatCraft

4 жыл бұрын

@@obrazovaja спасибо!

@__-hj6sk

Жыл бұрын

Игрокам GM привет. Не ожидал увидеть здеся знакомый ник из 2014 года

Спасибо за видео, я всё понял. Как можно это сделать с одним стеком?

@obrazovaja

Жыл бұрын

Это вам упражнение для самостоятельной работы

Можно сделать скобкам приоритет = 0, тогда будет проще алгоритм

@obrazovaja

3 жыл бұрын

В чём-то проще, а в чём-то сложнее. В текущей версии алгоритм может ожидать, что числа стоят рядом со знаками, а знаки рядом с числами, у скобок особая роль, они как и числа могут идти после знаков. Если приравнять скобки к обычным операциям, то придётся учить программу тому, какая операция после какой может стоять: скобка после умножения может, а деление после умножения - нет, к тому же открывающая и закрывающая скобки ведут себя по разному. Это усложнение алгоритма. Можно перейти на формальные грамматики, но это качественно другой уровень подхода к задаче, и в данном контексте это тоже будет усложнением.

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

@obrazovaja

Жыл бұрын

Здравствуйте. Откуда вы читаете? Из файла, с клавиатуры? У вас винда? Как выглядит лишний символ: он лишний в том смысле, что вы всё полезное прочитали, а там какой-то лишний взялся, или, наоборот, нужный символ застрял там и вы не можете его извлечь для анализа?

@user-tq3zn1wm1k

Жыл бұрын

@@obrazovaja пишу под андройд. Сначала посмотрел ваше видео, нарисовал в программе схему алгоритма. Ограничение на ввод символов сделал с помощью кастомных кнопок, но бывает так, что можно ввести лишний минус. И когда происходит распарс текста, то этот лишний символ застревает в буфере и программа, как бы зацикливается. Затем я переделал программу, и в таких случаях возвращает ноль. Но меня интересует вопрос, как можно написать анализ синтаксиса? Если после ввода проверить на синтаксис, и вдруг он не правильный, то и считать ничего не нужно. Поэтому мой вопрос относится к вопросу контроля синтаксиса путем анализа токенов.

@user-tq3zn1wm1k

Жыл бұрын

@@obrazovaja но моя проблема еще в том, что я добавляю функционал. Я функции поделил на бинарные и унарные. Например, вы в видео приводите только бинарные. В унарных операциях, например при извлечении корня, нужно брать только одно значение. Тригонометрические функции -- это тоже пример унарных операций. Вообщем, проблемы начинаются в двух вещах: 1) при добавлении нового функционала, сложнее обрабатывать исключения в буфере на выход за пределы массива. Джава, в отличие от С++, это контролирует. 2) Я не понимаю, как после разбиение на токены, контролировать синтаксические ошибки Спасибо

@obrazovaja

Жыл бұрын

@@user-tq3zn1wm1k Здравствуйте, прошу прощения за долгий ответ. Правильно ли я понимаю, что у вас нет проблемы со стандартным/файловым вводом и иными капризами операционной системы? Иногда бывает, что EOF потока обнаруживается сразу после чтения последнего символа, а иногда только после попытки считать несуществующий. Насколько я понял, раз вы пишите под андроид, то вы сами контролируете ввод и проблемы связаны именно с алгоритмом. > то этот лишний символ застревает в буфере и программа, как бы зацикливается Надо разбираться. Создать простейший пример, например "2 + 2 -" (насколько я понял у вас там что-то такое) и смотреть что происходит в алгориме, и держать в голове то, а чего бы мы в этом месте, собственно, хотели добиться, какое ожидаемое поведение. > как можно написать анализ синтаксиса Фазы обычно такие: - лексический разбор превращает текст в токены: числа, слова, операции, управляющие конструкции и тому подобные. - синтаксический разбор превращает поток токенов в абстрактное синтаксическое дерево. - интерпретатор производит вычисление дерева, вычисляя значение (наш случай), транслируя в другой язык, или иным образом. Фазы могут либо идти друг за другом, либо входящий поток проходит сквозь все фазы сразу. Таким образом на моём видео получились слиты вместе синтаксический разбор и вычисление. Если вы делаете что-то сложное, то стоит подумать о том, чтобы сделать всё по науке (хотя если речь идёт только об унарных минусах, то можно и так заколхозить). Посмотрите соответсвующие материалы про компиляторы. Если коротко обратиться к пробелме унарных операций, то я бы предложил вам научиться строить формальную грамматику вашего языка. Честно скажу, я не специалист по компиляторам, поэтому и не стал развивать эту тему в своих видео.

@user-tq3zn1wm1k

Жыл бұрын

​@@obrazovaja спасибо за ответ. Прошло достаточно времени с момента, когда я задал вопрос. С того момента, я уже выпустил свое приложение в release. Хотел бы поделиться, как лично я сделал условие выхода из цикла расчетов. Во первых, я заметил, что неважно какой длины выражение, если оно написано грамотно, то так или иначе оно дойдет до финала и даст ответ пользователю. В случае если, встретиться какой-то странный знак в буфере, который не уходит на протяжении определенного числа иттераций (условился 200), то означает, мы в бесконечном цикле, и нужно выходить из него, а на экран выдать результат, который лежит первым в буфере чисел, и, в случае, если таковых нет, выдать 0. Во-вторых, я написал парсинг, по контролю токенов до начала расчетов. Он не идеальный, но позволяет приблизительно оценить, насколько правильно написано. Ключевой проблемой является знак минус, тк иногда может быть рассталкован не верно. Если этот парсинг не верно истолкует, и где окажется два дублированных знака и тому подобное, то см.п.1. где говорится об ограничении на 200 иттераций, которые начинают действовать в тот момент, где у нас конец строки, а буфер еще не пустой. Также, если вы не против, я хотел бы поделиться графическим рисунком алгоритма, который я сделал. Я думаю, что он поможет многим начинающим писать код визуально, правда я не уверен, что ютуб разрешит внешнюю ссылку в комментариях. Если вы не против, вы бы могли оставить её у себя в описании под видео. Спасибо.

Я пытался сделать так в C#, но там выходит, что все числа заполняются в стек как символы, а не числа и вдобавок вбиваются раздельно все цифры

@obrazovaja

6 жыл бұрын

Я в 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 Обычно стэковый калькулятор дают ученикам, которые сначала научились работать со строками, извлекать из них подстроки, находить какой-нибудь символ, конвертировать в числа и так далее. Тем, кто с этим ещё не разобрался, дают много других интересных заданий на соответствующие темы.

@iliaTrof

6 жыл бұрын

Спасибо, я попробую

@en_li_85

5 жыл бұрын

using System.Data; string exp = "3 + 4 - 5 * 8/2 + 13"; Console.WriteLine("{0} = {1}", exp, new DataTable().Compute(exp,"")); пользуйся

@obrazovaja

5 жыл бұрын

@@en_li_85 Интересно было бы посмотреть, как этим методом переопределить, запретить, добавить какие-нибудь операции. Например, переопределить операцию ^ с побитового XOR на возведение в степень, запретить синусы, и т.д.

@user-rj5kq9sg6z

5 жыл бұрын

​@@en_li_85 Пожалуйста объясни вкратце как это работает

почему всем понятное слово не было дописано до конца *опа, забыл в стек сначала треугольник поместить . получилось бы ☼○□∆

На операциях с несколькими минусами всё ломается( По типу -1 -2 -3

как добавить приоритет операций в программму?

@obrazovaja

Жыл бұрын

Я не уверен, что правильно понял ваш вопрос, но попробую ответить как понял. В видео на 2:12 оформился объект с приоритетами. Записываете его в переменную: p = {'+': 1, '*': 2}. Тогда p['+'] - это 1, а p['*'] - это 2. Допустим, вы берёе операцию из стэка (переменная a) и хотите сравнить её со следующей операцией из выражения (переменная b), тогда вы сравниваете p[a] и p[b]. Какое число выше, та операция имеет больший приоритет.

А какие ещё есть способы?

@obrazovaja

Жыл бұрын

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

кек

БОЛЬШАЯ ПРОСЬБА выполнить такое выражение с помощью вашего алгоритма, хоть на бумаге: 0-1*0-6. Итог: неужели выйдет ПРАВИЛЬНЫЙ ОТВЕТ?

@obrazovaja

3 жыл бұрын

Почему вы в этом сомневаетесь?

@vladislavbutkobvo2699

3 жыл бұрын

@@obrazovaja Я воплотил идею на языке c++

@vladislavbutkobvo2699

3 жыл бұрын

@@obrazovaja Программа извлекает из строки символы и решает выражения любой длины на операторах + - * / с числами float, но пока без скобок. обрабатывает ввод (т.е. не допускает влияние его корректности на результат), а до начала ввода следующего выражения очищает все переменные и массивы.

@obrazovaja

3 жыл бұрын

@@vladislavbutkobvo2699 разбираем выражение 0-1*0-6. Кладём первый 0 в стэк. Берём первый минус, смотрим в стэке с операциями ничего нет, кладём его в стэк. Кладём 1 в стэк. Берём умножение, смотрим на вершине стэка минус, у него приоритет меньше, поэтому кладём умножение в стэк. Кладём второй ноль в стэк. В стэках сейчас: [0, 1, 0], [-, *]. Берём второй минус, смотрим на вершине стэка умножение, приортет выше, поэтому надо сначала умножить. Выкидываем умножение из стэка на помойку, умножаем 0 на 1, кладём результат в стэк. Получилось: [0, 0], [-] . Всё-таки пытаемся взять второй минус, смотрим на вершине стэка тоже минус, приоритеты одинаковые, поэтому выполняем сначала тот, что в стэке. Убираем из стэка минус, вычисляем ноль минус ноль, ответ кладём в стэка. Получилось: [0], []. Берём второй минус, смотрим в стэке ничего нет, кладём минус в стэк. Кладём 6 в стэк. Выражение закончилось, в стэках: [0, 6], [-]. Вычисляем вершину стэка: там минус, убираем его из стэка вычитаем 0-6, кладём ответ в стэк: [-6], []. Видим в стэке с операциями больше ничего нет, значит в стэке с числами ответ: -6.

@vladislavbutkobvo2699

3 жыл бұрын

​@@obrazovaja ​ Ошибки в алгоритме нет. Моя программа не умела вычислять два действия последовательно, т.е. когда предполагался минус она выполняла умножение и не ставала разбираться с тем что там дальше - ложила минус. Спасибо вам за проявленное внимание. Я друга прошу отлаживать мою программу, но вышло так что у меня получилось быстрее найти этот недочёт, только в третьей "версии" программы. Вы сэкономили мне много времени, за что я вам благодарен.