Числовая прямая

[ThomasHoffman]

На числовой прямой будем рассматривать только точки с целой координатой (в дальнейшем будем называть их целыми точками). Рассмотрим некоторое количество числовых промежутков, начало и конец которых являются целыми точками (предполагается, что начало и конец промежутка также входят в промежуток). С множествами чисел разрешается выполнять операции объединения, пересечения и разности:
Множество точек A+B содержит целые точки, которые принадлежат множеству A или множеству B (операция объединения).
Множество точек A*B содержит целые точки, которые принадлежат одновременно и множеству A, и множеству B (операция пересечения).
Множество точек A-B содержит целые точки, которые принадлежат множеству A, но не принадлежат множеству B (операция разности множеств).

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

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

Вход: файл input.txt, содержащий несколько строк с описанием промежутков в следующем формате:
имя начало конец
После описания промежутков (не более 26) в последней строке файла input.txt следует выражение, содержащие имена промежутков (только из описанного выше набора), знаки операций над промежутками (+, – и *) и круглые скобки. Прочих символов (в том числе пробелов и других разделителей) выражение не содержит.

Ограничения:в описании каждого отрезка: имя – заглавная буква латинского алфавита (имя промежутка), начало и конец – целые числа от -2000000000 до 2000000000 (соответственно, начало и конец промежутка); длина выражения не превосходит 250.

Выход: файл output.txt, содержащий одну или несколько строк – перечисление непересекающихся промежутков, из которых состоит результирующее множество точек (результат применения заданного выражения к предложенному набору промежутков). В каждой строке приводится два целых числа – начало и конец промежутка, разделенные пробелом. Промежутки перечисляются в порядке расположения на числовой прямой слева направо (то есть в порядке возрастания координат левых концов).

Дополнительные ограничения: расстояние между соседними промежутками в выходном файле (разность между правым концом одного промежутка и левым концом другого) должно быть строго больше 1. Иначе говоря, смежные промежутки (те, между которыми нет целых точек) «сливаются» в один.

Пример 1:

input.txt output.txt
A 1 5
B 3 7
A-B 1 2

Прошу помочь с этой задачкой, парюсь уже 5 дней, а решить никак не могу. Идеи есть, но реализация хромает. Прекрасно знаю, что строки названия промежутков и строки значений надо записать в отдельные массивы. Сделал. Знаю, что надо сперва обращать внимание на скобки, а затем на действия в них. Но как? Я вроде попытался в скобках посмотреть, но получается фигня какая-то. Буду благодарен. Мне важен сам принцип работы, как и куда писать, ибо понимание самой задачи есть.

Вот само считывание и преобразование значений:

program com;
var s,x,y,c:array [0..100] of string;
    c1:array[0..100] of char;
    x1,y1:array[0..100] of longint;
    i,n,j,k,l,sum,code:longint;
    d,cc,xx,yy:string;
    f1,f2:text;
begin
    assign(f1,'input.txt');
    assign(f2,'output.txt');
    reset(f1);
    rewrite(F2);
    code:=0;
    n:=0;
    while not eof(f1) do begin inc(n);
                               readln(f1,s[n]);
                         end;
                         
    d:=s[n];dec(n);
   for i:=1 to n do begin cc:=s[i];c[i]:=cc[1];
                           delete(s[i],1,2);
                     end;
   for i:=1 to n do begin xx:=s[i];x[i]:=xx[1];
                           val(x[i],x1[i],code);
                     end;
    for i:=1 to n do begin yy:=s[i];y[i]:=yy[3];
                           val(y[i],y1[i],code);
                     end;
    close(f1);
    close(f2);
end.

________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!

Модератор.

[Abstraction]

0) В условии отсутствует важная деталь: операторы одного приоритета вычисляются либо слева направо, либо справа налево, либо в каком-то ином порядке. Будем считать, что они вычисляются справа налево.

Если игнорировать скорость, то вот вариант алгоритма:
1) Есть функция eval, которая идёт по выражению и вычисляет его, возвращая объект пользовательского типа "набор промежутков" по достижении либо конца строки, либо закрывающей скобки; в качестве побочного эффекта функция сдвигает "курсор" по выражению на конец вычисленного выражения.
2) При обнаружении открывающей скобки в качестве аргумента eval вызывает сама себя, сдвинув "курсор" на 1. Возвращённое значение есть значение аргумента в скобках; также по окончании рекурсивного вызова eval сдвигает курсор ещё раз. При обнаружении закрывающей скобки курсор сдвигается на 1 назад перед выходом.
3) При обнаружении буквы в качестве аргумента eval считает значением аргумента отрезок, соответствующий этой букве.
4) eval "накапливает" текущий результат, изначально равный пустому множеству, и возвращает его в конце своей работы.
5) При обнаружении оператора, eval определяет его приоритет. Если он больше либо равен текущему приоритету, применяется операция, соответствующая оператору, к текущему результату и результату работы функции eval с приоритетом, равным приоритету оператора.
6) Если приоритет обнаруженного оператора меньше текущего, курсор отодвигается на шаг назад и eval возвращает текущий результат.
7) Вызов eval применительно ко входному выражению с приоритетом, равным наименьшему возможному, возвращает значение этого выражения.

