Провести лексический анализ строки и сказать является ли она верным арифметическим выражением - C#

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

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

Прошу сильно не пинать, т.к. только начал изучать дискретку. Есть некоторый алфавит состоящий из чисел типа double, и следующих операций / * + - ( ) Плюс и минус могут быть как унарными, так и бинарными. На входе строка (System.String) над предложенным алфавитом, нужно 1. Провести лексический анализ строки и сказать является ли она верным арифметическим выражением 2. Вычислить данное арифметическое выражение. Может у кого-то есть реализация подобного конечного автомата (код или блок-схема), если поделитесь буду очень признателен.

Решение задачи: «Провести лексический анализ строки и сказать является ли она верным арифметическим выражением»

textual
Листинг программы
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  4.  
  5. namespace Math
  6. {
  7.     public static class CalculateExpression
  8.     {
  9.         private static readonly Dictionary<char, byte> _opdict = new Dictionary<char, byte> { { '+', 1 }, { '-', 2 }, { '/', 3 }, { '*', 4 }, { '(', 0 } };
  10.  
  11.         private static readonly HashSet<char> _operators = new HashSet<char> {'+', '-', '/', '*'};
  12.  
  13.         private static double CalculateSimple(double a, double b, char op) //Выполняем нужное вычисление в зависимости от операции
  14.         {
  15.             double result = 0;
  16.             switch (op)
  17.             {
  18.                 case '+':
  19.                     result = a + b;
  20.                     break;
  21.                 case '-':
  22.                     result = a - b;
  23.                     break;
  24.                 case '*':
  25.                     result = a*b;
  26.                     break;
  27.                 case '/':
  28.                     result = a/b;
  29.                     break;
  30.             }
  31.             return result;
  32.         }
  33.  
  34.         private static double StackCalc(double a, double b, char op) //Так как из стека достаем в обратном порядке, требуется инвертировать левый и правый операнды
  35.         {
  36.             return CalculateSimple(b, a, op);
  37.         }
  38.  
  39.         private static bool BadBreckets(string s) //Проверяем баланс скобок в строке
  40.         {
  41.             int i = 0;
  42.             foreach (var c in s)
  43.             {
  44.                 if (c == '(')
  45.                     i++;
  46.                 else if (c == ')')
  47.                     i--;
  48.             }
  49.             return i != 0;
  50.         }
  51.  
  52.         private static string Reverse(string s) //Обращаем строку в обратный порядок
  53.         {
  54.             int length = s.Length;
  55.             var sb = new StringBuilder(s.Length, s.Length);
  56.             for (int i = length - 1; i >= 0; i--)
  57.                 sb.Append(s[i]);
  58.             return sb.ToString();
  59.         }
  60.        
  61.         public static string ToRPN(string input) //Для более удобного анализа переводим в ОПН
  62.         {
  63.             string result = "";
  64.             var stack = new Stack<char>();
  65.             foreach (char c in input)
  66.             {
  67.                 if (c == '(')
  68.                     stack.Push(c);
  69.                 else if (c == ')')//Если встречаем закрывающую скобку, то вытряхиваем в строку все, до появления открывабщей скобки
  70.                 {
  71.                     while (stack.Count > 0)
  72.                     {
  73.                         char a = stack.Pop();
  74.                         if (a == '(') break;
  75.                         result += " " + a;
  76.                     }
  77.                 }
  78.                 else if (_operators.Contains(c))//Иначе если это оператор, вытряхиваем все операторы с большим приоритетом в строку, после этого засовываемся сами в стек
  79.                 {
  80.                     result += " ";
  81.                     while (stack.Count > 0 && _opdict[c] < _opdict[stack.Peek()])
  82.                     {
  83.                         result += stack.Pop() + " ";
  84.                     }
  85.                     stack.Push(c);
  86.                 }
  87.                 else result += c;  //Если это не скобки и не операторы, то это цифра, добавляем к выходной строке
  88.             }
  89.             while (stack.Count > 0) //Вытряхиваем в строку оставшиеся символы
  90.                 result += " " + stack.Pop();
  91.             return result;
  92.         }
  93.  
  94.         public static string ToPN(string input)
  95.         {
  96.             return Reverse(ToRPN(input));
  97.         }
  98.  
  99.         public static double? Calculate(string input) //Вычисляем выражение. Если формат ввода неправильный, возвращаем null
  100.         {
  101.             if (BadBreckets(input) || String.IsNullOrEmpty(input))
  102.                 return null;
  103.             var strings = ToRPN(input).Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
  104.             var stack = new Stack<double>(input.Length/2);
  105.             foreach (var s in strings)
  106.             {
  107.                 if (_opdict.ContainsKey(s[0])) //Если оператор, то выполняем его над последними двумя элементами стека.
  108.                 {
  109.                     if (stack.Count < 2) return null;
  110.                     stack.Push(StackCalc(stack.Pop(), stack.Pop(), s[0]));
  111.                 }
  112.                 else //Иначе это должно быть число, если вдруг что-то другое, то возвращаем null
  113.                 {
  114.                     double a;
  115.                     if (!double.TryParse(s, out a)) return null;
  116.                     stack.Push(a);
  117.                 }
  118.             }
  119.             return System.Math.Round(stack.Peek(), 15); //В стеке остается единственный элемент, значение выражения, который возвращаем
  120.         }
  121.     }
  122. }

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


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

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

12   голосов , оценка 3.917 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы