2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 19:39 


05/09/12
2586

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 19:43 
Заслуженный участник
Аватара пользователя


27/04/09
27307

(2 _Ivana.)

Пробелы-то ладно. :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 19:48 


05/09/12
2586

(Оффтоп)

Почему претензии к русским буквам в коде пишутся вне тега оффтопа, а обсуждение алгоритма - внутри? Давайте выходить наружу :-)
arseniiv, посмотрите на те единственные 2 строчки моего кода, где я разбираю скобки входящей строки, и вы сразу поймете как я разбираю подобные ситуации :-)

ЗЫ равное количество открывающих и закрывающих скобок, не содержащее внутри себя знака можно игнорировать. Но я отдельно не анализирую эти случаи, все происходит само собой, стеково-автоматически :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 19:53 
Заслуженный участник
Аватара пользователя


27/04/09
27307
Моё сердце навеки отдано алгоритмам, основанным на грамматиках и комбинаторах. Не вернусь назад, даже алгоритм сортировочной станции не поможет! [Он ведь для таких случаев как раз — операции разбираются, приоритеты и ассоциативность учитываются, можно добавить функции.] :lol: :roll:

(Лень как-то ту страницу открывать; извините, пожалуйста.)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 20:02 


05/09/12
2586
Может тогда просветите не читавших теорию синтаксического разбора, и напишете свой код на грамматиках и комбинаторах? Чтобы можно было оценить красоту и возможности подхода. Только, если можно, на С, бэйсике, Паскале и подобных понятных многим языках :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 20:14 
Заслуженный участник
Аватара пользователя


30/01/06
72408
На псевдокоде! :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 21:41 
Заслуженный участник
Аватара пользователя


06/07/11
5600
кран.набрать.грамота
_Ivana в сообщении #688899 писал(а):
UPD страница с задачей не открывается, уже пару дней глюк какой-то у них на сайте. А я уже хотел отправить туда свой последний код на С, чтобы оценить сравнительную непрожорливость и производительность...

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

Пока могу про свой алгоритм написать.

У меня просматриваются все символы по очереди, в зависимости от того, какой символ встретился, выполняется соответствующее действие. В процессе строится дерево операций. Каждый элемент дерева соответствует операции. Корневая операция - это та, которая по правилам записи будет выполнена последней. Листья дерева - это переменные. У элемента дерева есть две ветви (операнды - их по условиям всегда два) и ссылка на операцию верхнего уровня. Элемент содержит признак "является простым": если да, то у него заполнено поле Value (имя переменной), если нет - то есть ссылки на ветви. Каждая операция имеет тип. Например:
Исходное выражение:
$(a+b)\cdot(c-d)$
Структура после парсинга:
Корневой элемент: тип Mul, "является простым" - false.
Ветви: первая - тип Add, не "простая", имеет в свою очередь две "простые" ветви - a и b. Вторая ветвь у корневого элемента: тип Sub, не "простая", две ветви - c и d. Собственно, я выкладывал проект для Lazarus - там есть визуализатор полученного дерева. Можно скомпилировать и посмотреть.

Я писал, ориентируясь больше на понятность кода и теоретическую возможность его расширения. Тешу себя надеждой, что у меня получилось :wink:
Хотя вон коллеги уже одну утечку памяти нашли...

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 21:50 
Заслуженный участник
Аватара пользователя


27/04/09
27307
_Ivana в сообщении #688940 писал(а):
Может тогда просветите не читавших теорию синтаксического разбора, и напишете свой код на грамматиках и комбинаторах?
«На комбинаторах» уже Xaositect написал. :-) Без них с грамматиками обычно справляются, отделяя их от кода, который по ним разбирает. Если «вшить» грамматику в код, получится много похожего текста и плохая изменяемость: язык изменился — надо переписывать некоторые места, и можно внести новые ошибки; если же данные грамматики отдельно, всё лучше, хотя работает немного медленнее — но это не так страшно.

Самый простой алгоритм, который работает, правда, не со всеми [контекстно свободными] грамматиками, а только с не леворекурсивными LL(1)-грамматиками, — это алгоритм рекурсивного спуска. Он получается из грамматики довольно прямо. (Хотел описать грамматику и алгоритм вместе с генерацией выхода, но получается слишком долго. Если и да, то точно не сегодня. :? )

