Вычислить выражение, содержащееся в строке, с использованием бинарного дерева поиска (парсинг строки)

@кверти · Регистрация: 22.09.2013

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

В символьной строке записано правильное арифметическое выражение, которое может содержать числа и знаки операций +-*\. Вычислить это выражение с использованием Бинарного дерева поиска.

Поделитесь идеями как делать задачу. Чисто алгоритм придумать не могу. Что хранить в узлах дерева и каким образом выполнить с помощью бст еще одно условие:
Арифметическое выражение с однозначными числами может содержать ошибки в арифметических операциях (например: 2++3*+3). Необходимо исправить выражение и показать исправления.

IGPIGP · 23.09.2016, 22:04

Сообщение от кверти

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

Это в принципе плохая идея. Лучше остановить выполнение и объяснив проблему предоставить пользователю самому исправить ошибку. Например, в Вашем примере может не плюс быть лишним, а не хватать операндов может:
2+4+3*5+3
И выяснить, где не хватает скобки или какая из них лишняя, без юзера не сможет никто. А желание налету исправить ввод, - залог страданий. То есть путь к тёмной стороне оно открыть может.

@_Ivana · 24.09.2016, 00:08

Не по теме:

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

То есть путь к тёмной стороне оно открыть может.

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

IGPIGP · 24.09.2016, 00:15

Не по теме:

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

К темному жаваскрипту оно путь откроет,

Из диалога на углу:
-Привет!
-Привет.
-Как дела?
-Скриптю потихоньку.

***
Умная программа, это хорошо, но иной раз возникает ощущение что что-то к мыши прилипло. :pardon:
Это как на жвачку наступить. Килограммовую. :scratch:
:)

@_Ivana · 24.09.2016, 00:23

Не по теме:

Кстати, если скормить предложенное выражение моему поделию (предварительно переведя операторы в префиксную форму), то получится вполне вменяемое

Lisp
1
2
++ 2 (* 3 +3)
=> 29

- то есть строковая конкатенация двойки и умножения двух чисел :) Но другие языки могут трактануть по-своему. Да что далеко за примерами ходить и на скрипты гнать - С/С++ тоже неплохо автокастят до непредсказуемого результата порой :)

IGPIGP · 24.09.2016, 00:32

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

С/С++ тоже неплохо автокастят до непредсказуемого результата порой

_Ivana, тут же ещё спарсить надо. У ТС задание исправлять ошибки (пусть и некоторые) при вводе строки математического выражения. Если это его идея, то я пытаюсь переубедить. А если это преподаватель измыслил, то придётся стать на его сторону. И обретя силу победить. Так было и так будет. Потому, что всегда двое их: - учитель и ученик.

@_Ivana · 24.09.2016, 00:39

Не по теме:

IGPIGP, я смотрю, вы тоже скучаете, что аж в такие темы на подобные темы пишете :) Айда с нами с ct0r фигней маяться - Задачки - погодная машина Санта-Клауса! :)

IGPIGP · 24.09.2016, 01:01

Не по теме:

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

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

Тема интересная в том плане, что требует построение бинарного дерева операций. А скуки нет. Сегодня как раз неплохой денёк. Даже покодить успел и на редкость удачно. Просто когда чувствую что уже плыву, не хочется чего-нить наломать. Вот и захожу посмотреть. А к деду морозу зайду раз ты говоришь. :)

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

Не по теме:

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

А к деду морозу зайду раз ты говоришь.

зашёл и вспомнил, - я уже видел эту тему. Там всё серьёзно, нужно авторизоваться в какой-либо из соцсетей и играть. Тут я пас. И на хаскеле я не понимайт тоже. :-[

@_Ivana · 24.09.2016, 01:05

Не по теме:

Ну я нигде в соцсетях не живу, через гитхабовский аккаунт вроде зашел, не помню уже :) Хаскель ни при чем, вон коллеги на Эрланге решают, там только ответы отправлять, а как их получать - хоть на С++, хоть на бумажке ручкой :)

IGPIGP · 24.09.2016, 01:17

Не по теме:

Не-а. Не хочу. Если одна задачка и опубликована тут, то ещё можно бы проследить и даже чего-то сказать, если придётся, а иначе нет. Спасибо за приглашение. :)

@Renji · 24.09.2016, 02:59

Сообщение от кверти

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

Не знаю причем тут дерево поиска, но через дерево задача, очевидно, решается так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Expression
{
public:
    Expression(const Expression*_leftValue,const Expression*_rightValue):
        leftValue(_leftValue),rightValue(_rightValue){}
    virtual~Expression(){
        delete leftValue;
        delete rightValue;
    }
    virtual double calculate()const=0;
protected:
    const Expression*const leftValue;
    const Expression*const rightValue;
};
 
class AddExpression:public Expression
{
public:
    AddExpression(const Expression*leftValue,const Expression*rightValue):
        Expression(leftValue,rightValue){}
    double calculate()const{return leftValue->calculate()+rightValue->calculate();}
};

Парсер уже сами делайте.

IGPIGP · 24.09.2016, 12:08

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

но через дерево задача, очевидно, решается так:

Я решал лесом:

C++
1
2
3
4
5
6
7
class Expression
{
Token token;
Expression * expression;//у корня ноль
list<Expression *>  expressions;//у листа ноль
//и понеслась...
};

Новые блоги и статьи Все статьи Все блоги /
Что нового в C# 14 UnmanagedCoder 10.03.2025 Предстоящая версия C# 14 обещает принести изменения, которые сделают разработку еще более приятной и эффективной. Что стоит отметить, так это влияние сообщества разработчиков на формирование новых. . .	Формулы поворота Igor3D 10.03.2025 Добрый день Тема Эти формулы приводятся во множестве тьюториалов, часто под видом "матрица вращения на плоскости". x' = x * cos(a) - y * sin(a) y' = y * cos(a) + x * sin(a) Как бы Вы их. . .	Что нового в .NET 10 UnmanagedCoder 10.03.2025 . NET 10 выходит как релиз с длительной поддержкой (LTS), включающей три года обновлений. В этом обновлении Microsoft сфокусировались на нескольких направлениях: производительность, оптимизация. . .	Отложенное высвобождение, RCU и Hazard Pointer в C++26 NullReferenced 09.03.2025 Многопоточное программирование стало важной частью современной разработки. Когда несколько потоков одновременно работают с общими данными, возникает целый ряд проблем, связанных с синхронизацией и. . .	Неблокирующийся стек на C++26 NullReferenced 09.03.2025 Традиционные способы синхронизации в многопоточном программировании — мьютексы, семафоры, условные переменные — часто превращаются в узкое место в плане производительности. При этом неблокирующиеся. . .
Обработка строк в C++26: Новые возможности string и string_view NullReferenced 09.03.2025 Новый стандарт C++26 предлагает много улучшений для работы с привычными string и относительно новыми string_view. string_view - это невладеющая ссылка на последовательность символов, появившаяся в. . .	Мой первый аддон для Blender 3D, с помощью нейронки (не зная даже азов пайтона, но это не значит что так и с остальным). Hrethgir 09.03.2025 Потратил весь день. Пол-дня мне хватило, чтобы понять что с версией с 14B мне не одолеть написание функционального кода, на языке с которым я вообще никак не знаком - пайтон. Версия 22B от другого. . .	Einstein@Home сегодня исполняется двадцать лет! Programma_Boinc 09.03.2025 Einstein@Home сегодня исполняется двадцать лет! Отправлено 19 февраля 2025 года в 17:20:21 UTC Я хочу поздравить всех наших волонтеров, разработчиков и ученых из Einstein@Home. Мы официально. . .	Заполнители и расширенный набор символов в C++26 NullReferenced 09.03.2025 C++26 представляет два важных обновления: заполнители и расширенный набор символов. Заполнители (placeholders) решают давнюю проблему лаконичности кода в шаблонных выражениях и лямбда-функциях. Они. . .	Контракты в C++26 NullReferenced 09.03.2025 Контракты – это механизм, позволяющий указывать предусловия, постусловия и инварианты для функций в коде. Эта функциональность должна была стать частью C++20, но была исключена на встрече комитета. . .

