Задача по ссылке от Munin

[_Ivana]

В соседней теме участник Munin предложил (правда, не всем желающим, а ТС) следующую задачку http://atpp.vstu.edu.ru/cgi-bin/arh_pro ... id_prb=898
Однако, мне она показалась достаточно интересной - относительно простой, понятной, годящейся для начала и позволяющей потренироваться в устойчивости к некорректным входным данным. Вот я и взял и написал программку её решения (на языке 1С7.7 , мне так было проще, но это не принципиально, код приводится в теге оффтопика).

(Оффтоп)

Перем ВходящееВыражение;
Перем м_Ошибка, м_РезультатОшибка;
Функция ДатьРезультат(Знач ПозНач, Знач ПозКон) Далее
//------------------------------------------------------------------------------------------

Функция ДатьПозициюЗакрывающейСкобки(Знач ПозНач)
   Счетчик = 1;
   Для й = ПозНач + 1 По СтрДлина(ВходящееВыражение) Цикл
      ТекСимвол = Сред(ВходящееВыражение, й, 1);
      Если       ТекСимвол = "(" Тогда Счетчик = Счетчик + 1;
      ИначеЕсли    ТекСимвол = ")" Тогда Счетчик = Счетчик - 1;
      КонецЕсли;
      
      Если Счетчик = 0 Тогда Прервать; КонецЕсли;
   КонецЦикла;
   Если Счетчик <> 0 Тогда м_Ошибка = 1 КонецЕсли;
   
   Возврат й;
КонецФункции
//------------------------------------------------------------------------------------------

Функция ДатьАргумент(ПозНач)
   ПервыйСимвол = Сред(ВходящееВыражение, ПозНач, 1);
   Если ПервыйСимвол = "(" Тогда
      ПозЗакрывающейСкобки = ДатьПозициюЗакрывающейСкобки(ПозНач);
      Результат = ДатьРезультат(ПозНач + 1, ПозЗакрывающейСкобки - 1);
      ПозНач = ПозЗакрывающейСкобки + 1;
   Иначе
      Результат = ПервыйСимвол;
      ПозНач = ПозНач + 1;
   КонецЕсли;
   
   Возврат Результат;
КонецФункции
//------------------------------------------------------------------------------------------

Функция ДатьРезультат(Знач ПозНач, Знач ПозКон)
   
   Если м_Ошибка = 1 Тогда Возврат м_РезультатОшибка КонецЕсли;
   
   Пока Сред(ВходящееВыражение, ПозНач, 1) = "(" Цикл
      Если ДатьПозициюЗакрывающейСкобки(ПозНач) = ПозКон Тогда
         ПозНач = ПозНач + 1;
         ПозКон = ПозКон - 1;
      Иначе
         Прервать;
      КонецЕсли;
   КонецЦикла;
   
   Если ПозНач > ПозКон Тогда
      м_Ошибка = 1;
       Возврат м_РезультатОшибка;
   ИначеЕсли ПозНач = ПозКон Тогда
       Возврат Сред(ВходящееВыражение, ПозНач, 1);
   КонецЕсли;
   
   Результат = "";
   Пока ПозНач < ПозКон Цикл
      Если Результат = "" Тогда
         ЛевыйАргумент = ДатьАргумент(ПозНач);
      Иначе
         ЛевыйАргумент = Результат;
      КонецЕсли;
      СимволОперации = Сред(ВходящееВыражение, ПозНач, 1);
      ПозНач = ПозНач + 1;
      
      Если (СимволОперации = "+") или (СимволОперации = "-") Тогда
         // правый аргумент берем до конца входящей строки
         ПравыйАргумент = ДатьРезультат(ПозНач, ПозКон);
         ПозНач = ПозКон + 1;
      Иначе
         // умножаем и делим только на ближайший аргумент
         ПравыйАргумент = ДатьАргумент(ПозНач);
      КонецЕсли;
      
      Результат = "(" + ЛевыйАргумент + "," + ПравыйАргумент + ")";
      Если       СимволОперации = "+" Тогда Результат = нрег(" ADD") + Результат;
      ИначеЕсли    СимволОперации = "-" Тогда Результат = нрег(" SUB") + Результат;
      ИначеЕсли    СимволОперации = "*" Тогда Результат = нрег(" MUL") + Результат;
      ИначеЕсли    СимволОперации = "/" Тогда Результат = нрег(" DIV") + Результат;
      Иначе                           м_Ошибка = 1;
      КонецЕсли;
   КонецЦикла;
   
   Возврат ?(м_Ошибка = 1, м_РезультатОшибка, Результат);
