Для вычисления алгебраического выражения, представленного текстом, требуется написать простенький анализатор этих самых выражений. Изначально мы имеет Выражение, из которого должны, с различных вычислений получить Число.
Для этого разберёмся, что же такое число и выражение, и какие они бывают.
Понятия и определения:
1) Число. Может быть целым или дробным. Запишем это так (в /.../ записано регулярное выражение для всех неотрицательных чисел, отрицательные рассмотрим, как выражение)
Число :- строка вида /[0-9]+(.[0-9]+)?/ или число на паскале
2) У Выражения можество определений. Во-первых, число само по себе тоже является выражением, возвращающим само себя. Во-вторых число {+,-,*,итд} выражение тоже являются выражением.
Набор рекурсивных определений:
Выражение :- Число
Выражение :- -Число
Выражение :- (Выражение)
Выражение :- Число + Выражение
Выражение :- Число - Выражение
Выражение :- Число * Выражение
Выражение :- Число \ Выражение
Список можно продолжить и для других математических операций.
Используя эти определения можно написать программу, которая реализует предикаты (функции) Число() и Выражение() (функции называй, как хочешь). Особенно удобно это делать на логических языках программирования по типу Prolog, так как её код очень похож на то, что записано выше.
Для паскаля же (или того же c++) нужно писать рекурсивную программу.
Далее псевдокод:
void ВывестиОшибку(){
Print("У тебя что-то не то с выражением!! Перепиши!");
}
real Число(string numb){
if(/[0-9]+(.[0-9]+)?/.IsMatch(numb) <> true) ВывестиОшибку();
return StrToInt(numb);
}
real Число(real numb){
return numb;
}
real Выражение (string expr) {
if(/[0-9]+(.[0-9]+)?/.IsMatch(expr)){
// Вариант: число
return Число(expr);
}
else if(/-[0-9]+(.[0-9]+)?/.IsMatch(expr)){
// Вариант: -число
return -Число(expr);
}
else if(/\((.+)\)/.IsMatch(expr)){
// Вариант: (выражение)
return Выражение(/\((.+)\)/.Match(expr)[1]); //Используя группы регулярных выражений вытаскиваем содержимое из скобок
}
else if(/([0-9]+(?.[0-9]+)?)\+(.+)/.IsMatch(expr)){
// Вариант: число + выражение
real numb = /([0-9]+(?.[0-9]+)?)\+(.+)/.Match(expr)[1]; // Вытаскиваем Число
expr = /([0-9]+(?.[0-9]+)?)\+(.+)/.IsMatch(expr)[2]; // Вытаскиваем Выражение
return Число(numb) + Выражение(expr); // Складываем
} else if (...далее для остальных (-,*,/) знаков...) {}
else {
//Если ничего не подошло, значит ошибка в выражении.
ВывестиОшибку();
}
}
P.S. В выражении не может быть пробелов. Если нужна поддержка пробелов, подкорректируй регулярки.
//PascalABC.NET версия 3.4.0.1677 от 17.06.18
//Если программа не запускается, то обновите версию
const
input_file = 'Kon.in';
output_file = 'Kon.out';
type
TCell = class
public
x, y: integer;
constructor Create(coords: string);
begin
coords := coords.Trim().ToLower();
y := StrToInt(coords[2]);
x := ord(coords[1]) - ord('a') + 1;
end;
constructor Create(i, j: integer);
begin
y := j;
x := i;
end;
function IsDeskCell(): boolean;
begin
Result := (x > 0) and (y > 0) and (x <= 8) and (y <= 8);
end;
class function operator+(a, b: TCell): TCell;
begin
Result := new TCell(a.x + b.x, a.y + b.y);
end;
class function operator=(a, b: TCell): boolean;
begin
Result := (a.x = b.x) and (a.y = b.y);
end;
function ToString: string; override;
begin
Result := Format('({0}, {1})', x, y);
end;
end;
procedure PrintAnswer(path: List<TCell>);
begin
var f := OpenWrite(output_file);
Writeln(f, path.Count() - 1);
Println(path.Count() - 1);
Println(path);
f.Close();
end;
begin
var knight_steps := Arr(
new TCell(1, 2),
new TCell(2, 1),
new TCell(2, -1),
new TCell(1, -2),
new TCell(-1, -2),
new TCell(-2, -1),
new TCell(-2, 1),
new TCell(-1, 2)
);
// var f := OpenWrite(input_file);
// Writeln(f, 'a1');
// Writeln(f, 'b2');
// f.Close();
// Exit;
var f := OpenRead(input_file);
var pawn_place: TCell := new TCell(f.ReadlnString());
var knight_place: TCell := new TCell(f.ReadlnString());
f.Close();
var paths := new List<List<TCell>>();
var occupied_cells := new List<TCell>();
paths.Add(Seq(knight_place).ToList);
occupied_cells.Add(knight_place);
repeat
var new_paths := new List<List<TCell>>();
foreach var path in paths do
begin
foreach var step in knight_steps do
begin
var p := new List<TCell>(path);
var t := p.Last + step;
if t.IsDeskCell() and not occupied_cells.Contains(t) then begin
p.Add(t);
new_paths.Add(p);
occupied_cells.Add(t);
end;
if t = pawn_place then begin
PrintAnswer(p);
Exit;
end;
end;
end;
paths := new_paths;
until (false)
end.
