RegExp на практике (министатья для начинающих) - C#

Узнай цену своей работы

Формулировка задачи:

Здравствуйте! Преамбула: Было дело, задали мне в институте написать программу, которая выводит таблицу истинности для булевого выражения. Я тогда написал ее очень плохо, решала она где-то 70% выражений, зачет я получил, но из спортивного интереса я потом ее переписал на совесть. Но когда стал изучать регэкспы то понял что можно написать ее чтоб кода было вполовину меньше. Здесь я не буду расказывать всю теорию и подробности RegExp, лучше для этого пробежать глазами эти статьи http://msgeeks.ru/?artid=47 http://2lx.ru/2009/02/regulyarnye-vyrazheniya-v-c/ Они мне очень помогли при написании этой проги. Итак начнем. Метод класса принимает булевое выражение вида "!(a+b)*(!c^(!a=b))" где * коньюнкиция + дизъюнкция - импликация = эквивалентность ^ XOR (исключительное или) ! отрицание a, b, c, ... переменные и возвращает таблицу истинности в виде string, учитывая приоритет операций и (). Также проверяет строку на соответствие правилам. Приступаем: метод, который строит таблицу: 
public static string BuildTrueFalseTable(string polinome)
{
    //считаем количество переменных выражения, объявляем свои переменные
    int varNnumber = CountVarNumber(polinome);
    string res = "";
    int[] values = new int[varNnumber];
    int rowNumber = (int)Math.Pow(2, (double)varNnumber);
    int[] roots = new int[rowNumber];
    //endcomment
    res = MakeHeaderForOutput(polinome, res); // добавлям в результат строку типа "a b c result"
    //генерируем значения для переменных в таблице, подставляем их в строку, решаем строку
    for (int i = 0; i < rowNumber; i++)
    {
        int ii = i;
        for (int j = 0; j < varNnumber; j++)
        {
            values[j] = ii % 2; //значения переменных у нас 1 или 0
            ii = ii >> 1; //сдвиг нужен для вычисления нового значения
            res += values[j].ToString() + " ";
        }
        string expression = ReplaceVariablesWithValues(values, polinome); //заменяем буквы на цифры
        roots[i] = SolveExpression(expression); //решаем выражение
        res += roots[i].ToString() + "\r\n";
    }
    //endcomment
    return res;
}
метод, который решает выражение: 
private static int SolveExpression(string expr)
{
    string res = expr;            
    while (res.Length != 1) // когда строка равна "0" или "1" мы вычислили выражение
    {
        //сначала считаются отрицания если они есть то пускаем цикл заново
        bool foundMatch = CalulateDenials(ref res); 
        if (foundMatch)
            continue;
        //потом нужно посчитать подвыражения в скобках - у них 
        //наивысший приоритет после отрицаня
        foundMatch = replaceWithBrackets(ref res);
        if (foundMatch)
            continue;
        //последними считаем подвыражения без скобок с учетом приоритета операций
        res = replaceWithoutBrackets(res);
    }
    return int.Parse(res);
}
метод, который вычисляет отрицание: 
private static bool CalulateDenials(ref string expr)
{
    //это сам РегЭксп находим выражения типа "!0"
    string pattern1 = @"\!(\d)"; 
    Regex reg = new Regex(pattern1);
    if (!reg.IsMatch(expr))
        return false;
    while (true)
    {
        Match match = reg.Match(expr);
        if (match.Success)
        {
            // здесь я использовал свой extension method для string он выглядит так:
            /*
            public static string ReplaceByIndex(this string str, string replacedWith, int index, int lenght)
            {
                string res = str.Remove(index, lenght);
                res = res.Insert(index, replacedWith);
                return res;            
            }
            */   
            expr = expr.ReplaceByIndex(denial(match.Groups[1].Value), match.Groups[0].Index, 2);
            match = match.NextMatch();
        }
        else
            break;
    }
    return true;
    //здесь используется метод denial он выглядит очень просто:
    /*
    private static string denial(string arg)
    {
        return (arg == "0") ? "1" : "0";                
    }
    */
}
метод, который вычисляет подвыражения в скобках: 
private static bool replaceWithBrackets(ref string res)
{
    bool flag = false;
    string pattern2 = @"\((\d)(.)(\d)\)"; // реэксп видит строки типа "(1*0)"
    Regex reg = new Regex(pattern2);
    Match match = reg.Match(res);
    if (match.Success)
    {
        res = replaceMatch(match, res);
        flag = true;
    }
    return flag;            
}
метод replaceMatch который здесь используется выглядит так: 
private static string replaceMatch(Match match, string res)
{
    //мы просто меняем подвыражение на его результат 
    //(считается в binaryOpps он ниже будет описан)
    //в этом нам помогает разбиение совпадений регэкспа по группам
    //(match.Groups[n])
    res = res.ReplaceByIndex( 
    binaryOpps(
        match.Groups[1].Value,
        match.Groups[3].Value,
        match.Groups[2].Value
        ),
    match.Groups[0].Index, match.Groups[0].Value.Length);
    return res;
}
метод binaryOpps это простой свитч и ничего лишнего 
private static string binaryOpps(string a, string b, string sign)
{
    string res = "";
    switch (sign)
    {
        case "+":
        res = (a== "0" && b=="0")? "0": "1";
        return res;
        case "-":
        res = (a== "0" && b=="1")? "0": "1";
        return res;
        case "*":
        res = (a== "1" && b=="1")? "1": "0";
        return res;
        case "^":
        res = (a!=b)? "1": "0";
        return res;
        case "=":
        res = (a==b)? "1": "0";
        return res;             
    }
    return "";
}
вернемся к методам для вычислений, replaceWithBrackets, вычисляет подвыражения без скобок с учетом приоритета 
private static string replaceWithoutBrackets(string expr)
{
    string res = expr;
    string[] patterns = new string[] { //отдельный шаблон для 
                    @"(\d)(\*)(\d)",   //каждой операции 
                    @"(\d)(\+)(\d)",   //в порядке приоритета
                    @"(\d)(\-)(\d)", 
                    @"(\d)(\^)(\d)", 
                    @"(\d)(\=)(\d)" 
        };
    foreach (string pattern in patterns)
    {
        Regex reg = new Regex(pattern);
        Match match = reg.Match(res);
        //очень просто, если нашли заменяем подвыражение
        //на его решение и выходим
        //(когда строка изменилась может поменяться порядок вычисления)
        if (match.Success)
            return replaceMatch(match, res);               
    }
    return res;
}
Это основа класса, полный выглядит вот так: 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
 