КонецФункции
//------------------------------------------------------------------------------------------

Процедура Сформировать()
   м_Ошибка = 0;
   м_РезультатОшибка = "Ошибка";
   
   // первично форматируем входящее выражение - убираем пробелы, в верхний регистр
   ВходящееВыражение = ВРЕГ(СтрЗаменить(СокрЛП(ВыбВходящееВыражение), " ", ""));
   
   ВыбРезультатВыражение = СокрЛП(ДатьРезультат(1, СтрДлина(ВходящееВыражение)));
КонецПроцедуры

Хотелось бы обсудить:
1) алгоритмические моменты
2) протестировать реакцию на разнообразно-некорректные входные данные
3) протестировать правильность вычислений (могу написать парсер выходного языка и вычисление значения выражений со случайными входными аргументами, и сравнить его с вычислением значения из исходной строки)
Для пунктов 2 и 3 можно предлагать навороченные строки в качестве исходных данных, буду выдавать результат.

[Xaositect]

Если меня не глючит, будет неправильно работать на строке "a-b-c" ( будет выдавать SUB(a,SUB(b,c)), а надо SUB(SUB(a, b), c) )
Также проверьте "a+b*", но тут зависит от поведения функции Сред, которого я не знаю.

(Оффтоп)

Что плохо с этим вашим 1с - запрос в поисковик "1С Сред конец строки" выдает что-то про среды.

[_Ivana]

1) a-b-c перевод sub(A, sub(B,C)) - как вы и предполагали Но тут немного философский вопрос, правильно это или нет. Если, например, явно указать порядок скобками, то получается (a-b)-c перевод sub( sub(A,B),C). А если явно не указывать, то я позволил себе более удобный мне порядок. Во всяком случае, требование автора задачи "Операнды должны идти в том же порядке, что и во входном выражении." не нарушается. Я похоже сильно ошибся и сделал неправильно! Эта моя алгоритмическая ошибка делает некорректным весь алгоритм... Ладно, доработаем...

2) a+b* перевод add(A, mul(B,)) - явная ошибка, спасибо вам, буду совершенствовать устойчивость. Я еще сам нашел, что +++ перевод add(+,+) - тоже буду дорабатывать Я пока выложил в каком-то смысле "сырой" код - работающий, но не стопроцентно отрабатывающий некорректные данные. Доработаю, и если будет интерес - выложу код. Но алгоритмически он останется тот же самый, только будут дополнительные проверки и выставление флага ошибки при определенных ситуациях. Найденная выше ошибка автоматически аннулирует это высказывание...

(Оффтоп)

Сред в 1С - средняя часть строки начиная с определенного номера символа, возвращает заданное количество символов, если не указано - то до конца строки. В С я бы написал с указателями и значениями по ним - выглядело бы проще

[Xaositect]

(Оффтоп)

_Ivana в сообщении #686984 писал(а):

Сред в 1С - средняя часть строки начиная с определенного номера символа, возвращает заданное количество символов, если не указано - то до конца строки. В С я бы написал с указателями и значениями по ним - выглядело бы проще

Что она делает, я догадался. Но вот как она будет реагировать на аргументы, вылезающие за строку, я не смог найти.

[_Ivana]

Вы, возможно, будете смеяться, но если мой алгоритм будет выдавать a-b-c перевод sub(A, add(B,C)), то это будет считаться правильным решением задачи?

[Xaositect]

Цитата:

Выражения языка L записываются по обычным правилам [...]

По обычным правилам a-b-c означает (a-b)-c, а не a-(b-c)

[_Ivana]

То что вы написали, бесспорно. И я уже наступил на эти грабли и испытал некоторое чувство стыда от этого Но мне кажется, вы могли иметь в виду a-b-c означает (a-b)-c, а не a-(b+c). Сейчас фактически я могу сделать 2 алгоритма - переводящие a-b-c в sub( sub(A,B),C) и в sub(A, add(B,C)). Конечно предпочтительнее первый, но второй как шуточный вариант я тоже наверное реализую

[Xaositect]

Ой, извините. Не заметил.

Цитата:

[...]Получить запись этого выражения на языке F.[...]

На мой взляд, с ADD будет другое выражение, хотя и реализующее ту же функцию.

[_Ivana]

Изменил пробежку по строке - теперь бегу с конца в начало, соответственно порядок рекурсии меняется на противоположный и цепочка вычитаний раскручивается правильно. Но может ещё какая ошибка принципиальная наличествует. Корректность входных данных пока не отрабатывал, не до грибов Код:

(Оффтоп)

Перем ВходящееВыражение;
Перем м_Ошибка, м_РезультатОшибка;
Функция ДатьРезультат(Знач ПозНач, Знач ПозКон) Далее
//------------------------------------------------------------------------------------------

Функция ДатьПозициюОткрывающейСкобки(Знач ПозКон)
   Счетчик = 1;
   Для йй = 1 По ПозКон - 1 Цикл
      й = ПозКон - йй;
      ТекСимвол = Сред(ВходящееВыражение, й, 1);
      Если       ТекСимвол = ")" Тогда Счетчик = Счетчик + 1;
      ИначеЕсли    ТекСимвол = "(" Тогда Счетчик = Счетчик - 1;
      КонецЕсли;
      
      Если Счетчик = 0 Тогда Прервать; КонецЕсли;
   КонецЦикла;
   Если Счетчик <> 0 Тогда м_Ошибка = 1 КонецЕсли;
   
   Возврат й;
КонецФункции
//------------------------------------------------------------------------------------------

Функция ДатьАргументСлева(ПозКон)
   ПервыйСимвол = Сред(ВходящееВыражение, ПозКон, 1);
   Если ПервыйСимвол = ")" Тогда
      ПозСкобки = ДатьПозициюОткрывающейСкобки(ПозКон);
      Результат = ДатьРезультат(ПозСкобки + 1, ПозКон - 1);
      ПозКон = ПозСкобки - 1;
   Иначе
      Результат = ПервыйСимвол;
      ПозКон = ПозКон - 1;
   КонецЕсли;
   
   Возврат Результат;
КонецФункции
//------------------------------------------------------------------------------------------