-- Чт фев 28, 2013 00:52:09 --

(Оффтоп)

Да, я в этой теме только болтаю и ничего не предлагаю по существу, нехорошо получается…

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение27.02.2013, 23:45 


05/09/12
2586
Мне пришла очередная идея, не знаю, будет ли она оптимальнее моего последнего алгоритма, но я попробую её реализовать и сравнить количество тактов выполнения при одинаковых входных строках. Суть идеи - сначала (прямо в массиве исходного выражения) перевести его в постфиксную форму записи (известным оптимальным методом), а потом пробегая по нему формировать выходное выражение, добавляя операции как справа так и слева от стартовой точки в середине массива выходных данных :-)

UPD если, конечно, получится формировать выходную строку без сдвига блоков - если нет, то мой последний алгоритм делает тоже со сдвигами, но сразу по исходной строке.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 02:37 
Заслуженный участник
Аватара пользователя


06/10/08
6322
arseniiv в сообщении #688963 писал(а):
«На комбинаторах» уже Xaositect написал.
Я, кстати, и на C могу (обратите внимание на строки со 127). Освобождения памяти нет, пробелы не обрабатываются, но это несложно дописать.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
#include <stdlib.h>
#include <stdio.h>

typedef enum {
  E_OK = 0,
  E_WRONG = -1,
  E_MEMORY = -2,
} error;

typedef enum {
  FIRST,
  SECOND
} choice;

#define CHECK(err) if (err) return (err)

#define FIELD(ptr, num) (&((ptr)->_##num))

