Создание программы для построения таблицы истинности

Лабораторная  работа №

Индивидуальное  задание №1 Программа для построения таблицы истинности

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ, МОЛОДЁЖИ И СПОРТА УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

ИМ. В. ДАЛЯ

ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК И ТЕХНОЛОГИЙ

Кафедра "Системная  инженерия"

 

 

 

«Дискретна математика»

 

Индивидуальное задание №1 
Тема: «Создание программы для построения таблицы истинности»

 

 

 

Выполнил: студент: Валуйский Р.В.

 

группа: КТ-711

Оценка: 

 

 

 

 

 

Проверил: асс. Быбко

 

 

 

Индивидуальное задание №1

ШИФР: z21203 
 Вариант 3. Валуйский Р.В. 

 

Луганск 2013 г.

Цель

Создать программу, которая бы помогла  быстро проверить правильность созданных вручную таблиц истинности.

Задание

Написать программу, которая будет  строить таблицы истинности для  исходных и упрощенных форм, и проверять  их тождественность. Таблицы истинности выводить на экран.

Исходный код

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace calcForLogicOperation

{

    public class  Operator

    {

        // Коллекция стандартных операторов

        public static List<string> StandartOperators =

            new List<string>(new string[] { "(", ")", "+", "*", "!", "|", "~", "@", "v", "<", "<<", ">", ">>" });

 

        public static List<string> OperatorsForImplication = new List<string>() { "<", ">"};

    }

 

class  OutputForAssignValue2

    {

        public static List<string> ChangeVariableToLogicNumber(List<string> input, out List<string> rowsCountOrLogicalNumbers, out List<string> columnsCountOrVariables)

        {

            List<string> output = new List<string>();

            List<string> outRowCountOrLogicalNumbers = new List<string>();

            // Отделяем переменные от входной строки

            // И возвращаем их коллекцию

            List<string> variables = columnsCountOrVariables = SeparateVariables(input);

            // Подсчитываем количество строчек

            int numberOfLines = (int)Math.Pow((double)2, (double)variables.Count);

 

            // Проходим по каждой строчке таблицы истинности

            for (int i = 0; i < numberOfLines; i++)

            {

                // Конвертируем число в двоичное

                string numberFromIntToBool = Convert.ToString(i, 2);

 

                // В случаи, если при переводе числа в двоичное

                // не хватает нулей, то добавляем их

                string addZero = String.Empty;

                // если количество переменных превышает число строк в двоичном числе,

                // то добавляем не достающие нули

                for (int h = 0; h < variables.Count - numberFromIntToBool.Length; h++)

                    addZero += "0";

                // Добавляем не достающие нули к логическим числам

                string logicalNumber = addZero + numberFromIntToBool;

                // заносим каждую строчку логического числа в выходную переменную

                outRowCountOrLogicalNumbers.Add(logicalNumber); 

 

                // подставляем в выражение значения из таблицы истинности

                // для данного выражения

                Queue<string> logicalNumbers = new Queue<string>(ConvertStringToList(logicalNumber));

                string convertInput = String.Empty;

                for (int j = 0; j < variables.Count; j++)

                {

                    if (!String.IsNullOrEmpty(convertInput))

                        // Находим переменные в выражении и подставляем вместо их логические значения

                        convertInput = convertInput.Replace(variables[j], logicalNumbers.Dequeue());

                    else

                        convertInput = ConvertListToString(input).Replace(variables[j], logicalNumbers.Dequeue());

                }

                output.Add(convertInput);

            }

            rowsCountOrLogicalNumbers = outRowCountOrLogicalNumbers;

            return output;           

        }

 

        // Возвращает из коллекции подстрок

        // коллекции подстрок только с переменными

        private static List<string> SeparateVariables(List<string> input)

        {

            List<string> output = new List<string>();

            int a;

            for (int i = 0; i < input.Count; i++)

                if (!Operator.StandartOperators.Contains(input[i]) &&

                    !output.Contains(input[i]) && !Int32.TryParse(input[i], out a))

                    output.Add(input[i]);

            return output;

        }

 

        // Преобразует коллекцию в строку

        private static string ConvertListToString(List<string> input)

        {

            string output = String.Empty;

            foreach (string c in input)

                output += c;

            return output;

       }

 

        // Конвертирует строку в коллекцию

        private static List<string> ConvertStringToList(string input)

        {

            List<string> outputString = new List<string>();

            List<char> output = input.ToList<char>();

            foreach (char c in output)

                outputString.Add(c.ToString());

            return outputString;

        }

    }

}

 

 

 

 

 

 

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using calcForLogicOperation;

 

namespace OPN2

{

    class PostfixNotationExpression

    {

        private List<string> operators;

 

        public PostfixNotationExpression()

        {

            operators = new List<string>(Operator.StandartOperators);

        }

 

        /// <summary>

        /// Разделяет входную строку на подстроки

        /// </summary>

        /// <param name="input">Входная строка</param>

        /// <returns></returns>

        public IEnumerable<string> Separate(string input)

