0

На вход подается описание бинарного дерева. На листьях (висячих вершинах) этого дерева написаны целые числа (от -10^6 до 10^6). Идем от корня дерева, случайно поварачивая направо или налево (с вероятностями 0.5).

Чему равно cреднее значение числа на листе, в который мы в конечном счете придем? Ответ вывести с точностью до двух знаков после запятой.

Данную задачу можно решить без дерева. Когда встречаешь "(" - уменьшать вероятность, когда ")" - увеличивать: res=a[i]*(0.5)^(b[i]), где a[i] — это какое-то число из строки ввода, b[i] — скобочный итог к моменту, когда мы встретили это число. И суммировать результаты. Т.е. когда скобка, он должен прибавлять или вычитать к s. А когда число - выполнять действия с ним. Подскажите.

using namespace std;

int main()
{
    string str,st;

int index = 0,k=0,i=0;
double s=0,res=0;
res = 0;
char chr;
getline(cin,str);

while (index < str.length())
{
    chr = str[index];

    if ((chr!='(')||(chr!=')'||(chr!=' ')))
        {
            st = chr;
            k = atoi(st.c_str()); cout << "k=" << k << endl;
            res = res + k*pow(0.5, s); cout << "s=" << s << endl;
        }

    if (chr == '(')
    {
        s = s+1 ;

    }
    if (chr == ')')
    {
        s = s-1;

    }
    cout << "ravn" << res<<endl;

    index++;
}
    cout << "ravn" << res;
        system("pause");
}

На вход подавться будет вот такое: (1 3(2 4))

7
  • Так, как сделал я, тоже нельзя. Нужно все же целое число. Подскажите, как быть?
    – doomsday
    19 ноя 2014 в 16:16
  • @doomsday: (1 3(2 4)) строка не является числом (как его обычно записывают). Какой ответ ожидается для (1 3(2 4)) строки? Все ли числа состоят только из одной цифры? Что необходимо сделать с этими числами после преобразования в int?
    – jfs
    19 ноя 2014 в 18:48
  • Не нужно совсем вопрос менять (существующие ответы становятся бессмысленными). Решение задачи по обходу дерева и распознавание числа в строке являются несколько разными задачами. ;) В чём неясность состоит? @iksuy уже показал как можно цифру char в int превратить. Мой ответ содержит, как строку в число превратить. Я уже привёл ссылку на пример кода, как отдельные цифры в число собрать. Я не вижу, что эти подсказки использованы в коде в вопросе.
    – jfs
    19 ноя 2014 в 22:07
  • @jfs, у меня несколько чисел, при чем я не знаю, сколько. И каждое число нужно считать отдельно, да и еще и так, чтобы мы знали, сколько раз встречается скобки до этого. Я не понимаю, как сделать это.
    – doomsday
    20 ноя 2014 в 18:02
  • @jfs, т.е. алгоритм следующий: подается формата (22 23(1 4)), программа должна считать количество скобок, встречающихся перед числом, определять число и считать для каждого числа res=a[i]*(0.5)^(b[i]), где a[i] — это какое-то число из строки ввода, b[i] — скобочный итог к моменту, и суммировать такие результаты.
    – doomsday
    20 ноя 2014 в 18:16

2 ответа 2

2

Чтобы преобразовать число в строке str в тип int: int i = stoi(str);

Пример

#include <iostream>
#include <string>

int main() {
    using namespace std;
    for (string line; getline(cin, line); ) {
      int i = stoi(line);
      cout << i << endl;
   }
}

Ввод

1
-1
             2
             3 rest
- 4

Вывод

1
-1
2
3
terminate called after throwing an instance of 'std::invalid_argument'
what():  stoi

Вывод показывает, что stoi() игнорирует пробелы до числа, игнорирует произвольные символы после числа в строке и не разрешает пробелы между минусом и целой частью числа.

11
  • строка в таком случае должна обязательно начинаться с числа. А у меня возможно любое начало. Даже я из строки буду каждый символ в цикле переводить в char, можно ли проверить число в нем или нет???
    – doomsday
    19 ноя 2014 в 10:45
  • @doomsday, можно использовать функцию isdigit из заголовка <cctype>(или <locale>)
    – Alex Krass
    19 ноя 2014 в 12:30
  • @Alex Krass, тут тоже необходимо, чтобы начиналось с числа. Я написал код( добавил его в вопрос), только не пойму почему он каждый раз распечатывает s и k? Ведь он не должен заходить туда(например, (()))..
    – doomsday
    19 ноя 2014 в 13:30
  • @doomsday: не верно. Строка может начинаться с пробелов, stoi() пропускает пробелы и игнорирует символы после числа
    – jfs
    19 ноя 2014 в 18:42
  • @jfs, только он падает при скобках.. И как реализовать мою программу, мне так и не подскази собственно.
    – doomsday
    19 ноя 2014 в 20:31
2

В с++ стандартных средств нету для таких целей. Следует либо найти библиотеку, либо написать самостоятельно дынный функционал. Логика такова: считывается строка, делится на токены по whitespace, проверяется каждый токен, если он состоит только из цифр, то это число. В вашем случае на токены разделение будет хитрее из-за скобочных последовательностей.

Обновление

В вашем случае удобно читать на лету, то есть:

char c;
while((c = getchar()) != '\n'){
    if(c >= '0' && c <= '9') //....
}

а преобразование символа-цифры в число:

int number = (c - '0');

@doomsday, и у вас логическая ошибка.
Нужно так:

if ((chr!='(') && (chr!=')' && (chr!=' ')))
6
  • А если для одного символа char? Не очень понимаю, как реализовать то, что Вы сказали.
    – doomsday
    19 ноя 2014 в 12:22
  • Если для одного, то все гораздо проще - просто проходите по строке, и если это цифра, то переводите её в int и записываете в какой-нибудь массив, например.
    – iksuy
    19 ноя 2014 в 12:28
  • Дело в том, что заранее я не знаю, цифра это или нет.
    – doomsday
    19 ноя 2014 в 12:55
  • Ну, проверить, цифра это или нет, обычно сводится к одной строчке вида: if(c >= '0' && c <= '9') //тогда это цифра
    – iksuy
    19 ноя 2014 в 13:36
  • 2
    Обновил ответ
    – iksuy
    19 ноя 2014 в 13:38

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.