#define DECLARE_SEQ(name, parser1, parser2)                   \
typedef struct result_##name {                                \
  result_##parser1 _1;                                        \
  result_##parser2 _2;                                        \
} result_##name;                                              \
error name(const char ** data, result_##name * result)        \
{                                                             \
  error err = parser1(data, &(result->_1));                   \
  CHECK(err);                                                 \
  err = parser2(data, &(result->_2));                         \
  CHECK(err);                                                 \
  return E_OK;                                                \
}                                                             \

#define DECLARE_SEQ3(name, parser1, parser2, parser3)         \
typedef struct result_##name {                                \
  result_##parser1 _1;                                        \
  result_##parser2 _2;                                        \
  result_##parser3 _3;                                        \
} result_##name;                                              \
error name(const char ** data, result_##name * result)        \
{                                                             \
  error err = parser1(data, &(result->_1));                   \
  CHECK(err);                                                 \
  err = parser2(data, &(result->_2));                         \
  CHECK(err);                                                 \
  err = parser3(data, &(result->_3));                         \
  CHECK(err);                                                 \
  return E_OK;                                                \
}                                                             \

#define DECLARE_ALT(name, parser1, parser2)                   \
typedef struct result_##name {                                \
  choice choice;                                              \
  union {                                                     \
    result_##parser1 _1;                                      \
    result_##parser2 _2;                                      \
  } value;                                                    \
} result_##name;                                              \
error name(const char ** data, result_##name * result)        \
{                                                             \
  error err = parser1(data, &(result->value._1));             \
  if (err) {                                                  \
    result->choice = SECOND;                                  \
    return parser2(data, &(result->value._2));                \
  } else {                                                    \
    result->choice = FIRST;                                   \
    return E_OK;                                              \
  }                                                           \
}                                                             \

#define DECLARE_STAR(name, parser)                            \
typedef struct result_##name {                                \
  size_t num;                                                 \
  result_##parser * items;                                    \
} result_##name;                                              \
error name(const char ** data, result_##name * result)        \
{                                                             \
  result->items = NULL;                                       \
  size_t rec_size = sizeof(result_##parser);                  \
  size_t num = 0;                                             \
  error err = E_OK;                                           \
  while (!err) {                                              \
    result_##parser * tmp = realloc(result->items,            \
                                    rec_size * (num + 1));    \
    if (tmp == NULL) {                                        \
      free(result->items);                                    \
      result->items = NULL;                                   \
      result->num = 0;                                        \
      return E_MEMORY;                                        \
    } else {                                                  \
      result->items = tmp;                                    \
      err = parser(data, result->items + num);                \
      num++;                                                  \
    }                                                         \
  }                                                           \
  result->num = num - 1;                                      \
  return E_OK;                                                \
}                                                             \

#define DECLARE_GET(name, var, condition)                     \
typedef char result_##name;                                   \
error name(const char ** data, result_##name * result)        \
{                                                             \
  char var;                                                   \
  var = **data;                                               \
  if (condition) {                                            \
    *result = var;                                            \
    (*data)++;                                                \
    return E_OK;                                              \
  } else {                                                    \
    return E_WRONG;                                           \
  }                                                           \
}                                                             \

#define PREDECLARE_REC(name)                                  \
typedef void * result_##name;                                 \
error name(const char ** data, result_##name * result);       \

#define DECLARE_REC(name, parser)                             \
error name(const char ** data, result_##name * result)        \
{                                                             \
  *result = malloc(sizeof(result_##parser));                  \
  if (*result == NULL)                                        \
    return E_MEMORY;                                          \
  return parser(data, (result_##parser *)(*result));          \
}                                                             \

DECLARE_GET(left, c, c=='(')
DECLARE_GET(right, c, c==')')
DECLARE_GET(letter, c, 'a' <= c && c <= 'z')
DECLARE_GET(addop, c, c == '+' || c == '-')
DECLARE_GET(mulop, c, c == '*' || c == '/')
DECLARE_GET(eoinp, c, c == '\0')

PREDECLARE_REC(expr_rec)

DECLARE_SEQ3(bracketed, left, expr_rec, right)
DECLARE_ALT(element, letter, bracketed)

DECLARE_SEQ(opelement, mulop, element)
DECLARE_STAR(elements, opelement)
DECLARE_SEQ(summand, element, elements)

DECLARE_SEQ(opsummand, addop, summand)
DECLARE_STAR(summands, opsummand)
DECLARE_SEQ(expr, summand, summands)

DECLARE_REC(expr_rec, expr)

DECLARE_SEQ(final, expr, eoinp)

void process_expr(result_expr * result);

void process_element(result_element * result)
{
  if (result->choice == FIRST) {
    printf("%c", result->value._1);
  } else {
    result_expr * subexpr = (result_expr *)result->value._2._2;
    process_expr(subexpr);
  }
}

void process_summand(result_summand * result)
{
  result_element * first = FIELD(result, 1);
  result_elements * rest = FIELD(result, 2);
  if (rest->num == 0) {
    process_element(first);
  } else {
    for (int i = rest->num - 1; i >= 0; i--) {
      if (rest->items[i]._1 == '*') {
        printf("MUL(");
      } else {
        printf("DIV(");
      }
    }
    process_element(first);
    for (int i = 0; i < rest->num; i++) {
      printf(", ");
      process_element(FIELD(rest->items + i, 2));
      printf(")");
    }
  }
}

void process_expr(result_expr * result)
{
  result_summand * first = FIELD(result, 1);
  result_summands * rest = FIELD(result, 2);
  if (rest->num == 0) {
    process_summand(first);
  } else {
    for (int i = rest->num - 1; i >= 0; i--) {
      if (rest->items[i]._1 == '+') {
        printf("ADD(");
      } else {
        printf("SUB(");
      }
    }
    process_summand(first);
    for (int i = 0; i < rest->num; i++) {
      printf(", ");
      process_summand(FIELD(rest->items + i, 2));
      printf(")");
    }
  }
}

void process(result_final * result)
{
  process_expr(FIELD(result, 1));
  printf("\n");
}

int main() {
  result_final result;
  char * input = "(a-b-c*d/(a-b))*(a+b*(c-d*e+h)/g)";
  const char * ptr = input;
  error err = final(&ptr, &result);
  process(&result);
  fflush(stdout);
  return 0;
}
 
При желании в такой же манере можно в макросах объявить функцию process_##name, с удобным интерфейсом, тогда получится еще лучше.

arseniiv в сообщении #688963 писал(а):
если же данные грамматики отдельно, всё лучше, хотя работает немного медленнее — но это не так страшно.
В классическом подходе (yacc и его потомки - генераторы парсеров для разных языков) грамматику транслируют в код на основном языке и компилируют. По эффективности это было лучше комбинаторов до недавних дней, когда в компиляторах ФЯ начали делать нетривиальную оптимизацию.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 12:39 
Заслуженный участник
Аватара пользователя


30/01/06
72408

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 13:31 
Заслуженный участник
Аватара пользователя


06/07/11
5600
кран.набрать.грамота
rockclimber в сообщении #688960 писал(а):
_Ivana в сообщении #688899 писал(а):
UPD страница с задачей не открывается, уже пару дней глюк какой-то у них на сайте. А я уже хотел отправить туда свой последний код на С, чтобы оценить сравнительную непрожорливость и производительность...

Я тоже уже который день хочу... Я успел даже еще одну задачку там посмотреть и решить. Когда страницу открываешь, там выводится предложение написать админу. Я написал, будем ждать реакцию.
Починили, бегом сдаваться!!! 8-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 23:23 


05/09/12
2586
Несколько десятков раз пытался отправить свое решение на сайт где выложена задача. Оформил ввод-вывод по С++ стандарту, допилил код что он нормально работает в С++ например здесь http://liveworkspace.org, выводит правильно преобразованное выражение. Но исходный сайт все равно дает вердикт - неправильный ответ! :-) Причем, не дает посмотреть как выглядит выходная строка... Я отчаялся убедить его, что решение правильное :-)
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>

int main(void)
{
   char out_str[275]; // 39*7+1+1
        int level=0, order=0, last_order=-1;
        char c, op;
        char *p_in, *p_out, *p_op, *p_arg;
   char in_str[81];
       
   p_in = in_str;
    while (std::cin.get(c)) {*p_in++ = c;} *p_in++ = 0;
   
  p_in = in_str; p_out = out_str;
   while (1) {
                c = *p_in++;
                if (c == ' ') {}
                else if (c == '(') { level++;}
                else if (c == ')') { level--;}
                else if ( (c == '+')||(c == '-')||(c == '*')||(c == '/')||(!c) ) {
                        order = 100 + (level<<1);
                        if ( (c == '*')||(c == '/') ) { order++;} else if (!c) { order = 0;}
                       
                        if (order <= last_order){
                                p_op = p_out - 5;
                                while (p_op >= out_str) {
                                        op = *p_op;
                                        if ( (op == '+')||(op == '-')||(op == '*')||(op == '/') ) {
                                                if (*(p_op + 1) < order) break;
                                                                       
                                                p_arg = p_op + 4;
                                                while (p_arg < p_out) {*(p_arg - 1) = *p_arg++;}
                                                *(p_arg - 1) = ')'; *(p_op + 2) = ',';
                                                p_arg = p_op - 3;
                                                while ( (p_arg >= out_str) & (*p_arg != ' ') ) {*(p_arg + 4) = *p_arg--;}
                                                p_arg++;
                                                if              (op == '+') { *p_arg++ = 'A';*p_arg++ = 'D';*p_arg++ = 'D';*p_arg++ = '(';}
                                                else if (op == '-') { *p_arg++ = 'S';*p_arg++ = 'U';*p_arg++ = 'B';*p_arg++ = '(';}
                                                else if (op == '*') { *p_arg++ = 'M';*p_arg++ = 'U';*p_arg++ = 'L';*p_arg++ = '(';}
                                                else if (op == '/') { *p_arg++ = 'D';*p_arg++ = 'I';*p_arg++ = 'V';*p_arg++ = '(';}
                                        }                                      
                                        p_op = p_op - 7;
                                }
                        }
                        if (!c) break;
                        *p_out++=' '; *p_out++=' '; *p_out++=c; *p_out++=order; *p_out++=' '; *p_out++=' ';
                        last_order = order;
                }
                else { *p_out++ = c;}      
        }
   *p_out++=0;
        //p_out = out_str;
        //while (*p_out) {std::cout.put(*p_out++);} //{std::cout << *p_out++;} //{cout.put(c);}                
   std::cout << out_str;
        //std::cout << std::endl;  
                       
        return 0;
}

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 23:34 
Заслуженный участник
Аватара пользователя


06/10/08
6322
_Ivana
У меня Ваша программа неправильно работает
Код:
$ g++ a.cpp
$ ./a.out
a + (b-c)/(c*d)
a  +d  SUB(b,c)  /e  c  *g  d

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 23:41 


05/09/12
2586
А на http://liveworkspace.org и в моей АВР студии
Код:
a + (b-c)/(c*d)
stdout:
ADD(a,DIV(SUB(b,c),MUL(c,d)))
я ни разу не работал с С++, подозреваю что какой то мелкий момент различия компиляторов. Похоже на неотработку нулевого символа в конце строки.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 89 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group