        {

            int pos = 0; // позиция символа

            while (pos < input.Length)

            {

                // создаем переменную, в которой будут хранится перемещенные символы

                // добавляем текущий символ к строке

                string s = string.Empty + input[pos]; // конвертируем символ в строку

 

                // если элемент не входит в состав стандартных операторов, то

                if (!Operator.StandartOperators.Contains(input[pos].ToString()))

                {

                    // если элемент число

                    if (Char.IsDigit(input[pos]))

                    {

                        // Выполнять цикл пока не достигним конца строки и пока

                        // следующий символ число или запятая или точка

                        for (int i = pos + 1; i < input.Length &&

                            (Char.IsDigit(input[i])); i++)

                            s += input[i]; // заносим текущий символ

                    }

                    // иначе если текущий символ знак

                    else if (Char.IsLetter(input[pos]))

                        // Выполнять цикл пока не будет достигнут конец строки и пока

                        // следующий символ знак или число             

                        for (int i = pos + 1; i < input.Length &&

                            !Operator.StandartOperators.Contains(input[i].ToString()) &&

                            (Char.IsLetter(input[i]) || Char.IsDigit(input[i])); i++)

                            s += input[i]; // добавляем текущий символ в строку                   

                }

                // если текущий элемент оператор

                if (Operator.StandartOperators.Contains(input[pos].ToString()))

                    for (int i = pos + 1; i < input.Length && Operator.OperatorsForImplication.Contains(input[i].ToString())

                        && Operator.OperatorsForImplication.Contains(input[i-1].ToString()); i++)

                        s += input[i];

 

                if (s != " ")

                    yield return s; // возвращаем поочередно каждую строку s;

                pos += s.Length; // длинна элемента может быть больше одного, то есть нам нужно сразу перейти к следующему

            }

        }

 

        /// <summary>

        /// Возвращает приоритет знака операции

        /// </summary>

        /// <param name="s">знак операции</param>

        /// <returns></returns>

        private byte GetPriority(string s)

        {

            switch (s)

            {

                case "(":

                    return 0;

                case ")":

                    return 1;

                case "+":

                case ">":

                case ">>":

                case "<":

                case "<<":

                case "|":

                case "~":

                case "@":

                case "v":

                    return 2;

                case "*":               

                    return 3;

                case "!":               

                    return 4;

                default:

                    return 5;

            }

        }

 

        /// <summary>

        /// Преобразовывает входное выражение в обратную польскую нотацию

        /// </summary>

        /// <param name="input">входное выражение</param>

        /// <returns></returns>

        public List<string> ConverToPostfixNotation(string input)

        {

            List<string> outputSeparated = new List<string>(); // выходная разделенная строка

            Stack<string> stack = new Stack<string>(); // стек, в него будут заносится знаки операций, скобки

 

            // проходим по всем элементам входной строки

            // занося их в стек, а затем некоторые в выходную строку

            foreach (string c in Separate(input))

            {

                // Если текущий символ является оператором (+,* и т.п.)

                if (operators.Contains(c))

                {

                    // Если в стеке есть элементы и

                    // если текущий символ не равен открывающийся скобке

                    if (stack.Count > 0 && !c.Equals("("))

                    {

                        // Если текущий символ равен закрывающийся скобке

                        if (c.Equals(")"))

                        {

                            // то извлекаем из стека верхний элемент

                            string s = stack.Pop();

                            // пока извлеченный символ не равен открытой скобке

                            while (s != "(")

                            {

                                outputSeparated.Add(s); // добавляем знак операции в выходную строку

                                s = stack.Pop(); // извлекаем следующий элемент из стека

                            }

                        }

                        // если приоритет текущего оператора выше или равен

                        // содержащегося на вершине стека

                        else if (GetPriority(c) >= GetPriority(stack.Peek()))

                            stack.Push(c); // то заносим этот символ в стек

                        else // иначе извлекаем вверхний символ из стека и добавляем в выходную строку

                        // пока стек содержит операторы или пока приоритет

                        // текущего оператора не будет больше или равным вершине стека

                        {

                            while (stack.Count > 0 && GetPriority(c) < GetPriority(stack.Peek()))

                                outputSeparated.Add(stack.Pop());

                            stack.Push(c); // после чего заносим оператор в стек

                        }

                    }

                    else // иначе, то есть если стек не содержит ни одного элемента или

                        // текущий оператор это открывающаяся скобка "("

                        stack.Push(c); // заносим его в стек

                }

                else // иначе, если текущий символ число

                    outputSeparated.Add(c); // заносим его сразу в выходную строку

            }

            // если в стеке остались элементы

            if (stack.Count > 0)

                foreach (string c in stack)

                    outputSeparated.Add(c);

 

            return outputSeparated; // возвращаем выходную строку в виде массива строк

        }

 

        /// <summary>

        /// Вычисляем выражение преобразованное в ОПЗ

        /// </summary>

        /// <param name="input">входная строка</param>

        /// <returns></returns>

        public bool Result(string input)

        {

            Stack<string> stack = new Stack<string>();

            // создаем очередь, которой передаем наше преобразованное выражение в ОПЗ

            Queue<string> queue = new Queue<string>(ConverToPostfixNotation(input));

 

            string str = queue.Dequeue(); // извлекаем первый элемент из очереди

            // пока в очереди содержатся элементы

            while (queue.Count >= 0)

            {

                // если текущий элемент не оператор

                if (!operators.Contains(str))

                {

                    // то заносим его в стек

                    stack.Push(str);

                    str = queue.Dequeue(); // переходим к следующему элементу

                }

                else // иначе, если текущий элемент оператор

                {

                    bool summ = false; // создаем переменную для хранения текущего вычисления

                    try // пробуем выполнить операции

                    {

                        switch (str) // определяем тип оператора

                        {

                            case "+":

                                {

                                    bool a = ConvertToBool(stack.Pop());

                                    bool b = ConvertToBool(stack.Pop());

                                    summ = a | b;

                                    break;

                                }