Задача по C - C/C++

Помогите решить что добавить в функцию, я уже извертелся...

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

Примеры:
Получает --> Возвращает
5 --> 5, len=1
(4+9) --> 13, len=5
((7-9)+(6+3)) --> 7, len=13
(4+(7-(4+1))) --> 6, len=13

Пример не правильных строк:
2+5 --> нет скобок
(1+2+3)--> больше чем 2 числа не разделенных скобками

Проверять не правильные строки не надо, то есть предположительно строка передаваемая в функцию верная.
int calc( char* s, int* len )

{
    if( *s == '(' )
 {
   // We're in the beginning of a complex expression
      int left_len, right_len, left_val, right_val;
      left_val = calc( ______, &left_len );
      char op = s[_________];
      right_val = calc( _______, _______ );
      *len = _________________;
      if( op == '+' )
          _____________________;
      else if( op == '-' ) 
          _____________________;
 }
    else
  {
     // We're on a simple, one-digit number
      *len = ______;
      return ______;
  }
}
//Пример main
int main()
{
int len;
printf( "%d", calc( "((7-9)+(6+3))", &len ) );
printf( "%d", len );
return 0;
}

Здравствуйте, Лис, Вы писали:

Лис>Помогите решить что добавить в функцию, я уже извертелся...

Лис>Задача.
Лис>Функция получает строку и указатель на переменную. Возврат функции это число которое должно получиться, а в переменной должна быть длина строки.
Лис>Алгоритм рекурсивный.

Лис>Примеры:
Лис>Получает --> Возвращает
Лис> 5 --> 5, len=1
Лис> (4+9) --> 13, len=5
Лис>((7-9)+(6+3)) --> 7, len=13
Лис>(4+(7-(4+1))) --> 6, len=13

Похоже на тесты от MS

Здравствуйте, Лис, Вы писали:

Лис>Помогите решить что добавить в функцию, я уже извертелся...

Лис>Задача.
Лис>Функция получает строку и указатель на переменную. Возврат функции это число которое должно получиться, а в переменной должна быть длина строки.

Тут одной функцией вряд ли обойдешься. Читай про синтаксический анализ.

B>Похоже на тесты от MS

Это в Технионе(Technion) нам задали, если слышал о таком)

Я сижу над этим неделю и отчаялся)

Здравствуйте, Socrat, Вы писали:

S>Здравствуйте, Лис, Вы писали:

Лис>>Помогите решить что добавить в функцию, я уже извертелся...

Лис>>Задача.
Лис>>Функция получает строку и указатель на переменную. Возврат функции это число которое должно получиться, а в переменной должна быть длина строки.

S>Тут одной функцией вряд ли обойдешься. Читай про синтаксический анализ.

К сожалению ничего добавлять или изменять нельзя, только заполнить пропущенное.

Здравствуйте, Лис, Вы писали:

Лис>К сожалению ничего добавлять или изменять нельзя, только заполнить пропущенное.

Примерно так:

int calc( char* s, int* len )
{
    if( *s == '(' )
   {
   // We're in the beginning of a complex expression
      int left_len, right_len, left_val, right_val;
      left_val = calc( s+1, &left_len );
      char op = s[left_len];
      right_val = calc( s+left_len+1, &right_len);
      *len = left_len+right_len+3;
      if( op == '+' )
          left_val+right_val;
      else if( op == '-' ) 
          left_val-right_val;
   }
    else
   {
     // We're on a simple, one-digit number
// А тут уж сам подумай...
      *len = ______;
      return ______;
   }
}

Здравствуйте, Лис, Вы писали:

Лис>Функция получает строку и указатель на переменную. Возврат функции это число которое должно получиться, а в переменной должна быть длина строки.

Пусть функции на вход подали такое:

((1+2)+(3+(4+5)))

Сколько раз и с какими аргументами calc должна вызвать себя?

Например, в самом начале она пойдет по первой ветке, увидев, что *s == '('. s[1] явно начинает первый операнд сложения или вычитания. Теперь нужно выяснить, где он заканчивается, что за знак стоит за ним и где начинается второй. Как здесь нужно вызвать calc? Обрати внимание на то, что len передается по указателю — к чему бы это?