namespace boolean_expressions
{
    class Comparer : IEqualityComparer<Group>
    {
        public bool Equals(Group x, Group y)
        {
            return x.Value == y.Value;
        }
        public int GetHashCode(Group obj)
        {
            return obj.Value.GetHashCode();
        }
    }
    
    class TFtableBuilder
    {
        public static bool PolinomeIsValid(string polinome)
        {
            string pattern1 = @"([^\+\-\*\=\^\!\w10\)\(]|\+{2,}|\-{2,}"+
                            @"|\*{2,}|\={2,}|\^{2,}|\!{2,}|\w{2,}|1{2,}|0{2,}|\(\)|\(\w\))";
            Regex reg = new Regex(pattern1);
            if (reg.IsMatch(polinome))
                return false;
            
            if (!BracketsMatch(polinome))            
                return false;
            return true;
        }
 
        private static bool BracketsMatch(string polinome)
        {
            int open = 0;
            int close = 0;
            string pattern1 = @"\(";
            string pattern2 = @"\)";                           
            Regex reg = new Regex(pattern1);
            Match match = reg.Match(polinome);
            while (match.Success)
            {
                open++;
                match = match.NextMatch();
            }
            reg = new Regex(pattern2);
            match = reg.Match(polinome);
            while (match.Success)
            {
                close++;
                match = match.NextMatch();
            }           
            if (open != close)
                return false;
            return true;
        }
        public static string BuildTrueFalseTable(string polinome)
        {
            //act variable declaration
            int varNnumber = CountVarNumber(polinome);
            string res = "";
            int[] values = new int[varNnumber];
            int rowNumber = (int)Math.Pow(2, (double)varNnumber);
            int[] roots = new int[rowNumber];
            //endact
            res = MakeHeaderForOutput(polinome, res);
            //act generate values and solve rows
            for (int i = 0; i < rowNumber; i++)
            {
                int ii = i;
                for (int j = 0; j < varNnumber; j++)
                {
                    values[j] = ii % 2;
                    ii = ii >> 1;
                    res += values[j].ToString() + " ";
                }
                string expression = ReplaceVariablesWithValues(values, polinome);
                roots[i] = SolveExpression(expression);
                res += roots[i].ToString() + "\r\n";
            }
            //endact
            return res;
        }
 
        private static string MakeHeaderForOutput(string polinome, string res)
        {            
            List<Group> lst = new List<Group>();
            FillMatchesList(polinome, lst);
            string[] variables = (from g in lst.Distinct(new Comparer()) select g.Value).ToArray();
            foreach (string variable in variables)
            {
                res += variable + " ";
            }
            res += "result\r\n";
            return res;
        }
 
        private static int CountVarNumber(string expr)
        {
            string pattern = @"(\w)";
            Regex reg = new Regex(pattern);
            Match match = reg.Match(expr);
            List<string> lst = new List<string>();
            while (match.Success)
            {
                lst.Add(match.Groups[0].Value);
                match = match.NextMatch();
            }
            return lst.Distinct().Count();
        }

        private static int SolveExpression(string expr)
        {
            string res = expr;            
            while (res.Length != 1)
            {
                bool flag = CalulateDenials(ref res);
                if (flag)
                    continue;
                flag = replaceWithBrackets(ref res);
                if (flag)
                    continue;
                res = replaceWithoutBrackets(res);
            }
            return int.Parse(res);
        }
 
        private static string replaceWithoutBrackets(string expr)
        {
            string res = expr;
            string[] patterns = new string[] { 
                            @"(\d)(\*)(\d)", 
                            @"(\d)(\+)(\d)", 
                            @"(\d)(\-)(\d)", 
                            @"(\d)(\^)(\d)", 
                            @"(\d)(\=)(\d)" 
                };
            foreach (string pattern in patterns)
            {
                Regex reg = new Regex(pattern);
                Match match = reg.Match(res);
                if (match.Success)
                    return replaceMatch(match, res);               
            }
            return res;
        }
 
        private static bool replaceWithBrackets(ref string res)
        {
            bool flag = false;
            string pattern2 = @"\((\d)(.)(\d)\)";
            Regex reg = new Regex(pattern2);
            Match match = reg.Match(res);
            if (match.Success)
            {
                res = replaceMatch(match, res);
                flag = true;
            }
            return flag;            
        }
 
        private static string ReplaceVariablesWithValues(int[] values, string expr)
        {            
            List<Group> matchesList = new List<Group>();
            FillMatchesList(expr, matchesList);
            string[] oldVars = (from gr in matchesList.Distinct(new Comparer()) select gr.Value).ToArray();
            //actual replacement
            for (int i = 0; i < matchesList.Count; i++)
            {
                for (int j = 0; j < oldVars.Length; j++)
                {
                    if (oldVars[j] == matchesList[i].Value)
                    {
                        expr = expr.ReplaceByIndex(values[j].ToString(), matchesList[i].Index, 1);
                        break;
                    }
                }
            }
            //endact
            return expr;
        }
 
        private static void FillMatchesList(string expr, List<Group> matchesList)
        {
            string patternnn = @"\w";
            Regex reg = new Regex(patternnn);
            Match match = reg.Match(expr);
            
            while (match.Success)
            {
                matchesList.Add(match.Groups[0]);
                match = match.NextMatch();
            }
        }
 
        private static bool CalulateDenials(ref string expr)
        {
            string pattern1 = @"\!(\d)";
            Regex reg = new Regex(pattern1);
            if (!reg.IsMatch(expr))
                return false;
            while (true)
            {
                Match match = reg.Match(expr);
                if (match.Success)
                {
                    expr = expr.ReplaceByIndex(denial(match.Groups[1].Value), match.Groups[0].Index, 2);
                    match = match.NextMatch();
                }
                else
                    break;
            }
            return true;
        }
 
        private static string replaceMatch(Match match, string res)
        {
            res = res.ReplaceByIndex(
            binaryOpps(
                match.Groups[1].Value,
                match.Groups[3].Value,
                match.Groups[2].Value
                ),
            match.Groups[0].Index, match.Groups[0].Value.Length);
            return res;
        }
        private static string denial(string arg)
        {
            string res = (arg == "0") ? "1" : "0";
            return res;
        }
        private static string binaryOpps(string a, string b, string sign)
        {
            string res = "";
            switch (sign)
            {
                case "+":
                res = (a== "0" && b=="0")? "0": "1";
                return res;
                case "-":
                res = (a== "0" && b=="1")? "0": "1";
                return res;
                case "*":
                res = (a== "1" && b=="1")? "1": "0";
                return res;
                case "^":
                res = (a!=b)? "1": "0";
                return res;
                case "=":
                res = (a==b)? "1": "0";
                return res;             
            }
            return "";
        }
    }
}
Всем спасибо, надеюсь кому-то пригодится

Решение задачи: «RegExp на практике (министатья для начинающих)»

textual
Листинг программы 
case "-":
res = (a== "1" && b=="0")? "0": "1";

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.833 из 5
Похожие ответы