Внимание! Прочитайте, пожалуйста, текст в правой колонке (внизу).
Внимание! Прочитайте, пожалуйста, текст в правой колонке (внизу). Внимание! Прочитайте, пожалуйста, текст в правой колонке (внизу). 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

Ссылки от спонсоров
   


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