int Calc(char * c,  int* len )
{
  if (*c == '(') 
  { // begin new layer
    int newLen = 0;
    (*len)++; // ++  to skip '('
    int left = Calc(c + 1, &newLen);
    c+=(++newLen);// ++ to skip +/-
    int right = Calc(c + 1, &newLen);
    (*len)+=(++newLen); // ++ to skip ')'
    return (*c == '+')?(left + right):(left - right);
  }
  else
  { 
   (*len)++;
   return *c - '0';
  }
}

Здравствуйте, Socrat, Вы писали:

S>Здравствуйте, Лис, Вы писали:

Лис>>К сожалению ничего добавлять или изменять нельзя, только заполнить пропущенное.

S>Примерно так:
S>

S>int calc( char* s, int* len )
S>{
S>    if( *s == '(' )
S>   {
S>   // We're in the beginning of a complex expression
S>      int left_len, right_len, left_val, right_val;
S>      left_val = calc( s+1, &left_len );
S>      char op = s[left_len];
S>      right_val = calc( s+left_len+1, &right_len);
S>      *len = left_len+right_len+3;
S>      if( op == '+' )
S>          left_val+right_val;
S>      else if( op == '-' ) 
S>          left_val-right_val;
S>   }
S>    else
S>   {
S>     // We're on a simple, one-digit number
S>// А тут уж сам подумай...
S>      *len = ______;
S>      return ______;
S>   }
S>}
S>

давай теперь ты "сам подумай" ...
"((7-9)+(6+(3-1)))" — получи 6

П.с. Этюд: найти ошибки в коде

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, Лис, Вы писали:

Лис>>Функция получает строку и указатель на переменную. Возврат функции это число которое должно получиться, а в переменной должна быть длина строки.

RO>Пусть функции на вход подали такое:

((1+2)+(3+(4+5)))

Сколько раз и с какими аргументами calc должна вызвать себя?

RO>Например, в самом начале она пойдет по первой ветке, увидев, что *s == '('. s[1] явно начинает первый операнд сложения или вычитания. Теперь нужно выяснить, где он заканчивается, что за знак стоит за ним и где начинается второй. Как здесь нужно вызвать calc? Обрати внимание на то, что len передается по указателю — к чему бы это?

У меня есть такое решение, но в len на выходе всегда остается 1, что не достаточно по требования программы.

int calc( char* s, int* len )
{
 if( *s == '(' )
 {
        // We're in the beginning of a complex expression
        int left_len, right_len, left_val, right_val;
        left_val = calc(s+1, &left_len );
        char op = s[(strlen(s)-left_len)+1];
        right_val = calc(s+(strlen(s)-left_len+2), &right_len);
        *len = right_len-1;
        if( op == '+' )
          return  left_val+right_val;
        else if( op == '-' )
          return  left_val-right_val;
}
 else
 {
     // We're on a simple, one-digit number
     *len = strlen(s);
     return *s-'0';
 }
}

Здравствуйте, Caracrist, Вы писали:

C>

C>int Calc(char * c,  int* len )
C>{
C>  if (*c == '(') 
C>  { // begin new layer
C>    int newLen = 0;
C>    (*len)++; // ++  to skip '('
C>    int left = Calc(c + 1, &newLen);
C>    c+=(++newLen);// ++ to skip +/-
C>    int right = Calc(c + 1, &newLen);
C>    (*len)+=(++newLen); // ++ to skip ')'
C>    return (*c == '+')?(left + right):(left - right);
C>  }
C>  else
C>  { 
C>   (*len)++;
C>   return *c - '0';
C>  }
C>}
C>

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

Здравствуйте, Лис, Вы писали:

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

Тогда исправь две ошибки у Socrata и всё.

Здравствуйте, Caracrist, Вы писали:

C>Здравствуйте, Лис, Вы писали:

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

C>Тогда исправь две ошибки у Socrata и всё.

Сейчас попробую...

Мой вариант.

int calc( char* s, int* len )
{
    if( *s == '(' )
    {
        // We're in the beginning of a complex expression
        int left_len, right_len, left_val, right_val;
        left_val = calc( s+1, &left_len );
        char op = s[ left_len + 1 ];
        right_val = calc( s+left_len+2,&right_len );
        *len = (left_len+right_len+1+1+1);
        if( op == '+' )
            return left_val + right_val;
        else if( op == '-' ) 
            return left_val - right_val;
    }
    else
    {
        // We're on a simple, one-digit number
        *len = 1;
        return *s - 48;
    }
}
//Пример main
int main()
{
    int len;
    printf( "%d", calc( "((2+3)-(1+(4+(7-(4+1)))))", &len ) );
    printf( "%d", len );
    return 0;
}