Пример вычисления. Выражение A+B*C*(B*A-D)+С. Курсор обозначается точкой. Стек вызовов eval растёт слева направо. Для каждого вызова eval указаны приоритет и текущий результат. Знак в конце текущего результата означает, что eval прервала своё выполнение, уже "определившись" с операцией и лишь дожидаясь значения второго операнда.

.A+B*C*(B*A-D)+С  eval(1,0) //(4)
A.+B*C*(B*A-D)+С  eval(1,A) //(3)
A+.B*C*(B*A-D)+С  eval(1,A+) //(5)
A+.B*C*(B*A-D)+С  eval(1,A+) eval(1,0) //(4)
A+B.*C*(B*A-D)+С  eval(1,A+) eval(1,B) //(3)
A+B*.C*(B*A-D)+С  eval(1,A+) eval(1,B*) //(5)
A+B*.C*(B*A-D)+С  eval(1,A+) eval(1,B*) eval(2,0) //(4)
A+B*C.*(B*A-D)+С  eval(1,A+) eval(1,B*) eval(2,C) //(3)
A+B*C*.(B*A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) //(5)
A+B*C*.(B*A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0) //(4)
A+B*C*(.B*A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() //(2)
A+B*C*(.B*A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,0) //(4)
A+B*C*(B.*A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B) //(3)
A+B*C*(B*.A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*) //(5)
A+B*C*(B*.A-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*) eval(2,0) //(4)
A+B*C*(B*A.-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*) eval(2,A) //(3)
A+B*C*(B*A-.D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*) eval(2,A) //(6)
A+B*C*(B*A.-D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A)
A+B*C*(B*A-.D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A-) //(5)
A+B*C*(B*A-.D)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A-) eval(1,0) //(4)
A+B*C*(B*A-D.)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A-) eval(1,D) //(3)
A+B*C*(B*A-D).+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A-) eval(1,D) //(1)
A+B*C*(B*A-D.)+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A-D) //(2)
A+B*C*(B*A-D).+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,0() eval(1,B*A-D) //(1)
A+B*C*(B*A-D).+С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,B*A-D) //(2)
A+B*C*(B*A-D)+.С  eval(1,A+) eval(1,B*) eval(2,C*) eval(2,B*A-D) //(6)
A+B*C*(B*A-D).+С  eval(1,A+) eval(1,B*) eval(2,C*(B*A-D))
A+B*C*(B*A-D)+.С  eval(1,A+) eval(1,B*) eval(2,C*(B*A-D)) //(6)
A+B*C*(B*A-D).+С  eval(1,A+) eval(1,B*C*(B*A-D))
A+B*C*(B*A-D)+.С  eval(1,A+) eval(1,B*C*(B*A-D)+) //(5)
A+B*C*(B*A-D)+.С  eval(1,A+) eval(1,B*C*(B*A-D)+) eval(1,0) //(4)
A+B*C*(B*A-D)+С.  eval(1,A+) eval(1,B*C*(B*A-D)+) eval(1,C) //(3)
A+B*C*(B*A-D)+С.  eval(1,A+) eval(1,B*C*(B*A-D)+) eval(1,C) //(1)
A+B*C*(B*A-D)+С.  eval(1,A+) eval(1,B*C*(B*A-D)+C) //(1)
A+B*C*(B*A-D)+С.  eval(1,A+B*C*(B*A-D)+C) //(1)
Результат: A+((B*(C*((B*A)-D)))+C)

[ThomasHoffman]

Спасибо за способ, но, к сожалению, время нужно не больше 6 секунд. И что-то я не замечал этой функции в паскале, буду благодарен за другие варианты.

[Abstraction]

М-м-м... подразумевалось, что eval напишете Вы - так, чтобы она исполняла 7 перечисленных правил.

Другие варианты подразумевают честное построение дерева синтаксического разбора и его оптимизацию (пустое множество является важным частным случаем, теоретически позволяющем обойтись без вычисления значительных подвыражений). То есть, скажем, та же eval, которая вместо вычисления выражений возвращает соответствующие им поддеревья; дальше на получившееся дерево (содержащее аргументы в символьном виде) можно натравить какой-нибудь алгоритм поиска общих подвыражений. По крайней мере, необходимо сохранять все найденные произведения и разности элементарных аргументов и, как уже сказано, пытаться выделять поддеревья, сворачивающиеся в пустое множество. В любом случае, разбор писать придётся, так что можете начать с него и проверить, медленный он или нет.