Внимание! Прочитайте, пожалуйста, текст в правой колонке (внизу).
Внимание! Прочитайте, пожалуйста, текст в правой колонке (внизу). Внимание! Прочитайте, пожалуйста, текст в правой колонке (внизу). Homepage Карта сайта Версия для печати

Джентльменский набор Web-разработчика   Ларри Уолл о Perl6   Наблы Система Orphus
 

10. Рекурсивный main(), или программирование квадратиком

[6 ноября 2001 г.]

  Карл у Клары украл кораллы,
а Клара у Карла украла кларнет

Язык сломаешь

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

Тем временем, один человек по имени Дмитрий Мельник, не теряя этого самого времени, решил посжимать программы на практике. Угадайте, что делает следующий код.

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

Листинг 1
#include <stdio.h>
float err=0, vars[27], q, r; char s1[1024]=" ", *st=s1+1, *x, *y, g, f=1;
float main(char *s, int i1, int i2, int u)
{  char c=0, op[]=",=+-*/", *p, *t, d; int br=0, i;
   if (f) goto l1; else if (i1>i2) { err=err?1:!u; return 0; }
   for (p=op; *p; p++)
     for (i=(*p=='='?i1:i2); d=s[i],(*p=='='?i<=i2:i>=i1); (*p=='='?i++:i--))
       if(!br&&d==*p){c=*p;goto l;} else if(d=='('||d==')')br+=(d=='('?1:-1);
l: if (c==',') { main(s, i1, i-1, 0); return main(s, i+1, i2, 0); }
   if(d=s[i1]&223,c=='=') return  i1==i-1&&d>64&&d<91?vars[d-65]=main(s,i+1,i2,0):(err=1,0);
   if((s[i-1]&223)!='E'&&(c=='+'||c=='-'))return main(s,i1,i-1,1)+(44-c)*main(s,i+1,i2,0);
   if (c=='/') {q=main(s, i+1, i2, 0); return q?main(s, i1, i-1, 0)/q:(err=1);}
   if (c=='*') return main(s, i1, i-1, 0)*main(s, i+1, i2, 0);
   if(s[i1]=='(') return s[i2]==')'?main(s, i1+1, i2-1, 0):(err=1,0);
   if (i1==i2 && (s[i1]&223)>64 && (s[i1]&223)<91) return vars[(s[i1]&223)-65];
     return (sscanf(s+i1,"%g%n",&r,&i) && i==i2-i1+1)?r:(err=1, 0);
l1:for(f=0,gets(st),x=st,y=st; err=0,g=*x,(x>st?*(x-1):*st); x++)
     if(g!=' '||*(y-1)>47&&*(y-1)<58&&*(x+1)>47&&*(x+1)<58)*(y++)=(g?*x:0);
   if (printf((err?"Error!\n\n":"%g\n\n"), main(st, 0, y-st-2, 0))) goto l1;
}

Ну что, догадались? Нет?.. Тогда откомпилируйте программу и запустите (не важно — в Unix или же в Borland C 3.1). Введите выражение:

d=8, 1+(a=b=2*(c=2+d))/5+a

Вы получите в ответ:

25

Поразительно, не правда ли?.. При таком объеме он еще и правильно считает. Вот что пишет по этому поводу сам автор.

Калькулятор v21a - 20 строк!
Поддерживаются стандартные арифметические операции над данными типа float, однобуквенные переменные, оператор присваивания (в том числе "сквозной", например x=y=z=1), а также оператор «запятая». При записи чисел с плавающей точкой возможно использование формата [+-]dddE[+-]ddd, например, 2e-2. Реализован контроль синтаксических ошибок и деления на ноль. Работоспособность проверялась на Borland C 3.1. Для того, чтобы программа скомпилировалась, необходимо запретить использование синтаксиса C++, а чтобы правильно работала, необходимо использовать соглашения о вызовах языка C (не Pascal!). Кстати, эти требования соответствуют установкам BC 3.1 по умолчанию.

Дмитрий Мельник,
21 сентября 2000 г.

