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

@perec200 · Регистрация: 04.10.2014

Студворк — интернет-сервис помощи студентам

Всем привет, не так давно начал постигать c++. Возник вопрос как сделать программу-калькулятор, в которую можно вводить свои числа и арифметические операции.
Пример:
Выскакивает консолька и пользователь вводит "17 + 19 * 6 - 8", то есть пользователь не ограничен в действиях.

@taras atavin · 04.10.2014, 20:05

Сообщение от _Ivana

Если не видите проблем, напишите рекурсивный алгоритм.

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

Добавлено через 47 секунд

Сообщение от _Ivana

Но при чем тут русские буквы

А вот это уже не ко мне.

Добавлено через 2 минуты

Сообщение от _Ivana

taras atavin, это я для простоты кода ограничение предложил.

Скорей для дополнительной сложности.

@_Ivana · 04.10.2014, 20:07

Сообщение от taras atavin

Лично я не напишу

Отож! Нерекурсивный и я могу, и надежный, и с приоритетами/функциями/арностью - спасибо Дейкстре

. Просто вы предложили ТС написать "рекурсивный парсер", а я отметил, что по крайней мере для задачи не вычисления а перевода на префиксный язык это требует некоторых усилий.

@taras atavin · 04.10.2014, 20:12

У него задача вычисления. Решать можно или рекурсивным разбором, или трансляцией в постфиксную/префиксную форму. Одно из трёх, комбинации не даны, так как при рекурсивном разборе выражения можно получить только дерево выражений. Если можете написать надёжный не рекурсивный парсер изначально рекурсивной нотации, то имеете отличный повод для хвастовства. Нет - читайте Герберта Шилдта и пробуйте приспособить для своих нужд предложенный им парсер.

@monolit · 04.10.2014, 20:13