А вот изменения в WinMerge.

P.S. Извините, если у кого рисунок съел много траффика. Увы, на РСДН нету раскрывающихся блоков для сообщений.

Всем большое спасибо за помощь.

Здравствуйте, Yuki-no Tenshi, Вы писали:

YNT>А вот изменения в WinMerge.
YNT>http://www.image2blog.com/images/2010/01/27/fceaa451230673e2f9d0898d4ea6051a.jpg
YNT>Извините, если у кого рисунок съел много траффика. Увы, на РСДН нету раскрывающихся блоков для сообщений.

	Скрытый текст
	Кто же так делает скриншоты, да еще и сохраняет в JPEG? Вот PNG, всего 52 КБ: А насчет [cut], те, кто считают трафик, великодушно простят тебе его неиспользование, ибо он появился лишь несколько дней назад :-)

Здравствуйте, Roman Odaisky.

	Скрытый текст
	На счет CUT спасибо. .

Вообще странно... Вы уверены что в вашей задаче должны использоваться только две арифмитические операции: "+" и "-"? Наличие скобок в примере смущает, так как не вижу особого смысла в них для операций с одинаковым приоритетом. У меня такое чувство, что задача сильно упрощена... Хотя вполне возможно что так и есть.

Мой вариант:

#include <stdlib.h>

int calc( char* s, int* len )
{
    if( *s == '(' )
    {
        // We're in the beginning of a complex expression
        int left_len, right_len, left_val, right_val;
        left_val = calc( s+1, &left_len );
        char op = s[ strlen(s)-left_len+1 ];
        right_val = calc( s+(strlen(s)-left_len+2), &right_len );
        *len = '\0' == s[strlen(s)-right_len+2] ?  strlen(s) : right_len-1 ;
        if( op == '+' )
            right_val = left_val + right_val;
        else if( op == '-' ) 
            right_val = left_val - right_val;
    }
    else
    {
        // We're on a simple, one-digit number
        *len = strlen(s);
        return atoi(s);
    }
}

//Пример main
int main(int argc, char* argv[])
{
    int len;

    //printf( "4 = %d : ", calc( "4", &len ) );
    //printf( "%d\n", len );

    printf( "(4+9) = %d : ", calc( "(4+9)", &len ) );
    printf( "%d\n", len );

    printf( "(4+(3+2)) = %d : ", calc( "(4+(3+2))", &len ) );
    printf( "%d\n", len );

    printf( "(4+(7-(4+1))) = %d : ", calc( "(4+(7-(4+1)))", &len ) );
    printf( "%d\n", len );

    printf( "((7-9)+(6+3)) = %d : ", calc( "((7-9)+(6+3))", &len ) );
    printf( "%d\n", len );

    printf( "(3+((7-9)+(6-3))) = %d : ", calc( "(3+((7-9)+(6-3)))", &len ) );
    printf( "%d\n", len );

    printf( "(4+((3-5)+(3+((7-9)+(6-3))))) = %d : ", calc( "(4+((3-5)+(3+((7-9)+(6-3)))))", &len ) );
    printf( "%d\n", len );
    return 0;
}

	От:	Лис
	Дата:	27.01.10 14:16
	Оценка:

	От:	blackhearted
	Дата:	27.01.10 14:23
	Оценка:

	От:	Socrat
	Дата:	27.01.10 14:32
	Оценка:	3 (1)

	От:	Лис
	Дата:	27.01.10 14:34
	Оценка:

	От:	Лис
	Дата:	27.01.10 14:37
	Оценка:

	От:	Roman Odaisky
	Дата:	27.01.10 15:03
	Оценка:	3 (1)

От:	Caracrist	https://1pwd.org/
Дата:	27.01.10 16:28
Оценка:	3 (1)

	От:	Yuki-no Tenshi
	Дата:	27.01.10 20:37
	Оценка:	3 (1)

	От:	stapter
	Дата:	28.01.10 12:36
	Оценка:

	От:	nen777w
	Дата:	30.01.10 13:41
	Оценка: