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

@кверти · Регистрация: 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;//у листа ноль
//и понеслась...
};

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

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

	Вычислить выражение, содержащееся в строке, с использованием бинарного дерева поиска (парсинг строки) 23.09.2016, 11:46. Показов 3131. Ответов 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