Question

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

Пример: abc + a + bca-acb+abc+abc+a

Ответ: 2a+3abc.

Answer 1

Опишем формальную грамматику для разбора входной строки.
<символ> ::= <буква> | <знак>
<буква> ::= '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