Для начала выделим регулярные выражения для чисел и действий:
private const string RegexBr = "\\(([1234567890\\.\\+\\-\\*\\/^%]*)\\)"; // Скобки
private const string RegexNum = "[-]?\\d+\\.?\\d*"; // Числа
private const string RegexMulOp = "[\\*\\/^%]"; // Первоприоритетные числа
private const string RegexAddOp = "[\\+\\-]"; // Второприоритетные числа
Теперь метод, который полученную строку разделяет на элементы и рекурсивно их вычисляет:
public static double Parse(string str)
{
// Парсинг скобок
var matchSk = Regex.Match(str, RegexBr);
if (matchSk.Groups.Count > 1)
{
string inner = matchSk.Groups[0].Value.Substring(1, matchSk.Groups[0].Value.Trim().Length - 2);
string left = str.Substring(0, matchSk.Index);
string right = str.Substring(matchSk.Index + matchSk.Length);
return Parse(left + Parse(inner).ToString(CultureInfo.InvariantCulture) + right);
}
// Парсинг действий
var matchMulOp = Regex.Match(str, string.Format("({0})\\s?({1})\\s?({2})\\s?", RegexNum, RegexMulOp, RegexNum));
var matchAddOp = Regex.Match(str, string.Format("({0})\\s?({1})\\s?({2})\\s?", RegexNum, RegexAddOp, RegexNum));
var match = matchMulOp.Groups.Count > 1 ? matchMulOp : matchAddOp.Groups.Count > 1 ? matchAddOp : null;
if (match != null)
{
string left = str.Substring(0, match.Index);
string right = str.Substring(match.Index + match.Length);
return Parse(left + ParseAct(match).ToString(CultureInfo.InvariantCulture) + right);
}
// Парсинг числа
try
{
return double.Parse(str, CultureInfo.InvariantCulture);
}
catch (FormatException)
{
throw new FormatException(string.Format("Неверная входная строка '{0}'", str));
}
}
И последним напишем метод, который непосредственно вычисляет значение действия:
private static double ParseAct(Match match)
{
double a = double.Parse(match.Groups[1].Value, CultureInfo.InvariantCulture);
double b = double.Parse(match.Groups[3].Value, CultureInfo.InvariantCulture);
switch (match.Groups[2].Value)
{
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
case "/": return a / b;
case "^": return Math.Pow(a, b);
case "%": return a % b;
default: throw new FormatException($"Неверная входная строка '{match.Value}'");
}
}
Такое вот «ненормальное программирование» у меня было. Исходный текст полностью приводить не вижу никакого смысла — вряд ли это кому-нибудь понадобится. Но в любом случае составить класс из трех кусков — дело пары секунд.
Спасибо за внимание.
Комментарии (16)
Kroleg
19.11.2015 22:37#include <stdio.h> #include <stdlib.h> double eval(char*&p); bool is(char*&p, char c) { return *p == c ? p++, true : false; } double un(char*&p) { if (is(p, '(')) { double r = eval(p); if (!is(p, ')')) printf("expected ')'"); return r; } else return strtod(p, &p); } double muls(char*&p) { double r = un(p); for (;;) { if (is(p, '*')) r *= un(p); else if (is(p, '/')) r /= un(p); else return r; } } double eval(char*&p) { double r = muls(p); for (;;) { if (is(p, '+')) r += muls(p); else if (is(p, '-')) r -= muls(p); else return r; } } int main(int argc, char** argv) { double r = eval(argv[1]); if (*argv[1] == 0) printf("%lf", r); else printf("error at %s", argv[1]); }
A1ien
20.11.2015 12:36Ну и? Тут кто-то кроме вас разберется? Был у меня подобный код, через пол года смотришь на него как баран на новые ворота. В итоге подобную задачу (делал скриптовый язык для МК) решил при помощи связки лекс/бизон компиляция в VM, а на микроконтроллере конечный автомат разбора и исполнения простейшей стековой VM, все красиво все понятно.
Kroleg
20.11.2015 18:54И моей команде, да и мне самому через 10 лет будет легко разобраться в этом коде,
потому что:
- Это классический рекурсивный спуск, описанный в классическом труде Вирта,
который, в силу особенностей российской системы образования, знаком каждому прораммисту. - Этот код, занимающий 30 строк текста, и не имеющий ни одной внешней зависимости,
проще в чтении, чем одно определение RegexBr из верхнего примера. - Этот код является формальной записью BNF разбираемого выражения на языке Си.
В самом деле, посмотрите функцию muls, разбирающую операции с приоритетом умножения,
и сравните ее с BNF записью (естественно, освобожденной от левой рекурсии):
muls ::= unar muls_tail muls_tail ::= "" | '*' unar muls_tail | '/' unar muls_tail
Что касается lex/bison. Для полноценного скриптового языка его применение может быть оправдано. Но для вычисления простого выражения — это — как из пушки по воробьям.
Стековая машина имеет примерно двукратный оверхед по скорости и полуторакратный оверхед по памяти байткода по сравнению с регистровой машиной. На микроконтроллере это может быть критично.
Приведенная мной прямая интерпретация выражения примерно в полтора раза медленнее виртуальной машины и на порядки быстрее парсинга бизоном и исполнения на vm.
Если производительность критична, я бы подумал о генерации машинного кода и выбрал микроконтроллер, который умеет исполнять код из RAM.A1ien
20.11.2015 18:591. Скорость была не критична,
2. Я немного не понял, вы хотите сказать, что код для витруальной машины исполняемой на МК пусть даже стековой, будет медленнее нежели прямой парсинг?
Может я не корректно высказался — на VM исполнялся именно байткод.Kroleg
20.11.2015 20:16Если задача — загрузить в МК выражение (в любой форме) и выполнить его вычисление, то ниже — все способы, расположенные от быстрых к медленным:
- Фрагмент машинного кода (МК должен уметь исполнять из RAM)
- Регистровый байт-код // в 4..8 раз медленнее предыдущего варианта
- Стековый байт-код // в 2 раза медленнее предыдущего варианта
- Текстовое выражение (парсить моим eval) // в 2 раза медленнее предыдущего варианта
- Текстовое выражение (парсить через «автомат разбора и исполнения простейшей стековой VM»)// существенно медленнее предыдущего варианта + память для байт-кода
- Это классический рекурсивный спуск, описанный в классическом труде Вирта,
Zibx
19.11.2015 23:26С похожим порывом писал в школе парсер на visual basic. Только в те времена регулярные выражения я считал черными ящиками, работающими на магии, потому разбирал руками. Первый вариант искал самую глубокую скобку, а потом лез наверх. Но это оказалось очень медленно (я писал штуку для построения графиков). А вот второй вариант работал примерно тем же образом, но строил цепочку операций которые приводили к вычислению выражения. Фактически — постфиксная запись, обёрнутая в некое подобие виртуальной машины. И вот тогда рисовальщик графиков стал летать.
rafuck
20.11.2015 03:17C# без интернета? Без интернета было много чего, но только не C#
leremin
20.11.2015 04:46Почему это? Диск с 2005, кажется, студией в палатке в метро — и поехали.
rafuck
20.11.2015 15:10Я к тому, что ссылаться на недоступность сети Internet в том же 2005 году несколько странно. Не такое уж это дремучее было время.
leremin
20.11.2015 16:09У кого как.
rafuck
20.11.2015 21:46В 2005 году я лично общался с одноклассниками из поселка Ванавара Тунгусско-Чунского района Эвенкийского Автономного Округа. В который даже продукты доставляют раз в год баржами по весне.
Общался через интернет. Так что я примерно представляю у кого как. Хотя неважно это. Пусть не было интернета тогда. Это не оправдание для вычисления арифметических выражений при помощи выражений регулярных.
lockywolf
Регулярные выражения — это в каком-то смысле и есть конечные автоматы. То есть, регулярка компилируется в конечный автомат, в котором терминальные вершины — как раз «нашлось» и «не нашлось».
То есть, на самом деле, вы всё по науке сделали.
leremin
Да, согласен. Я имел ввиду, что в то время я и слов таких-то не знал.
KvanTTT
Ну с наукой вы мягко говоря преувеличили. По науке выражения нужно парсить с помощью кс-парсеров и вычислять на каждом подвыражении промежуточный результат, а в идеале строить граф и обходить его. И не использовать регулярки.
zagayevskiy
Какой отвратительно неверный вывод вы сделали из верной посылки.