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, учитывая приоритет операций и (). Также проверяет строку на соответствие правилам.
Приступаем:
метод, который строит таблицу:
метод, который решает выражение:
метод, который вычисляет отрицание:
метод, который вычисляет подвыражения в скобках:
метод replaceMatch который здесь используется выглядит так:
метод binaryOpps это простой свитч и ничего лишнего
вернемся к методам для вычислений, replaceWithBrackets, вычисляет подвыражения без скобок с учетом приоритета
Это основа класса, полный выглядит вот так:
Всем спасибо, надеюсь кому-то пригодится
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; }
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; }
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 ""; }
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";
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д