Функция ДатьРезультат(Знач ПозНач, Знач ПозКон)
   
   Если м_Ошибка = 1 Тогда Возврат м_РезультатОшибка КонецЕсли;
   
   Пока Сред(ВходящееВыражение, ПозКон, 1) = ")" Цикл
      Если ДатьПозициюОткрывающейСкобки(ПозКон) = ПозНач Тогда
         ПозНач = ПозНач + 1;
         ПозКон = ПозКон - 1;
      Иначе
         Прервать;
      КонецЕсли;
   КонецЦикла;
   
   Если ПозНач > ПозКон Тогда
      м_Ошибка = 1;
       Возврат м_РезультатОшибка;
   ИначеЕсли ПозНач = ПозКон Тогда
       Возврат Сред(ВходящееВыражение, ПозНач, 1);
   КонецЕсли;
   
   Результат = "";
   Пока ПозНач < ПозКон Цикл
      Если Результат = "" Тогда
         ПравыйАргумент = ДатьАргументСлева(ПозКон);
      Иначе
         ПравыйАргумент = Результат;
      КонецЕсли;
      СимволОперации = Сред(ВходящееВыражение, ПозКон, 1);
      ПозКон = ПозКон - 1;
      
      Если (СимволОперации = "+") или (СимволОперации = "-") Тогда
         // левый аргумент берем до начала входящей строки
         ЛевыйАргумент = ДатьРезультат(ПозНач, ПозКон);
         ПозКон = ПозНач - 1;
      Иначе
         // умножаем и делим только на ближайший аргумент
         ЛевыйАргумент = ДатьАргументСлева(ПозКон);
      КонецЕсли;
      
      Результат = "(" + ЛевыйАргумент + "," + ПравыйАргумент + ")";
      Если       СимволОперации = "+" Тогда Результат = нрег(" ADD") + Результат;
      ИначеЕсли    СимволОперации = "-" Тогда Результат = нрег(" SUB") + Результат;
      ИначеЕсли    СимволОперации = "*" Тогда Результат = нрег(" MUL") + Результат;
      ИначеЕсли    СимволОперации = "/" Тогда Результат = нрег(" DIV") + Результат;
      Иначе                           м_Ошибка = 1;
      КонецЕсли;
   КонецЦикла;
   
   Возврат ?(м_Ошибка = 1, м_РезультатОшибка, Результат);
КонецФункции
//------------------------------------------------------------------------------------------

Процедура Сформировать()
   м_Ошибка = 0;
   м_РезультатОшибка = "Ошибка";
   
   // первично форматируем входящее выражение - убираем пробелы, в верхний регистр
   ВходящееВыражение = ВРЕГ(СтрЗаменить(СокрЛП(ВыбВходящееВыражение), " ", ""));
   
   ВыбРезультатВыражение = СокрЛП(ДатьРезультат(1, СтрДлина(ВходящееВыражение)));
КонецПроцедуры

[Xaositect]

Теперь с делениями та же проблема: "a/b/c" будет DIV(a, DIV(b,c))

[_Ivana]

Точно! Хотел с наскока, а придется все таки подумать...

[_Ivana]

Релиз бета.3: бегу по строке слева направо, но перед пробежкой добавляю дополнительные скобки для определения порядка сложений-вычитаний текущего уровня рекурсии. Мне самому этот метод не кажется изящным, но вроде вышеупомянутые ошибки не допускает. В функцию передаются не указатели а сама строка по значению, внутри функции она ещё и изменяется - лишний кусочек ОЗУ не экономим. В функцию ДатьАргумент передается строка по ссылке, внутри отрезается. Код:

(Оффтоп)

Перем ВходящееВыражение;
Перем м_Ошибка, м_РезультатОшибка;
Функция ДатьРезультат(Знач ПереданаСтрока) Далее
//------------------------------------------------------------------------------------------

Функция ДатьПозициюЗакрывающейСкобки(Знач ПереданаСтрока, Знач ПозНач)
   Счетчик = 1;
   Для й = ПозНач + 1 По СтрДлина(ПереданаСтрока) Цикл
      ТекСимвол = Сред(ПереданаСтрока, й, 1);
      Если       ТекСимвол = "(" Тогда Счетчик = Счетчик + 1;
      ИначеЕсли    ТекСимвол = ")" Тогда Счетчик = Счетчик - 1;
      КонецЕсли;
      
      Если Счетчик = 0 Тогда Прервать; КонецЕсли;
   КонецЦикла;
   Если Счетчик <> 0 Тогда м_Ошибка = 1 КонецЕсли;
   
   Возврат й;
КонецФункции
//------------------------------------------------------------------------------------------

