Опишем формальную грамматику для разбора входной строки.
<символ> ::= <буква> | <знак>
<буква> ::= 'a' | 'b' | 'c' | ... | 'y' | 'z'
<знак> ::= '+' | '-'
<терм> ::= <буква> [ <терм> ]
<операнд> ::= [ <знак> ] <терм>
<строка> ::= <операнд> [ <операнд> ]
Ниже приведена программа на языке Pascal.ABC, реализующая разбор входной строки и её упрощение по правилам приведения подобных членов.
const
n = 30; {максимальное количество операндов, я так захотел!}
pm = ['+', '-']; {символы <знак>}
letter = ['a'..'z'];{символы <буква>}
type
tOper = record
sgn: integer;
vars: string
end;
tM = array[1..n] of tOper;
taSort = array[1..n] of string;{для сортировки}
var
s: string;
l, p: integer;
symb: set of char;
procedure GetSymbol(var c: string);
{
Сканирует строку s с позиции p и возвращает элемент <символ>
Продвигает курсор p к первому необработанному символу строки s
}
var
found: boolean;
begin
found := false;
c := '';
while (p <= l) and (not found) do
begin
if s[p] in symb then begin
found := true;
c := s[p]
end;
p := p + 1
end
end;
procedure Sort(var a: taSort; kol: integer);
{Сортировка вставкой}
var
i, j: integer;
x: string;
flag: boolean;
begin
for i := 2 to kol do
begin
x := a[i];
j := i - 1;
flag := False;
while (j > 0) and (not flag) do
if x < a[j] then
begin
a[j + 1] := a[j];
j := j - 1
end
else flag := True;
a[j + 1] := x
end
end;
function GetSign(c: char): integer;
begin
case c of
'+': Result := 1;
'-': Result := -1;
else Result := 0
end
end;
procedure GetOper(var oper: tOper);
{
Строит элемент <операнд> максимально возможной длины и упорядочивает
составляющие его символы в лексикографическом порядке.
Если операнд построить невозможно, в oper.vars помещается пустая строка.
Процедура обращается к процедурам GetSymbol и Sort.
}
var
i, n: integer;
c, c1: string;
ExitFlag: boolean;
a: taSort;
begin
c := '';
ExitFlag := false;
GetSymbol(c1); {попытаемся получить знак}
if c1[1] in pm then oper.sgn := GetSign(c1[1])
else begin
oper.sgn := 1;
c := c1
end;
repeat
GetSymbol(c1);
if c1 = '' then ExitFlag := true
else if c1[1] in pm then begin
p := p - 1;
ExitFlag := true
end
else
c := c + c1
until ExitFlag;
if c <> '' then
begin
n := Length(c);
for i := 1 to n do a[i] := c[i];
Sort(a, n);
c := '';
for i := 1 to n do c := c + a[i];
oper.vars := c
end
else oper.vars := ''
end;
procedure Add2M(var a: tM; c: tOper; var pn: integer);
{
Ищет среди элементов массива a.vars элемент, совпадающий с с.vars.
При нахождении алгебраически добавляет c.sgn к a[i].sgn, в противном случае
добавляет в массив новый элемент a[i], увеличивая pn на 1.
При вызове pn - количество элементов в массиве.
}
var
i: integer;
c1: string;
found: boolean;
begin
c1 := c.vars;
i := 1;
while (i <= pn) and (not found) do
begin
found := (c1 = a[i].vars);
if found then a[i].sgn := a[i].sgn + c.sgn
else i := i + 1
end;
if not found then begin
a[i].sgn := c.sgn;
a[i].vars := c1;
pn := pn + 1
end
end;
function Convert(k: integer): string;
begin
case k of
-1: Result := '-';
0: Result := '';
1: Result := '+';
else begin
Str( k, Result);
if k > 0 then Result := '+' + Result
end
end
end;
var
c, cz: string;
n1, i: integer;
opr: tOper;
a: tM;
begin
symb := pm + letter;
p := 1;
n1 := 0;
writeln('Введите исходное выражение');
readln(s);
s := LowerCase(s); {перевод символов в нижний регистр}
l := Length(s);
repeat
GetOper(opr);
Add2M(a, opr, n1)
until p > l;
if n1 > 0 then
begin
cz := Convert(a[1].sgn);
if cz = '+' then cz := '';
if cz = '' then c := ''
else c := cz + a[1].vars;
for i := 2 to n1 do
begin
cz := Convert(a[i].sgn);
if cz <> '' then c := c + cz + a[i].vars
end
end
else c := '';
if c='' then c:='0';
if c[1]='+' then c:=copy(c,2,Length(c)-1);
writeln('Результат: ', c)
end.
Тестовое решение:
Введите исходное выражение
abc + a+bca -acb+abc+abc +a
Результат: 3abc+2a
Введите исходное выражение
ab-bca+bc+cba+abc-ba+cba+da+adb+bad-db
Результат: 2abc+bc+ad+2abd-bd
<символ> ::= <буква> | <знак>
<буква> ::= 'a' | 'b' | 'c' | ... | 'y' | 'z'
<знак> ::= '+' | '-'
<терм> ::= <буква> [ <терм> ]
<операнд> ::= [ <знак> ] <терм>
<строка> ::= <операнд> [ <операнд> ]
Ниже приведена программа на языке Pascal.ABC, реализующая разбор входной строки и её упрощение по правилам приведения подобных членов.
const
n = 30; {максимальное количество операндов, я так захотел!}
pm = ['+', '-']; {символы <знак>}
letter = ['a'..'z'];{символы <буква>}
type
tOper = record
sgn: integer;
vars: string
end;
tM = array[1..n] of tOper;
taSort = array[1..n] of string;{для сортировки}
var
s: string;
l, p: integer;
symb: set of char;
procedure GetSymbol(var c: string);
{
Сканирует строку s с позиции p и возвращает элемент <символ>
Продвигает курсор p к первому необработанному символу строки s
}
var
found: boolean;
begin
found := false;
c := '';
while (p <= l) and (not found) do
begin
if s[p] in symb then begin
found := true;
c := s[p]
end;
p := p + 1
end
end;
procedure Sort(var a: taSort; kol: integer);
{Сортировка вставкой}
var
i, j: integer;
x: string;
flag: boolean;
begin
for i := 2 to kol do
begin
x := a[i];
j := i - 1;
flag := False;
while (j > 0) and (not flag) do
if x < a[j] then
begin
a[j + 1] := a[j];
j := j - 1
end
else flag := True;
a[j + 1] := x
end
end;
function GetSign(c: char): integer;
begin
case c of
'+': Result := 1;
'-': Result := -1;
else Result := 0
end
end;
procedure GetOper(var oper: tOper);
{
Строит элемент <операнд> максимально возможной длины и упорядочивает
составляющие его символы в лексикографическом порядке.
Если операнд построить невозможно, в oper.vars помещается пустая строка.
Процедура обращается к процедурам GetSymbol и Sort.
}
var
i, n: integer;
c, c1: string;
ExitFlag: boolean;
a: taSort;
begin
c := '';
ExitFlag := false;
GetSymbol(c1); {попытаемся получить знак}
if c1[1] in pm then oper.sgn := GetSign(c1[1])
else begin
oper.sgn := 1;
c := c1
end;
repeat
GetSymbol(c1);
if c1 = '' then ExitFlag := true
else if c1[1] in pm then begin
p := p - 1;
ExitFlag := true
end
else
c := c + c1
until ExitFlag;
if c <> '' then
begin
n := Length(c);
for i := 1 to n do a[i] := c[i];
Sort(a, n);
c := '';
for i := 1 to n do c := c + a[i];
oper.vars := c
end
else oper.vars := ''
end;
procedure Add2M(var a: tM; c: tOper; var pn: integer);
{
Ищет среди элементов массива a.vars элемент, совпадающий с с.vars.
При нахождении алгебраически добавляет c.sgn к a[i].sgn, в противном случае
добавляет в массив новый элемент a[i], увеличивая pn на 1.
При вызове pn - количество элементов в массиве.
}
var
i: integer;
c1: string;
found: boolean;
begin
c1 := c.vars;
i := 1;
while (i <= pn) and (not found) do
begin
found := (c1 = a[i].vars);
if found then a[i].sgn := a[i].sgn + c.sgn
else i := i + 1
end;
if not found then begin
a[i].sgn := c.sgn;
a[i].vars := c1;
pn := pn + 1
end
end;
function Convert(k: integer): string;
begin
case k of
-1: Result := '-';
0: Result := '';
1: Result := '+';
else begin
Str( k, Result);
if k > 0 then Result := '+' + Result
end
end
end;
var
c, cz: string;
n1, i: integer;
opr: tOper;
a: tM;
begin
symb := pm + letter;
p := 1;
n1 := 0;
writeln('Введите исходное выражение');
readln(s);
s := LowerCase(s); {перевод символов в нижний регистр}
l := Length(s);
repeat
GetOper(opr);
Add2M(a, opr, n1)
until p > l;
if n1 > 0 then
begin
cz := Convert(a[1].sgn);
if cz = '+' then cz := '';
if cz = '' then c := ''
else c := cz + a[1].vars;
for i := 2 to n1 do
begin
cz := Convert(a[i].sgn);
if cz <> '' then c := c + cz + a[i].vars
end
end
else c := '';
if c='' then c:='0';
if c[1]='+' then c:=copy(c,2,Length(c)-1);
writeln('Результат: ', c)
end.
Тестовое решение:
Введите исходное выражение
abc + a+bca -acb+abc+abc +a
Результат: 3abc+2a
Введите исходное выражение
ab-bca+bc+cba+abc-ba+cba+da+adb+bad-db
Результат: 2abc+bc+ad+2abd-bd
0
0