По новейшим сведениям, 20 строк — не предел для такой задачи. Имеются рабочие версии и размером в 13 строк! Правда, алгоритм там применяется немного другой, менее универсальный.

Напоследок приведу еще одну версию этой программы, которая чуть менее квадратна и более структурирована, зато длиннее. И в ней нет рекурсивного main(), что само по себе уже не так интересно.

Листинг 2
#include <stdio.h>
#include <string.h>
float Vars[256],E,r;
float Eval(unsigned char* s, unsigned char *f, float e)
{ int d, in, n; unsigned char *op=",=+-*/", *p, q;
  for(q=0; *op && !q; op+=!q)
    for(in=0, d=(*op!='=')?-1:1, p=(d<0)?f-1:s; !q && p>=s && p<f; p+=!q*d)
      in+=(*p=='(') ? 1 : (*p==')') ? -1 : (*p==*op&&!in) ? (q=1) : 0;
  if(!q&&*s=='('&&f[-1]==')' || s==f&&e) return s==f? 0 : Eval(s+1,f-1,0);
  if(*op==',') return Eval(s,p,0), Eval(p+1,f,0);
  if(*op=='=' && p-s==1) return Vars[p[-1]]=Eval(p+1,f,0);
  if(*op=='+' || *op=='-') return Eval(s,p,1)+(44-*op)*Eval(p+1,f,0);
  if(*op=='*') return Eval(s,p,0)*Eval(p+1,f,0);
  if(*op=='/' && ((e=Eval(p+1,f,0))<-1e-10||e>1e-10)) return Eval(s,p,0)/e;
    else if(*op=='/') goto Z;
  if((*s&0xDF)>='A' && (*s&0xDF)<='Z' && f-s==1) return Vars[*s];
  if(sscanf(s,"%g%n",&e,&n) && n==f-s) return e;
E:if(!E) printf("! Syntax error near '%.*s'\n",f-s+2,s-1); return E=1.232e5;
Z:if(!E) printf("! Divide by 0 near '%.*s'\n",f-p+1,p); return E=1.322e5;
}
void main(void)
{   unsigned char st[256]=" ",i;
S:  printf("\nExpression (Enter to quit)> "); if(!*gets(st+1)) return;
    for(i=1; i<strlen(st); i++) if(st[i]==' ') strcpy(st+i,st+i--+1);
    if(E=0,r=Eval(st+1,st+strlen(st),0),!E) printf("Result: %g\n",r);
    goto S;
}

Зоркий глаз заметит, а внимательный нос учует, что тут использовано то же самое «ядро» разбора скобочных выражений, предложенное изначально Дмитрием Мельником. Его (ядра, а не Дмитрия) достоинства — удивительная простота добавления новых операторов с различными приоритетами, причем как левосторонних, так и правосторонних.

Да, и последнее. Никогда так не делайте.

 
Рекламный блок
   

Важное объявление:
    автор категорически против копирования и распространения в Интернете всех статей «Куроводства» с возрастом, меньшим 6 месяцев. Печальный опыт «расползания» чрезвычайно устаревших ошибочных версий статьи про Apache действительно объясняет такое решение.

Орфография на «Куроводстве»:
    если вы заметили орфографическую, стилистическую или другую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Выделенный текст будет немедленно отослан вебмастеру, а Вы даже ничего и не заметите — настолько быстро все произойдет.

На заметку:
    если вы уже вскипели насчет дизайна этой страницы, то присмотритесь повнимательнее к названию, почитайте FAQ, сходите по лебедевским местам, как это уже предлагалось выше. Можно ли считать пародию плагиатом? Надеюсь, что нет.

Параметры этой страницы
   
GZip

Ссылки от спонсоров
    Профессиональный стабильный хостинг. Многолетний опыт, качество, привлекательные цены. | Вспомогательное оборудование для ларн larn32.ru.


Дмитрий Котеров | 6 ноября 2001 г. ©1999-2016 | Генеральный спонсор: Хостинг «Джино» | Контакт Вернуться к оглавлению