Функция ДатьАргумент(ПереданаСтрока)
   ПервыйСимвол = Сред(ПереданаСтрока, 1, 1);
   Если ПервыйСимвол = "(" Тогда
      ПозЗакрывающейСкобки = ДатьПозициюЗакрывающейСкобки(ПереданаСтрока, 1);
      Результат = ДатьРезультат(Сред(ПереданаСтрока, 1, ПозЗакрывающейСкобки));
      ПереданаСтрока = Сред(ПереданаСтрока, ПозЗакрывающейСкобки + 1);
   Иначе
      Результат = ПервыйСимвол;
      ПереданаСтрока = Сред(ПереданаСтрока, 2);
   КонецЕсли;
   
   Возврат Результат;
КонецФункции
//------------------------------------------------------------------------------------------

Функция ДатьРезультат(Знач ПереданаСтрока)
   
   Если м_Ошибка = 1 Тогда Возврат м_РезультатОшибка КонецЕсли;
   
   Пока Сред(ПереданаСтрока, 1, 1) = "(" Цикл
      Если ДатьПозициюЗакрывающейСкобки(ПереданаСтрока, 1) = СтрДлина(ПереданаСтрока) Тогда
         ПереданаСтрока = Сред(ПереданаСтрока, 2, СтрДлина(ПереданаСтрока) - 2);
      Иначе
         Прервать;
      КонецЕсли;
   КонецЦикла;
   
   Если ПереданаСтрока = "" Тогда
      м_Ошибка = 1;
       Возврат м_РезультатОшибка;
   ИначеЕсли СтрДлина(ПереданаСтрока) = 1 Тогда
       Возврат ПереданаСтрока;
   КонецЕсли;
   
   // вставим в наш аргумент дополнительные скобки для определения порядка вычисления вычитаний и сложений
   ПромСтрока = "";
   УровеньОпераций = 0;
   КоличествоДобавилиСкобок = 0;
   Для й = 1 по СтрДлина(ПереданаСтрока) Цикл
      ТекСимвол = Сред(ПереданаСтрока, й, 1);
      Если       ТекСимвол = "(" Тогда УровеньОпераций = УровеньОпераций + 1;
      ИначеЕсли    ТекСимвол = ")" Тогда УровеньОпераций = УровеньОпераций - 1;
      КонецЕсли;
      
      Если ((ТекСимвол = "-") или (ТекСимвол = "+")) и (УровеньОпераций = 0) Тогда
         ПромСтрока = ПромСтрока + ")" + ТекСимвол;
         КоличествоДобавилиСкобок = КоличествоДобавилиСкобок + 1;
      Иначе
         ПромСтрока = ПромСтрока + ТекСимвол;
      КонецЕсли;
   КонецЦикла;
   Для й = 1 по КоличествоДобавилиСкобок Цикл
      ПромСтрока = "(" + ПромСтрока;
   КонецЦикла;
   ПереданаСтрока = ПромСтрока;
   //Если КоличествоДобавилиСкобок > 0 Тогда Сообщить(ПереданаСтрока); КонецЕсли;

   Результат = "";
   Пока СтрДлина(ПереданаСтрока) > 0 Цикл
      Если Результат = "" Тогда
         ЛевыйАргумент = ДатьАргумент(ПереданаСтрока);
      Иначе
         ЛевыйАргумент = Результат;
      КонецЕсли;
      СимволОперации = Сред(ПереданаСтрока, 1, 1);
      ПереданаСтрока = Сред(ПереданаСтрока, 2);
      
      Если (СимволОперации = "+") или (СимволОперации = "-") Тогда
         // правый аргумент берем до конца входящей строки
         ПравыйАргумент = ДатьРезультат(ПереданаСтрока);
         ПереданаСтрока = "";
      Иначе
         // умножаем и делим только на ближайший аргумент
         ПравыйАргумент = ДатьАргумент(ПереданаСтрока);
      КонецЕсли;
      
      Результат = "(" + ЛевыйАргумент + "," + ПравыйАргумент + ")";
      Если       СимволОперации = "+" Тогда Результат = нрег(" ADD") + Результат;
      ИначеЕсли    СимволОперации = "-" Тогда Результат = нрег(" SUB") + Результат;
      ИначеЕсли    СимволОперации = "*" Тогда Результат = нрег(" MUL") + Результат;
      ИначеЕсли    СимволОперации = "/" Тогда Результат = нрег(" DIV") + Результат;
      Иначе                           м_Ошибка = 1;
      КонецЕсли;
   КонецЦикла;
   
   //Возврат ?(м_Ошибка = 1, м_РезультатОшибка, Результат);
   Возврат Результат;
