(*
Логический калькулятор (версия для Алекса).
Строит таблицу истинности для логический формулы.
Список подпрограмм:
1. _and - конъюнкция;
2. _equ - эквиваленция;
3. _imp - импликация;
4. _not - инверсия;
5. _or - дизъюнкция;
6. count - вычисляет значение выражения;
7. dectobin - переводит число из 10-ричной системы в 2-чную;
8. pow - возводит натуральное число в натуральную степень;
9. splice_oper - сдвигает элементы массива операций влево на 1, начиная с
нужной позиции;
10. splice_vars - сдвигает элементы массива переменных влево на 1, начиная
с нужной позиции;
11. step - делает обработку входной информации и вывод результата.
Автор:
Шлыков Евгений Алекснадрович, 10А.
Версия от 29.04.2014.
Правила ввода данных:
1. Данные вводятся в файл input.txt.
2. Вводится логическое выражение, соответствующее следующим правилам:
<логическая выражение> ::= <операнд> | <логическое выражение> [
<бинарная операция> <логическое выражение> ] | { <унарная операция> }
<логическое выражение> | ( <логическое выражение> )
<операнд> ::= <переменная> | <константа> | { <унарная операция> }
<операнд> | ( <операнд> )
<переменная> ::= a | b | c | d | e | f | g | h | i | j | k | l | m |
n | o | p | q | r | s | t | u | v | w | x | y | z
<константа> ::= 0 | 1
<унарная операция> ::= -
<бинарная операция> ::= + | - | > | =
3. Между знаками выражения может стоять произвольное количество пробелов и
других символов, не используемых в выражении. (Внимание: они будут отражены
при выводе таблицы истинности!)
4. Результат - таблица истинности для введенной формулы. Переменные использу-
ются в порядке появления при чтении формулы слева направо.
5. Результат находится в файле output.txt.
*)
program logical_calculator_for_alex(input, output);
type
literals = set of char; // Множество для
// символов выражения.
operation = record // Структура
// логической операции.
name :string;
sign :char; // Знак операции.
order, index :byte; // пПиоритет и индекс.
end;
oper_in_list = record // Структура для
// храниения операций
// в массиве.
first, second :byte; // Индексы первого и
// второго операндов
// операции.
oper :operation; // сама операция.
end;
char_var_list = array [1..128] of char; // Массив переменных.
bool_var_list = array [1..128] of boolean; // Массив значений
// переменных.
oper_list = array [1..9] of operation; // Массив операций.
formula_oper_list = array [1..128] of oper_in_list; // Массив операций из
// формулы.
var_values = array ['a'..'z'] of boolean; // Значения переменных
// в данный момент по
// имени.
var
opers : oper_list; // Массив возможных операций.
i : byte;
var_symbols : literals; // Множество символов для переменных.
oper_symbols : literals; // Множество символов для операций.
const_symbols : literals; // Множество символов для констант.
f : string; // Исходное логическое выражение.
function _not( // Инверсия логического значения.
x : boolean;
y : boolean // Не используется.
): boolean;
begin
_not := not x;
end;
function _and( // Конъюнкция двух логических значений.
x : boolean;
y : boolean
): boolean;
begin
_and := x and y;
end;
function _or( // Дизъюнкция двух логических значений.
x : boolean;
y : boolean
): boolean;
begin
_or := x or y;
end;
function _imp( // Импликация двух логических значений.
x : boolean;
y : boolean
): boolean;
begin
_imp := not x or y;
end;
function _equ( // Эквиваленция двух логических хначений.
x : boolean;
y : boolean
): boolean;
begin
_equ := x = y;
end;
function dectobin( // Перевод числа из десятичной системы счисления в
// двоичную.
n : longint
): string;
var
p, q : string;
begin
p := '';
while n > 0 do
begin
str(n mod 2, q);
p := q + p;
n := n div 2;
end;
dectobin := p;
end;
function pow( // Возведения числа в степень. Основание и показатель
// натуральные.
a : integer;
b : integer
): longint;
var
i : integer;
c : longint;
begin
c := 1;
for i := 1 to b do
c := c * a;
pow := c;
end;
procedure splice_vars( // Сдвигает элементы массива переменных на
// позицию влево, начиная с позиции m
var a : bool_var_list; // Массив значений переменных.
var m : byte; // Начальная позиция.
n : byte // Длина всего массива.
);
var
i : byte;
begin
for i := m to n - 1 do
a[i] := a[i + 1];
dec(n);
end;
procedure splice_oper( // Сдвигает элементы массива переменных на
// позицию влево, начиная с позиции m
var a : formula_oper_list; // Массив операций формулы.
var m : byte; // Начальная позиция.
var n : byte // Длина всего массива.
);
var
i : byte;
begin
for i := m to n - 1 do
a[i] := a[i + 1];
dec(n);
end;
function count( // Вычисляет значение выражения.
f : string; // Логическое выражение.
value : var_values // Значения переменных по именам.
): boolean;
var
p : bool_var_list; // Значения переменных по индексам.
q : formula_oper_list; // Массив операций формулы.
i, j, k, l : byte;
n,m : byte; // Количество переменных и операций.
c : char; // Текущий символ выражения.
x : operation; // Текущая операция.
g : boolean; // Промежуточное значение.
begin
n := 0; // Количество переменных.
m := 0; // Колиество операций.
i := 0; // Позиция текущего символа.
while i < length(f) do
begin
inc(i);
c := f[i];
if c in var_symbols
then
begin
inc(n);
p[n] := value[c];
end
else
if c = '(' // ...то ищем соответстующую этой закрывающую и
then // рекурсивно получаем значение в скобках.
begin
l := i;
k := 1;
j := l + 1;
while (k <> 0) and (j <= length(f)) do
begin
c := f[j];
if c = '('
then
inc(k)
else
if c = ')'
then
dec(k);
inc(j);
end;
i := j - 1;
inc(n);
p[n] := count(copy(f, l + 1, i - l - 1), value);
end
else
if c in const_symbols // ...то сразу подставляем.
then
begin
inc(n);
if c = '1'
then
p[n] := true
else
p[n] := false;
end
else
if c in oper_symbols // ...то записываем операцию
// и позиции операндов.
then
begin
inc(m);
q[m].first := n;
q[m].second := n + 1;
case c of
'*' : q[m].oper := opers[2];
'+' : q[m].oper := opers[3];
'>' : q[m].oper := opers[4];
'=' : q[m].oper := opers[5];
else begin
inc(q[m].first);
q[m].oper := opers[1];
end;
end;
end;
end;
while m > 0 do // Пока мы не вычислили значения всех операций...
for i := 1 to 4 do // Цикл по приоритетам операци.
begin
j := 1;
while j <= m do // Ищем все операции с таким приоритетом.
begin
if q[j].oper.order <> i
then
begin
inc(j);
continue;
end;
x := q[j].oper;
case x.index of // Вычисляем значение этой операции для
// для найденных ранее операндов.
1 : g := _not(p[q[j].first], p[q[j].second]);
2 : g := _and(p[q[j].first], p[q[j].second]);
3 : g := _or(p[q[j].first], p[q[j].second]);
4 : g := _imp(p[q[j].first], p[q[j].second]);
5 : g := _equ(p[q[j].first], p[q[j].second]);
end;
p[q[j].first] := g;
p[q[j].second] := g;
if x.order <> 1 // Если операция не отрицания, то
then // То сдвигаем все операции в массиве
begin // и переписываем индексы операндов.
splice_vars(p,q[j].first, n);
for k := 1 to m do
begin
if q[k].first > q[j].first
then
dec(q[k].first);
if q[k].second > q[j].second
then
dec(q[k].second)
end;
end;
splice_oper(q, j, m);
end;
end;
count := p[1];
end;
procedure step( // Основное действие программы.
f:string // Логическое выражение.
);
var
vars : char_var_list; // Массив переменных.
vars_set : literals; // Множество переменных.
code : string; // Набор значений в строковом виде.
g : boolean; // Значение выражения при данном наборе.
i,k : byte;
n : byte; // Количество переменных.
j : longint; // Номер набора значений переменных.
c : char; // Текущий символ выражения.
value : var_values; // Массив значений переменных по имени.
begin
// Обработка выражения.
n := 0;
vars_set := [];
for i := 1 to length(f) do
begin
c := f[i];
if (c in var_symbols) and not (c in vars_set)
then
begin
inc(n);
vars_set := vars_set + [c];
vars[n] := c;
end;
end;
// Выписываем переменные и выражение.
for i := 1 to n do
write(vars[i], ' ');
writeln(f);
for j := 0 to pow(2, n) - 1 do
begin
// Создаем набор значений переменных.
code := dectobin(j);
while length(code) < n do
code := '0' + code;
for k := 1 to n do
if code[k] = '0'
then
value[vars[k]] := false
else
value[vars[k]] := true;
// Получаем начение выражения при наборе и строим строку таблицы.
g := count(f, value);
for k := 1 to n do
if value[vars[k]]
then
write('1 ')
else
write('0 ');
if g
then
writeln('1')
else
writeln('0');
end;
end;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
// Создание операций и знаков выражений.
opers[1].sign := '-';
opers[1].order := 1;
opers[2].sign := '*';
opers[2].order := 2;
opers[3].sign := '+';
opers[3].order := 3;
opers[4].sign := '>';
opers[4].order := 4;
opers[5].sign := '=';
opers[5].order := 4;
var_symbols := ['a' .. 'z'];
oper_symbols := [];
for i := 1 to 5 do
begin
oper_symbols := oper_symbols + [opers[i].sign];
opers[i].index := i;
end;
const_symbols := ['0', '1'];
// Основная часть программы.
readln(f);
step(f);
writeln;
end.