using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.IO; /* В текстовом файле записана без ошибок формула вида: <формула>=<цифра>|M(<формула>,<формула>)|m(<формула>,<формула>) <цифра>=0|1|2|3|4|5|6|7|8|9 M обозначает вычисление максимума, m – минимума Вычислить значение этой формулы Например M(m(3,5),M(1,2))=3 */ namespace SoloLearn { class Program { static void Main(string[] args) { string expr = "M(m(3,5),M(1,2))"; Console.WriteLine(ExpressionSolver.SolveFromString(expr)); } } class ExpressionSolver { //метод, решающий формулу, взятую из файла public static int SolveFromFile(string filepath) { string s = ReadFormula(filepath); if (s != null) return Solve(ParseExpression(s)); return 0; } //метод, решающий формулу прямо из строки public static int SolveFromString(string expression) { return Solve(ParseExpression(expression)); } //превращает строку с формулой в бинарное дерево private static TreeNode ParseExpression(string source) { //формула состоит из одной единственной цифры if (char.IsDigit(source[0])) return new TreeNode(source[0]); //формула состоит из чуть более иного, чем одна цифра TreeNode root = new TreeNode(); TreeNode temp = root; Stack nodes = new Stack(); nodes.Push(temp); foreach (char c in source) { switch (c) { case 'm': case 'M': nodes.Push(temp); temp.value = c; break; case '(': temp.left = new TreeNode(); temp = temp.left; break; case ',': temp = nodes.Peek(); temp.right = new TreeNode(); temp = temp.right; break; case ')': temp = nodes.Pop(); break; default: temp.value = c; break; } } return root; } // Заметьте: по условию задачи, нам изначально дано написанное // без ошибок выражение. Значит, если у узла есть левый // потомок, то у него есть и правый. private static int Solve(TreeNode parsedExpression) { //Дерево состоит из единственного узла, значение которого //и есть решение формулы if (parsedExpression.left == null) return int.Parse(parsedExpression.value.ToString()); //Инициализируемся Stack nodes = new Stack(); nodes.Push(parsedExpression); //Проходимся по дереву while (nodes.Count != 0) { //Берем последний добавленный элемент TreeNode currNode = nodes.Peek(); //У этого элемента нет потомков => этот элемент //содержит число if (currNode.left != null) { //читайте комментарий к функции if (currNode.left.left != null) { //если мы здесь, то данный узел в качестве value //содержит знак операции (m или M), а не число, //работает с левым поддеревом nodes.Push(currNode.left); } else if (currNode.right.right != null) { //аналогично условию выше, только для правого поддерева nodes.Push(currNode.right); } else { //если же мы здесь, то этот узел -- последний //из своего поддерева, содержащий знак, а не цифру. currNode = nodes.Pop(); int a = int.Parse(currNode.left.value.ToString()); int b = int.Parse(currNode.right.value.ToString()); currNode.value = (char)(48 + PerformAction(a, currNode.value, b)); currNode.left = null; currNode.right = null; } } //так как выражение правильное, можно не опасаться //за пустой стак else nodes.Pop(); } return int.Parse(parsedExpression.value.ToString()); } //чтение формулы из файла private static string ReadFormula(string path) { try { return File.ReadAllText(path); } catch (Exception e) { Console.WriteLine(e.Message); return null; } } //выполняем действие над двумя числами private static int PerformAction(int a, char action, int b) { return action switch { //поиск минимума 'm' => Minimum(a, b), //поиск максимума 'M' => Maximum(a, b), //никогда не должно произойти _ => '0' }; } //поиск МИНИМАЛЬНОГО числа из двух данных чисел private static int Minimum(int a, int b) { return a < b ? a : b; } //поиск МАКСИМАЛЬНОГО числа из двух данных чисел private static int Maximum(int a, int b) { return a > b ? a : b; } } class TreeNode { public char value; public TreeNode left; public TreeNode right; public TreeNode() {} public TreeNode(char c) { value = c; } public TreeNode(char c, TreeNode left, TreeNode right) { value = c; this.left = left; this.right = right; } } }

Expression Parsing