Задание

Разработать программу, проверяющую эквивалентность двух выражений. Выражения могут содержать операции отрицания, дизъюнкции, конъюнкции, импликации и произвольное число однобуквенных переменных. Программа может полагаться на то, что входные выражения всегда корректны и не содержит ошибок.

Краткое описание работы программы

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

Код программы

using System;

using System.Collections;

using System.Collections.Generic; using System.Linq;

namespace ConsoleApplication3

{

public class Program

{

static void Main(string[] args)

{

string f = "F"; string f2 = "F"; string expr;

expr = Console.ReadLine();

var rpn = GetRPN(expr).ToArray();

var varValues = new Dictionary<char, int>(); var headerShown = false;

foreach (var combination in GetAllCombinations("ABC".ToArray(), 0, varValues))

{

var res = Calculate(rpn, varValues); if (!headerShown)

{

foreach (var var in varValues.Keys) Console.Write(var + "\t");

Console.WriteLine(expr); headerShown = true;

}

foreach (var var in varValues.Values) Console.Write(var + "\t");

f = String.Concat(f, res); Console.WriteLine(res);

}

Console.WriteLine(f); Console.WriteLine(); string expr2;

expr2 = Console.ReadLine(); rpn = GetRPN(expr2).ToArray();

varValues = new Dictionary<char, int>(); headerShown = false;

foreach (var combination in GetAllCombinations("ABC".ToArray(), 0, varValues))

{

var res = Calculate(rpn, varValues); if (!headerShown)

{

foreach (var var in varValues.Keys) Console.Write(var + "\t");

Console.WriteLine(expr2); headerShown = true;

}

foreach (var var in varValues.Values) Console.Write(var + "\t");

f2 = String.Concat(f2, res); Console.WriteLine(res);

}

Console.WriteLine(f2); int result;

result = String.CompareOrdinal(f, f2); if(result == 0)

Console.WriteLine("Выражения эквивалентны"); else

Console.WriteLine("Выражения не эквивалентны"); Console.ReadKey();

}

private static IEnumerable<char> GetRPN(IEnumerable<char> expr)

{

var stack = new Stack<char>();

foreach (var token in expr)

{

if (token == ')')

{

}

else

stack.Pop();

if (!char.IsLetterOrDigit(token))

{

stack.Push(token); continue;

}

else

yield return token;

while (stack.Count > 0 && stack.Peek() != '(') yield return stack.Pop();

}

}

static int Calculate(IEnumerable<char> rpn, Dictionary<char, int> variableValue)

{

var stack = new Stack<bool>();

foreach (var token in rpn) switch (token)

{

case '!': stack.Push(!stack.Pop()); break;

case '|': stack.Push(stack.Pop() | stack.Pop()); break; case '&': stack.Push(stack.Pop() & stack.Pop()); break; case '>': stack.Push(!stack.Pop() | stack.Pop()); break; case '0': stack.Push(false); break;

case '1': stack.Push(true); break;

default: stack.Push(variableValue[token] == 1); break;

}

return stack.Pop() ? 1 : 0;

}

static IEnumerable GetAllCombinations(IList<char> variables, int index, Dictionary<char, int> varValues)

{

if (index >= variables.Count) yield return null; else

foreach (var val in Enumerable.Range(0, 2))

{

varValues))

}

}

}

}

varValues[variables[index]] = val;

foreach (var temp in GetAllCombinations(variables, index + 1, yield return temp;

Результат работы программы

Рисунок 1 – Выражение, являющееся эквивалентными

Рисунок 2 – Выражение, не являющееся тавтологией

Вывод

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

1