КонецФункции
//------------------------------------------------------------------------------------------

Процедура Сформировать()
   м_Ошибка = 0;
   м_РезультатОшибка = "Ошибка";
   
   // первично форматируем входящее выражение - убираем пробелы, в верхний регистр
   ВходящееВыражение = ВРЕГ(СтрЗаменить(СокрЛП(ВыбВходящееВыражение), " ", ""));
   
   ВыбРезультатВыражение = СокрЛП(ДатьРезультат(ВходящееВыражение));
КонецПроцедуры

[arseniiv]

(Оффтоп)

Обычно такие вещи с помощью грамматики реализуют. Особенно когда ассоциативность операций бывает разная.

[_Ivana]

alpha - beta - delta - gamma + phi/psi/ro/epsilon
ADD( SUB( SUB( SUB(alpha,beta),delta),gamma), DIV( DIV( DIV(phi,psi),ro),epsilon))

и отработка некорректных данных

[Xaositect]

По условию операнды однобуквенные, но многобуквенные операнды - это усложнение задачи, так что ок :)
Кстати, мой вариант (Haskell, quick and dirty, естественно без использования готовых парсеров)

Используется синтаксис Haskell

module Main where

import Data.Char
import Control.Applicative
import Control.Monad
import Control.Arrow

splitOn :: (a -> Bool) -> [a] -> ([[a]], [a])
splitOn p xs = 
  let 
    (prefix, rest) = break p xs
  in 
    if null rest
      then ([prefix], [])
      else (prefix:) *** (head rest :) $ (splitOn p $ tail rest)

type Marked = (Char, Integer)
data Tree = Leaf Char | Branch Char Tree Tree
type Parser = [Marked] -> Maybe Tree

instance Show Tree where
  show (Leaf c) = c:[]
  show (Branch c l r) = (op c) ++ "(" ++ (show l) ++ ", " ++ (show r) ++ ")"

isVar :: Char -> Bool
isVar c = isAlpha c && isAscii c

op :: Char -> String
op '+' = "ADD"
op '-' = "SUB"
op '*' = "MUL"
op '/' = "DIV"

mark :: String -> [Marked]
mark str = mark' (filter (/= ' ') str) 0 where
  mark' [] _ = []
  mark' ('(':rest) i = ('(', i):(mark' rest (i+1))
  mark' (')':rest) i = (')', i-1):(mark' rest (i-1))
  mark' (c:rest) i = (c, i):(mark' rest i)

parseLeftAssoc :: [Char] -> Parser -> Parser
parseLeftAssoc operators subparser str =
  let
    level = snd $ head str
    (summands, ops) = (reverse *** reverse) $ (map subparser *** map fst) $ splitOn ((flip elem operators) *** (==level) >>> uncurry (&&)) str
  in
    go summands ops
  where
    go [e] [] = e
    go [e] _ = Nothing
    go (e:es) (o:os) = Branch o <$> (go es os) <*> e

parseBracket :: Parser -> Parser
parseBracket _ [(c, n)] = guard (isVar c) >> (return $ Leaf c)
parseBracket subparser (('(', n):xs) = guard (last xs == (')', n)) >> (subparser $ init xs)
parseBracket _ _ = Nothing

parseExpr :: Parser
parseExpr = parseLeftAssoc "+-" $ parseLeftAssoc "*/" $ parseBracket parseExpr

parse :: String -> Maybe Tree
parse = parseExpr . mark

main :: IO ()
main = do
  string <- getLine
  let tree = parse string
  case tree of
    Nothing -> print "Error"
    Just t -> print t