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

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

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

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

Поделитесь идеями как делать задачу. Чисто алгоритм придумать не могу. Что хранить в узлах дерева и каким образом выполнить с помощью бст еще одно условие:
Арифметическое выражение с однозначными числами может содержать ошибки в арифметических операциях (например: 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;//у листа ноль
//и понеслась...
};

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@кверти 6 / 6 / 3 Регистрация: 22.09.2013 Сообщений: 166

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

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

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

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