@кверти 6 / 6 / 3 Регистрация: 22.09.2013 Сообщений: 166
		1
	Вычислить выражение, содержащееся в строке, с использованием бинарного дерева поиска (парсинг строки) 23.09.2016, 11:46. Показов 2937. Ответов 11 Метки нет (Все метки) В символьной строке записано правильное арифметическое выражение, которое может содержать числа и знаки операций +-\. Вычислить это выражение с использованием Бинарного дерева поиска. Поделитесь идеями как делать задачу. Чисто алгоритм придумать не могу. Что хранить в узлах дерева и каким образом выполнить с помощью бст еще одно условие: Арифметическое выражение с однозначными числами может содержать ошибки в арифметических операциях (например: 2++3+3). Необходимо исправить выражение и показать исправления. 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4704 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	23.09.2016, 22:04	2
	Сообщение от кверти Необходимо исправить выражение и показать исправления. Это в принципе плохая идея. Лучше остановить выполнение и объяснив проблему предоставить пользователю самому исправить ошибку. Например, в Вашем примере может не плюс быть лишним, а не хватать операндов может: 2+4+3*5+3 И выяснить, где не хватает скобки или какая из них лишняя, без юзера не сможет никто. А желание налету исправить ввод, - залог страданий. То есть путь к тёмной стороне оно открыть может. 0

@_Ivana
	24.09.2016, 00:08	3
	Не по теме: Сообщение от IGPIGP То есть путь к тёмной стороне оно открыть может. К темному жаваскрипту оно путь откроет, и далее к еще более темным языкам, в которых все по-возможности как-то трактуется, кастится и вычисляется, но далеко не всегда так, как подразумевал писавший кот :D 0

IGPIGP
	24.09.2016, 00:15	4
	Не по теме: Сообщение от _Ivana К темному жаваскрипту оно путь откроет, Из диалога на углу: -Привет! -Привет. -Как дела? -Скриптю потихоньку. *** Умная программа, это хорошо, но иной раз возникает ощущение что что-то к мыши прилипло. :pardon: Это как на жвачку наступить. Килограммовую. :scratch: :) 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4704 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	24.09.2016, 00:32	6
	Сообщение от _Ivana С/С++ тоже неплохо автокастят до непредсказуемого результата порой _Ivana, тут же ещё спарсить надо. У ТС задание исправлять ошибки (пусть и некоторые) при вводе строки математического выражения. Если это его идея, то я пытаюсь переубедить. А если это преподаватель измыслил, то придётся стать на его сторону. И обретя силу победить. Так было и так будет. Потому, что всегда двое их: - учитель и ученик. 0

@_Ivana
	24.09.2016, 00:39	7
	Не по теме: IGPIGP, я смотрю, вы тоже скучаете, что аж в такие темы на подобные темы пишете :) Айда с нами с ct0r фигней маяться - Задачки - погодная машина Санта-Клауса! :) 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4704 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	24.09.2016, 01:01	8
	Не по теме: Сообщение от _Ivana я смотрю, вы тоже скучаете, что аж в такие темы на подобные темы пишете Тема интересная в том плане, что требует построение бинарного дерева операций. А скуки нет. Сегодня как раз неплохой денёк. Даже покодить успел и на редкость удачно. Просто когда чувствую что уже плыву, не хочется чего-нить наломать. Вот и захожу посмотреть. А к деду морозу зайду раз ты говоришь. :) Добавлено через 17 минут Не по теме: Сообщение от IGPIGP А к деду морозу зайду раз ты говоришь. зашёл и вспомнил, - я уже видел эту тему. Там всё серьёзно, нужно авторизоваться в какой-либо из соцсетей и играть. Тут я пас. И на хаскеле я не понимайт тоже. :-[ 0

@_Ivana
	24.09.2016, 01:05	9
	Не по теме: Ну я нигде в соцсетях не живу, через гитхабовский аккаунт вроде зашел, не помню уже :) Хаскель ни при чем, вон коллеги на Эрланге решают, там только ответы отправлять, а как их получать - хоть на С++, хоть на бумажке ручкой :) 0

IGPIGP
	24.09.2016, 01:17	10
	Не по теме: Не-а. Не хочу. Если одна задачка и опубликована тут, то ещё можно бы проследить и даже чего-то сказать, если придётся, а иначе нет. Спасибо за приглашение. :) 0