А ПОЛИЗ чем не устраивает? Всего то и делов перегнать числа в числа (int'ы), символы операций в какие-нибудь подходящие структуры (и char сойдет) - и то это при условии, что числа больше, чем однозначные, иначе и делать ничего не надо - берешь алгоритм и считаешь. Выражение в ПОЛИЗ -> Считаешь ПОЛИЗ -> Профит!

Но если только начал, то лучше сперва с структурами данных различными ознакомиться, как мне кажется. А еще лучше - их самому реализовать. vector'а, stack'и, map'ы всякие...

@_Ivana · 04.10.2014, 20:22

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

@taras atavin · 04.10.2014, 20:25

Сообщение от _Ivana

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

Нет. Стек нужен только при рекурсивном разборе и только затем, чтоб правильно возвращать управление. При нерекурсивной трансляции стек не нужен.

@_Ivana · 04.10.2014, 20:31

Как будете без стека разбирать 1+(2+(3+(4+5)))? Последовательной редукцией всей строки по одному действию наивысшего приоритета пока действия не закончатся? Тоже вариант, но немного более затратный - надо строку (или другой контейнер хранения структуры вычислений) каждый раз переписывать.

@taras atavin · 04.10.2014, 21:00

1+(2+(3+(4+5)))
Шаг первый.

член	приоритет	уровень скобок
1		0
+	0	0
2		1
+	3	1
3		2
+	6	2
4		3
+	9	3
5
		2
		1
		0

Шаг второй

член	приоритет
1
2
+	1
3
+	3
4
+	6
5
+	9

Шаг третий.

член	приоритет
1
2
3
4
5
+	9
+	6
+	3
+	0

Результат.

. На первом шагу просто все числа и знаки операций заносим в таблицу в порядке написания, при этом скобки пропускаются, но считается и записывается в ту же таблицу их уровень, а для знаков операций в ту же таблицу пишется приоритет, + и - получают приоритет 0+3*уровень скобок, а приоритет * и / 1+3*уровень скобок. После расстановки приоритетов, скобки больше не нужны, этот столбец можно выбросить. На втором шаге все знаки операций проталкиваются на один шаг вперёд. На третьем сортируются так, чтоб в любой паре знаков операций, разделённых только числами, либо непосредственно соседствующих друг другу раньше стоял знак операции с не меньшим приоритетом. Всё, постфиксное выражение готово. Пока нет функций, а все операции бинарны, этот алгоритм будет работать.

Добавлено через 3 минуты

Сообщение от _Ivana

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

А стек что не надо каждый раз переписывать?

Добавлено через 2 минуты
Исправить с учётом функций и разной арности не могу, так как данный алгоритм смог только сочинить без понимания того, почему он вообще работает.

@castorsky · 04.10.2014, 22:19

Сообщение от taras atavin

А где ж ещё нужна рекурсия? Уж не на декларативных ли языках описания страниц?

Там, где отсутствует итерация (рекурсия преобразуется в цикл).

Сообщение от taras atavin

Решать можно или рекурсивным разбором

... вот мне интересно... зачем? Ведь можно while(*string_ptr){switch(*string_ptr) {...}}
perec200, то, что Вы реализовали... на уровне школы. Вы, а не кто-либо другой, поставили задачу разобрать математическое выражение. Что ж, в наипростейшем ее варианте Вы справились. Теперь постарайтесь сделать то же, но без участия пользователя (т.е. чтобы машина сама разибарал что и с чем ей делать).

@gazlan · 05.10.2014, 02:10

Сообщение от perec200

как сделать программу-калькулятор

evaluateExpression: A Function to Evaluate Arithmetic Expressions

evaluateExpression is a convenient utility for parsing and evaluating arithmetic expressions at runtime. You can use it, for example, to evaluate expressions read from data files or configuration files or expressions entered directly by users. evaluateExpression is provided as an example of the use of the AnaGram parser generator.

This example has been specially constructed so that you can easily adapt it to your specific requirements, even if you do not have a copy of AnaGram.

evaluateExpression may be freely copied and modified.

Click here to download complete source code for this example.

IGPIGP · 05.10.2014, 02:33

Сообщение от _Ivana

только при рекурсии используется системный стек

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

@_Ivana · 05.10.2014, 02:46

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

Сообщение от _Ivana

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

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

@gazlan · 05.10.2014, 02:51

По ссылке с RSDN: Строчный калькулятор

IGPIGP · 05.10.2014, 03:00

Сообщение от _Ivana

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

Да, пардон. Я не понял сразу:

Сообщение от _Ivana

только при рекурсии используется системный стек

что это Вы о стеке вызовов. Потому как при рекурсии он конечно используется и утверждение напоминает "Волга впадает в Каспийское море"... Я подумал о том, что Вы имеете ввиду использование стека выражений, в котором как только находится операция старшего приоритета, выталкивается результат...
Так что, не вчитался в сказанное.

@_Ivana · 05.10.2014, 03:13

Сообщение от IGPIGP

утверждение напоминает "Волга впадает в Каспийское море"

Я согласен что оно именно это и напоминает, и именно это и имел в виду когда писал его

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

Добавлено через 1 минуту

Сообщение от IGPIGP

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

А это и есть сортировочная станция Дейсктры, хотя я слышал также ее название как "стековый автомат" и др.

Добавлено через 5 минут

Сообщение от IGPIGP

И всё повторяется, пока от предложения не останется слово - результат.
Можно написать ба-альшущую функцию, которая всё это делает.

И еще насчет бальшущести - когда я писал это на языке, который имеет бортовой контейнер для хранения различных типов и при этом авторесайзится при удалении части элементов из его середины (STL и C++ не знаю, но думаю там должен быть похожий аналог), то весь код разбора и вычисления выражения занимал несколько строк.

IGPIGP · 05.10.2014, 03:46

Сообщение от _Ivana

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

Имеете в виду язык с общим родительским типом вроде Object как в С#? Для хранения различных типов в STL нет ничего, но можно написать класс-оболочку и при разборе генерировать строку таких объектов. У меня не слишком компактно вышло. Но я ещё тот кодер.

@_Ivana · 05.10.2014, 03:53

Боюсь навлечь на себя гнев тру-кодеров, но я имею в виду 1С 7.7

Там есть объект "СписокЗначений", который может хранить значения любого типа, имеет индекс и (если надо) ключ каждого элемента, авторесайзится при добавлении/удалении в/из любого места себя и вообще очень удобен и хорош. и мы запихиваем в него нашу строку сразу с числами, операциями и их рассчитанным приоритетом при пробежке по строке, а потом просто бегаем по списку, вычисляем значения максимального приоритета операций, заменяем операцию на это значение, а предыдущий и следующий элементы (исходные аргументы инфиксной записи) удаляем, и не заботимся о целостности и связности списка.

Жаль, я надеялся что в STL есть подобное... Теперь еще меньше поводов учить С++

Хотя, насчет типов - никто не мешает действительно создать структуру с полями: типом енумом-значение или операция, приоритетом операции и значением значения. Но авторесайз конечно удобная штука.

IGPIGP · 05.10.2014, 04:20

Сообщение от _Ivana

Теперь еще меньше поводов учить С++

Хм... С++ как раз позволяет понять, что делает парсер при разборе сырой цепочки символов. Хотя любопытство может и до ассемблера конкретного процессора довести. Другая крайность, - скачать готовый калькулятор и не напрягаться.

На плюсах, можно же не только разобрать, а и при первом разборе создать контейнер операций инициализированный операндами. Для этого все числа можно отобразить на массив и работать с целочисленными значениями-индексами (если использовать не только литеральные числа, а и имена-параметры удобно) и потом при вычислениях запускать последовательное выполнение "скомпелированной цепочки" при любых фактических значениях переменных, минуя стадию разбора. Это быстрее, если заполнять таблицу, например, или график построить или уравнение решить. И на C# это можно.

@_Ivana · 05.10.2014, 04:31

Да ладно, парсер будет делать то, что мы ему напишем (а написать его мы можем по-разному, даже в этой теме несколько вариантов уже предлагалось), а от языка он зависит в последнюю очередь - может только вопрос наличия/отсутствия удобных контейнеров. Как раз о С и asm для некоторых архитектур я некоторое представление имею, а с С++ ни разу не сталкивался - нет, конечно написал на С++ тетрис, но в чисто сишном стиле

, без объектов/классов/ООП. Поэтому и не знаю, что там придумали с шаблонами и какие вкусные объекты есть в STL. И если там есть какой-нибудь список/вектор/что-то еще, из которого можно одной строкой вызвать метод "удалить элемент", то это просто удобно. Ваш текст про то, что можно на плюсах навскидку не понял, буду перечитывать и думать

Я вот хочу это баловство сейчас на Haskell реализовать, на его базовых структурах, без библиотечных соответствий и прочих алгебраических типов, просто на списках однотипных структур.

IGPIGP · 05.10.2014, 04:55

Сообщение от _Ivana

парсер будет делать то, что мы ему напишем

Как я понял, то что ест 1 С, он парсит автоматом или с минимальным кодом...

Сообщение от _Ivana

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

Может и непонятно написал. Давайте представим что есть строка:
1,25e-2+1,23 + x - a * ( sin ( x + bcd1 ) )
Есть значения для a, bcd1 и диапазон и шаг для x. Можно каждую точку вычислять разбирая заново, а можно один раз разобрать и построить цепочку операций. У каждой операнды и результат. Они отражаются на массив, то есть каждой следующей не нужен результат предыдущей, а достаточно индекса, где он появится. Потом для вычислений разбирать уже ничего не нужно.

Хотя С++ учить можно с разными мотивами и сказанное, скорее шутка. Мне этот язык нравится. Хоть я его и не знаю почти.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .	Теория всего 12. ВГК на планете в стратегической игре "терра" anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .

@perec200 0 / 0 / 0 Регистрация: 04.10.2014 Сообщений: 98

	Калькулятор с парсингом ввода 04.10.2014, 13:05. Показов 18036. Ответов 78 Метки нет (Все метки) Всем привет, не так давно начал постигать c++. Возник вопрос как сделать программу-калькулятор, в которую можно вводить свои числа и арифметические операции. Пример: Выскакивает консолька и пользователь вводит "17 + 19 * 6 - 8", то есть пользователь не ограничен в действиях. 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	04.10.2014, 20:12
	У него задача вычисления. Решать можно или рекурсивным разбором, или трансляцией в постфиксную/префиксную форму. Одно из трёх, комбинации не даны, так как при рекурсивном разборе выражения можно получить только дерево выражений. Если можете написать надёжный не рекурсивный парсер изначально рекурсивной нотации, то имеете отличный повод для хвастовства. Нет - читайте Герберта Шилдта и пробуйте приспособить для своих нужд предложенный им парсер. 0

@monolit 188 / 187 / 46 Регистрация: 24.03.2011 Сообщений: 670
	04.10.2014, 20:13
	А ПОЛИЗ чем не устраивает? Всего то и делов перегнать числа в числа (int'ы), символы операций в какие-нибудь подходящие структуры (и char сойдет) - и то это при условии, что числа больше, чем однозначные, иначе и делать ничего не надо - берешь алгоритм и считаешь. Выражение в ПОЛИЗ -> Считаешь ПОЛИЗ -> Профит! Но если только начал, то лучше сперва с структурами данных различными ознакомиться, как мне кажется. А еще лучше - их самому реализовать. vector'а, stack'и, map'ы всякие... 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	04.10.2014, 20:22
	Вообще по-большому счету рекурсивные/нерекурсивные алгоритмы решения этой задачи в принципе одинаковы - только при рекурсии используется системный стек, куда сохраняются необходимые промежуточные значения плюс еще куча контекста, а при нерекурсивных алгоритмах мы создаем/заполняем/разбираем этот стек самостоятельно вручную внутри одной функции разбора/вычисления. А повод для хвастовства (или некоторого удовлетворения) у меня будет тогда, когда я пойму выложенное знакомым решение этой задачи на Haskell с использованием комбинаторов, принципов синтаксического разбора, порождающих грамматик и прочих интересных и пока непонятных мне слов. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	04.10.2014, 20:31
	Как будете без стека разбирать 1+(2+(3+(4+5)))? Последовательной редукцией всей строки по одному действию наивысшего приоритета пока действия не закончатся? Тоже вариант, но немного более затратный - надо строку (или другой контейнер хранения структуры вычислений) каждый раз переписывать. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	05.10.2014, 03:53
	Боюсь навлечь на себя гнев тру-кодеров, но я имею в виду 1С 7.7 Там есть объект "СписокЗначений", который может хранить значения любого типа, имеет индекс и (если надо) ключ каждого элемента, авторесайзится при добавлении/удалении в/из любого места себя и вообще очень удобен и хорош. и мы запихиваем в него нашу строку сразу с числами, операциями и их рассчитанным приоритетом при пробежке по строке, а потом просто бегаем по списку, вычисляем значения максимального приоритета операций, заменяем операцию на это значение, а предыдущий и следующий элементы (исходные аргументы инфиксной записи) удаляем, и не заботимся о целостности и связности списка. Жаль, я надеялся что в STL есть подобное... Теперь еще меньше поводов учить С++ Хотя, насчет типов - никто не мешает действительно создать структуру с полями: типом енумом-значение или операция, приоритетом операции и значением значения. Но авторесайз конечно удобная штука. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	05.10.2014, 04:31
	Да ладно, парсер будет делать то, что мы ему напишем (а написать его мы можем по-разному, даже в этой теме несколько вариантов уже предлагалось), а от языка он зависит в последнюю очередь - может только вопрос наличия/отсутствия удобных контейнеров. Как раз о С и asm для некоторых архитектур я некоторое представление имею, а с С++ ни разу не сталкивался - нет, конечно написал на С++ тетрис, но в чисто сишном стиле , без объектов/классов/ООП. Поэтому и не знаю, что там придумали с шаблонами и какие вкусные объекты есть в STL. И если там есть какой-нибудь список/вектор/что-то еще, из которого можно одной строкой вызвать метод "удалить элемент", то это просто удобно. Ваш текст про то, что можно на плюсах навскидку не понял, буду перечитывать и думать Я вот хочу это баловство сейчас на Haskell реализовать, на его базовых структурах, без библиотечных соответствий и прочих алгебраических типов, просто на списках однотипных структур. 0