Форум программистов, компьютерный форум, киберфорум
Наши страницы
Haskell
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
zeroalef
-13 / 11 / 1
Регистрация: 29.03.2019
Сообщений: 64
1

Molecule to atoms

21.04.2019, 23:17. Просмотров 804. Ответов 21

Приветствую специалистов и любителей языка haskell. Я обращаюсь в эту ветку по той причине, что haskell является языком со строгой статической типизацией, а саму задачу я пытаюсь решить на языке rust (тоже очень строгая и очень статическая =) ). Отсутсвие опыта работы с подобными техниками ставит меня в тупик. Скажем, python/c++ не вызвали бы у меня такой зуд, но запахло керосином. Так что прошу помочь мне решить задачу у вас. Оригинал постановки здесь. Кому лень линкать описываю своими словами:
Кликните здесь для просмотра всего текста
Дана строка (молекула) вида "K4[ON(SO3)2]2". Требуется распарсить ее и вернуть список списков/кортежей/выбрать_свое вида
[("K", 4), ("O", 14),("N", 2),("S", 4)]

У меня тут получается громоздкое и совсем запутанное (много типов пришлось костылить) решение, которое к тому же я еще и не завершил, а уже напрягся как электричество.
Кликните здесь для просмотра всего текста
Код
type Atom = (String, usize);
type Molecule = Vec<Atom>;
type NumCatch = (bool, i32, Vec<char>);
type ElemCatch = (bool, String, Vec<char>);
type BraceCatch = (bool, char, Vec<char>);

fn catch_num(v: Vec<char>) -> NumCatch {
    ...
}


fn catch_element(v: Vec<char>) -> ElemCatch {
    ...
}

fn catch_brace(v: Vec<char>) -> BraceCatch {
    ...
}

fn is_open_brace(ch: char) -> bool {
    ...
}

fn is_cole_brace(ch: char) -> bool {
    ...
}

fn get_colse_brace(ch: char) -> char {
    ...
}

fn catch_expr(v: Vec<char>, ) -> HashMap<String, i32> {
    ...
}

//pub fn parse_molecule(s: &str) -> Result<Molecule, ParseError> {
//  Err(ParseError{})
//}
Я справедливо подозреваю что все гораздо проще и элегантней.
0
XRuZzz
Антикодер
1614 / 775 / 44
Регистрация: 15.09.2012
Сообщений: 2,883
22.04.2019, 00:02 2
Для сложного парсинга используются комбинаторные парсеры. А тут вы хотите без комбинаторных парсеров решить?
1
zeroalef
-13 / 11 / 1
Регистрация: 29.03.2019
Сообщений: 64
22.04.2019, 00:21  [ТС] 3
XRuZzz, я не вижу здесь сложного парсинга. А "комбинаторные парсеры" -- для меня, увы, совсем непонятное выражение. Сложность в том, что я совсем не умею использовать типизацию подобного рода. Если угодно, само проектирование решения ставит в ступор.

Добавлено через 5 минут
XRuZzz, смотрите. В моем решении функции catch_elem, catch_num, catch_brace возвращают разные типы. Это вызывает затруднения с их поочередными вызовами в функции catch_expr. Затруднения, если угодно, с точки зрения "чистоты кода".
0
XRuZzz
Антикодер
1614 / 775 / 44
Регистрация: 15.09.2012
Сообщений: 2,883
22.04.2019, 05:01 4
Точно не скажу(уже голова не робит). Но мне кажется рекурсивно отщипываем от строки(списка) по одному элементу, и классифицируем его, если не классифицируется кладём в промежуточный буфер, и продолжаем отщипывать по элементу, до тех пока не сможем разобрать промежуточный буфер. Тип промежуточного буфера тоже строка.
Пример не рабочего кода
Кликните здесь для просмотра всего текста
Haskell
1
2
3
4
5
6
7
8
parse (x:xs) accList accElem
  | isUpcaseChar x = parse xs accList (accElem ++ [x])
  | isLowcaseChar x && accElem /= [] = parse xs accList (accElem ++ [x])
  | isNumber x && accElem /= [] = parse xs (accList++[(accElem, charToInt x)]) []
  | isOpenBrace x && accElem /= [] = parse xs accList (accElem ++ x)
  | isOpenBrace x = parse xs accList (accElem ++ x)
  | isCloseBrace x && accElem /= [] = parse xs (accList ++ parse accElem [] x)
  | otherwise = parse xs accList accElem


Тут конечно нужно добавлять обработку исключений, подчёт атомов и прочее.

Решение на комбинаторных парсерах было бы более профессиональным:
https://habr.com/ru/post/436234/
Но для этого нужно разбираться в классах типов.
1
22.04.2019, 05:01
loothood
88 / 70 / 11
Регистрация: 07.06.2015
Сообщений: 119
Записей в блоге: 12
22.04.2019, 07:24 5
Для подобных задач в мире rust используется nom. Попробуйте. Если возникнут вопросы, спрашивайте.
1
XRuZzz
Антикодер
1614 / 775 / 44
Регистрация: 15.09.2012
Сообщений: 2,883
22.04.2019, 12:26 6
Я думаю, тут сначала нужно производить разбор элементов формулы, в список или дерево, а затем производить необходимые преобразования в список количества атомов.
Вот первый этап, но код по прежнему сильно сыроват:
Кликните здесь для просмотра всего текста
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
module Cyberforum.MoleculeParsing.Molecule where
 
import Data.Char (isUpper, isLower, isLetter, isDigit)
import Data.List (elem)
import Debug.Trace (trace)
data Atom = EmptyAtom | H | He | Skip1 | C | N | O | F | Ne | Na | Mg | Al
  deriving (Enum, Eq, Ord, Read, Show)
type Dare = [(Atom, Int)]
 
data Gram = Atom1 Atom | Number1 Int | BracketOpen | BracketClose
  deriving (Eq, Read, Show)
 
parseElem :: String -> Gram
parseElem xxs@(x:xs)
    | isUpper x = -- trace ("trace parseElem " ++ show x) $
      Atom1 (read xxs :: Atom)
    | x `elem` ['(', '[', '{'] = BracketOpen
    | x `elem` [')', ']', '}'] = BracketClose
    | isDigit x = Number1 (read xxs :: Int)
    | otherwise = undefined
 
parse :: String ->[Gram] -> String -> [Gram]
parse [] accList [] = accList
parse [] accList accElem = trace (show accList) $ accList ++ [parseElem accElem]
parse (x:xs) accList []
    | isUpper x = -- trace ("trace parse isUpper [] " ++  show x) $
      parse xs accList [x]
    | x `elem` ['(', '[', '{'] = parse xs (accList ++ [BracketOpen]) []
    | x `elem` [')', ']', '}'] = parse xs accList []
    | isDigit x = parse xs accList [x]
    | otherwise = undefined
parse (x:xs) accList accElem
    | isUpper x = parse xs (accList ++ [parseElem accElem]) [x]
    | isLower x = parse xs (accList ++ [parseElem (accElem++[x])]) []
    | isDigit x =  if (isDigit (last accElem)) then parse xs accList (accElem ++ [x])
                                              else parse xs (accList ++ [parseElem accElem]) [x]
    | x `elem` ['(', '[', '{'] = parse xs (accList  ++ [BracketOpen]) (accElem ++ [x])
    | x `elem` [')', ']', '}'] = parse xs (accList ++ [parseElem accElem, BracketClose] ) []
    | otherwise = parse xs accList accElem


Хорошая статья про комбинаторные парсеры:
http://dev.stephendiehl.com/fun/002_parsers.html

Хороший разбор скобок(может пригодиться):
https://stackoverflow.com/questions/...sis-in-haskell
1
zeroalef
-13 / 11 / 1
Регистрация: 29.03.2019
Сообщений: 64
22.04.2019, 15:43  [ТС] 7
Цитата Сообщение от loothood Посмотреть сообщение
Если возникнут вопросы, спрашивайте.
Я осваиваю язык. Теоретически я понимаю примеры оттуда, но практически пока не готов использовать этот крейт. Вот нашел у китайцев идею ”K4[ON(SO3)2]2” =>K4[ONSO3SO3]2” =>K4+ONSO3SO3+ONSO3SO3”=KKKK+…... Все еще сложнее чем я хочу сделать.
0
loothood
88 / 70 / 11
Регистрация: 07.06.2015
Сообщений: 119
Записей в блоге: 12
22.04.2019, 15:50 8
Цитата Сообщение от zeroalef Посмотреть сообщение
Я осваиваю язык. Теоретически я понимаю примеры оттуда, но практически пока не готов использовать этот крейт.
В любом случае, вы можете начать. Всегда подскажем.
Я не понял принципов вашего парсинга. Не понимаю как в вашем примере строка "K4[ON(SO3)2]2" превратилась в [("K", 4), ("O", 14),("N", 2),("S", 4)]
откуда у О 14? почем у S 4, а не 3?
Напишите что-либо. При первых проблемах спрашивайте.
0
zeroalef
-13 / 11 / 1
Регистрация: 29.03.2019
Сообщений: 64
22.04.2019, 16:18  [ТС] 9
Цитата Сообщение от loothood Посмотреть сообщение
Я не понял принципов вашего парсинга.
Посимвольный разбор. Без регулярных выражений и т.п. Сначала пробуем споймать один вид токена, если удачно парсим дальше, если нет -- другой вид токена и т.д. если скобка -- рекурсивно разбираем выражение до закрытой скобки, ловим числовой токен, умножаем на него результат, парсим дальше.
Цитата Сообщение от loothood Посмотреть сообщение
Не понимаю как в вашем примере строка "K4[ON(SO3)2]2" превратилась в [("K", 4), ("O", 14),("N", 2),("S", 4)]
откуда у О 14? почем у S 4, а не 3?
Скобки смотрите внимательней. (O + O*3*2)*2 = O14, S*2*2 = S4
0
loothood
88 / 70 / 11
Регистрация: 07.06.2015
Сообщений: 119
Записей в блоге: 12
22.04.2019, 19:42 10
Цитата Сообщение от zeroalef Посмотреть сообщение
Скобки смотрите внимательней. (O + O*3*2)*2 = O14, S*2*2 = S4
Я понял вашу задачу. Это довольно сложный парсинг. И я был не прав, nom не подойдет. Вам лучше всего подойдет pest.
У меня довольно загруженная неделя, так что написать за вас я не смогу. Даже примерчик накидать. Но если вдруг будут проблемы, обращайтесь. С радостью покажу в какую сторону копать.
1
zeroalef
-13 / 11 / 1
Регистрация: 29.03.2019
Сообщений: 64
22.04.2019, 20:33  [ТС] 11
loothood, спасибо, но не подойдет. Я буду эту кату скидывать на codewars. Там не будет возможности задать pest файл с описанием грамматики.
0
loothood
88 / 70 / 11
Регистрация: 07.06.2015
Сообщений: 119
Записей в блоге: 12
22.04.2019, 21:04 12
Цитата Сообщение от zeroalef Посмотреть сообщение
Я буду эту кату скидывать на codewars. Там не будет возможности задать pest файл с описанием грамматики.
А так вы на кодварс. Можно ссыль на кату? То-то задача показалась мне знакомой. Я ее решал по-моему когда-то давно.

Добавлено через 16 минут
нашел кату
К сожалению, на rust я ее не решал. Так бы скинул готовый код

Добавлено через 7 минут
Цитата Сообщение от zeroalef Посмотреть сообщение
Посимвольный разбор. Без регулярных выражений и т.п. Сначала пробуем споймать один вид токена, если удачно парсим дальше, если нет -- другой вид токена и т.д. если скобка -- рекурсивно разбираем выражение до закрытой скобки, ловим числовой токен, умножаем на него результат, парсим дальше.
сразу предостерегу - это не правильный подход для решения такой задачи.
у вас не получится решить ее таким образом на rust.
лучше использовать регекспы.
Ну и функциональщина просто создана для таких задач. Потому побольше всяких flatten, iter, group_by, map и тд
2
XRuZzz
Антикодер
1614 / 775 / 44
Регистрация: 15.09.2012
Сообщений: 2,883
23.04.2019, 01:41 13
Я конечно написал код для разбора формулы в список и дерево токенов, но код по прежнему очень сырой, не знаю чему можно научиться по такому коду. И поставленную задачу я до конца не решил.
Может на codewars предполагается разбор сразу в список кортежей?
Я специально не использовал комбинаторные парсеры, но думаю с ними код был бы значительно выразительнее.

Кликните здесь для просмотра всего текста
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import Data.Char (isUpper, isLower, isLetter, isDigit)
import Data.List (elem, null)
import Debug.Trace (trace)
 
data Atom = EmptyAtom | H | He | Li | Be | B | C | N | O | F | Ne | Na | Mg | Al | Si | P | S | Cl | Ar | K
  deriving (Enum, Eq, Ord, Read, Show)
 
data Token = Atom1 Atom | Number1 Int | Bracket Char
  deriving (Eq, Read, Show)
 
brackets = ['(', '[', '{', ')', ']', '}']
 
parseElem :: String -> Token
parseElem xxs@(x:xs)
    | isUpper x = Atom1 (read xxs :: Atom)
    | x `elem` brackets = Bracket x
    | isDigit x = Number1 (read xxs :: Int)
    | otherwise = undefined
 
-- Разбор токенов в список
parseToList :: String ->[Token] -> String -> [Token]
parseToList [] accList [] = accList
parseToList [] accList accElem = accList ++ [parseElem accElem]
parseToList (x:xs) accList []
    | isUpper x = parseToList xs accList [x]
    | x `elem` brackets = parseToList xs (accList ++ [Bracket x]) []
    | isDigit x = parseToList xs accList [x]
    | otherwise = undefined
parseToList (x:xs) accList accElem
    | isUpper x = parseToList xs (accList ++ [parseElem accElem]) [x]
    | isLower x = parseToList xs (accList ++ [parseElem (accElem++[x])]) []
    | isDigit x =  if (isDigit (last accElem)) then parseToList xs accList (accElem ++ [x])
                                              else parseToList xs (accList ++ [parseElem accElem]) [x]
    | x `elem` brackets = parseToList xs (accList  ++ [parseElem accElem, Bracket x]) []
    | otherwise = parseToList xs accList accElem
 
 
-- Второе решение - разбор формулы в дерево
data Node = A' Atom | AA' Atom Int | N' [Node] | NA' [Node] Int 
  deriving (Eq, Read, Show)
 
data CommonNode = EmptyNode1 | IsNode Node
  deriving (Eq, Read, Show)
 
data BrackType = BrackFigure | BrackQuad | BrackCycle
  deriving (Eq, Read, Show)
 
parseAccElemToNode :: String -> String -> [Node]
parseAccElemToNode [x] []
  | isUpper x = [A' (read [x] :: Atom)]
  | otherwise = undefined
parseAccElemToNode [x] [acc]
  | isUpper x && isUpper acc = [A' (read [acc] :: Atom), A' (read [x] :: Atom)]
  | isLower x && isUpper acc = [A' (read (acc: [x]) :: Atom)]
  | isDigit x && isUpper acc = [AA' (read [acc] :: Atom) (read [x] :: Int)]
  | otherwise = undefined
parseAccElemToNode (x:xs) []
  | isUpper x = parseAccElemToNode xs [x]
  | otherwise = undefined
parseAccElemToNode (x:xs) acc
  | isUpper x = parseAccElemToNode acc [] ++ parseAccElemToNode xs [x]
  | otherwise = undefined
 
-- Разбор токенов в дерево
parseToTree :: String -> Node -> String -> [BrackType]-> Node
parseToTree [] accTree [] [] = accTree
parseToTree [] (A' x) accElem accBr = N' $ (A' x):parseAccElemToNode accElem []
parseToTree [] xy@(AA' x y) accElem accBr = N' $ xy:parseAccElemToNode accElem []
parseToTree [] xxs@(N' xs) accElem@(y:ys) []
  | y == '(' = let
                   exp1 = takeWhile (/= ')') ys
                   zs = tail (dropWhile (/= ')') ys)
                in
                    if null zs then N' $ xs ++ parseAccElemToNode accElem []
                              else N' $ xs ++ [NA' (parseAccElemToNode exp1 []) (read zs :: Int)]
  | y == '[' = let
                   exp1 = takeWhile (/= ']') ys
                   zs = tail (dropWhile (/= ']') ys)
                in
                   if null zs then N' $ xs ++ [parseToTree exp1 (N' []) [] []]
                                 else N' $ xs ++ [NA' [parseToTree exp1 (N' []) [] []] (read zs :: Int)]
parseToTree [] xxs@(N' xs) accElem accBr = N' $ xs ++ parseAccElemToNode accElem []
parseToTree [] xxs@(NA' xs n) accElem accBr = NA' (xs ++ parseAccElemToNode accElem []) n
parseToTree (x:xs) y@(A' z) [] accBr
  | isUpper x = parseToTree xs (N' [y]) [x] accBr
  | otherwise = undefined
parseToTree (x:xs) yz@(AA' y z) [] accBr = undefined
parseToTree (x:xs) yys@(N' ys) [] accBr
  | isUpper x = parseToTree xs yys [x] accBr
  | isLower x = parseToTree xs yys [x] accBr
  | x == '(' = parseToTree xs yys [x] (BrackCycle:accBr)
  | otherwise = undefined
parseToTree (x:xs) xxs@(NA' ys n) [] accBr = undefined
parseToTree (x:xs) (A' y) accElem accBr = undefined
parseToTree (x:xs) yz@(AA' y z) accElem accBr = undefined
parseToTree (x:xs) yys@(N' ys) accElem []
  | isUpper x = parseToTree xs (N' (ys ++ parseAccElemToNode accElem [])) [x] []
  | isLower x = parseToTree xs yys (accElem ++ [x]) []
  | isDigit x = parseToTree xs yys (accElem ++ [x]) []
  | x == '(' = parseToTree xs (N' (ys ++ parseAccElemToNode accElem [])) [x] (BrackCycle:[])
  | x == '[' = parseToTree xs (N' (ys ++ parseAccElemToNode accElem [])) [x] (BrackQuad:[])
  | otherwise = undefined
parseToTree (x:xs) yys@(N' ys) accElem accBr@(z:zs)
  | isUpper x = parseToTree xs yys (accElem ++ [x]) accBr
  | isLower x = parseToTree xs yys (accElem ++ [x]) accBr
  | isDigit x = parseToTree xs yys (accElem ++ [x]) accBr
  | x == '(' = parseToTree xs (N' ys) (accElem ++ [x]) (BrackCycle:accBr)
  | x == ')' = parseToTree xs (N' ys) (accElem ++ [x]) (if z == BrackCycle then zs else undefined)
  | x == ']' = parseToTree xs (N' ys) (accElem ++ [x]) (if z == BrackQuad then zs else undefined)
  | otherwise = undefined
parseToTree (x:xs) xxs@(NA' ys n) accElem accBr = undefined


Пример вывода:
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Для списка
ghci> parseToList "H2O" [] ""
[Atom1 H,Number1 2,Atom1 O]
ghci> parseToList "Mg(OH)2" [] ""
[Atom1 Mg,Bracket '(',Atom1 O,Atom1 H,Bracket ')',Number1 2]
parseToList "K4[ON(SO3)2]2" [] ""
[Atom1 K,Number1 4,Bracket '[',Atom1 O,Atom1 N,Bracket '(',Atom1 S,Atom1 O,Number1 3,Bracket ')',Number1 2,Bracket ']',Number1 2]
 
# Для дерева
ghci> parseToTree "H2O" (N' []) [] []
N' [AA' H 2,A' O]
ghci> parseToTree "Mg(OH)2" (N' []) [] []
N' [A' Mg,NA' [A' O,A' H] 2]
ghci> parseToTree "K4[ON(SO3)2]2" (N' []) [] []
N' [AA' K 4,NA' [N' [A' O,A' N,NA' [A' S,AA' O 3] 2]] 2]
В принципе, элементы дерева сложить не сложно. Думаю, что разбор формулы в дерево сделать сложнее.
Но если вдруг дорешаю, то выложу решение на codewars.
2
Curry
2952 / 2021 / 252
Регистрация: 01.06.2013
Сообщений: 4,409
Записей в блоге: 8
24.04.2019, 00:52 14
Без контроля ошибок. То есть работает только если химическая формула правильная
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import Data.Char (isUpper, isLower)
import Data.List (groupBy,sort)
import Data.Function (on)
import Numeric (readDec)
 
type Dictionary = [(String,Int)]
 
addD :: Dictionary -> Dictionary -> Dictionary
addD d1 d2 = map (\g -> (fst $ head g, sum $ map snd g)) $ groupBy ((==) `on` fst) $ sort $ d1 ++ d2
 
mulD :: Int -> Dictionary -> Dictionary
mulD n = map ((*n) <$>) 
 
job :: String -> Dictionary
job = fst . go
    where go (a:b:xs) | isUpper a && isLower b = mk1 (a:[b]) xs
          go (a:xs) | isUpper a = mk1 [a] xs 
                    | a `elem` "{[(" = let (a',r') = go xs
                                       in mk a' r'
                    | otherwise = ([],xs)
          go _ = ([],"")
          mk1 a = mk [(a,1)]
          mk  a xs = let (a',r') = case readDec xs of 
                                    [(n,r)] -> (mulD n a,r)
                                    _ -> (a,xs)
                         (a'',r'') = go r'
                     in  (addD a' a'',r'')

Не по теме:

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

1
zeroalef
-13 / 11 / 1
Регистрация: 29.03.2019
Сообщений: 64
24.04.2019, 23:03  [ТС] 15
Цитата Сообщение от Curry Посмотреть сообщение
А вообще то, просить помощи для решения задач на содерварсах и им подобным нехорошо.
В данном случае не совсем уместное замечание. Я прошу помощи в освоении языка. Языковых техник, с которыми очень хорошо знакомы те, кто использует haskell.
Цитата Сообщение от zeroalef Посмотреть сообщение
Скажем, python/c++ не вызвали бы у меня такой зуд
0
Curry
2952 / 2021 / 252
Регистрация: 01.06.2013
Сообщений: 4,409
Записей в блоге: 8
24.04.2019, 23:52 16

Не по теме:

Цитата Сообщение от zeroalef Посмотреть сообщение
В данном случае не совсем уместное замечание. Я прошу помощи в освоении языка.
Нет. Вы просили
Цитата Сообщение от zeroalef Посмотреть сообщение
Так что прошу помочь мне решить задачу у вас.

В качестве антиоффтопа мой вариант куда добавлена проверка ошибок.
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
job :: String -> Either String Dictionary
job = fmap fst . go ' '
    where go e (a:b:xs) | isUpper a && isLower b = mk1 e (a:[b]) xs
          go e (a:xs) | isUpper a = mk1 e [a] xs 
                      | a `elem` "{[(" = do
                            (a',r') <- go a xs
                            mk e a' r'
                      | (e=='(' && a == ')') ||
                        (e=='[' && a == ']') ||
                        (e=='{' && a == '}') = Right ([],xs)
          go _ [] = Right ([],"")
          go _  _ = Left "illegal formula"
          mk1 e a = mk e [(a,1)]
          mk  e a xs = do
                        let (a',r') = case readDec xs of 
                                        [(n,r)] -> (mulD n a,r)
                                        _ -> (a,xs)
                        (a'',r'') <- go e r'
                        return (addD a' a'',r'')
А кату эту я, оказывается, уже решал. Хвала склерозу, решил снова.
2
zeroalef
25.04.2019, 00:15  [ТС]
  #17

Не по теме:

Цитата Сообщение от Curry Посмотреть сообщение
Нет. Вы просили
Если Вам полегчает, я решил оставить этот вопрос до той поры пока мой навык использования языка rust не станет лучше сегодняшнего. Благодарю за продуктивные советы менторской тональности.

0
Catstail
Модератор
24603 / 12511 / 2284
Регистрация: 12.02.2012
Сообщений: 20,328
25.04.2019, 17:56 18
Как вариант. Решение на элементарных структурах:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import Data.List
 
isPar :: Char -> Bool
isPar x = x `elem` "()[]"
 
isDig :: Char -> Bool
isDig x = x `elem` "0123456789"
 
isCap :: Char -> Bool
isCap x = x `elem` ['A','B'..'Z']
 
isLow :: Char -> Bool
isLow x = x `elem` ['a','b'..'z']
 
isAtom :: String -> Bool
isAtom x = isCap $ head x
 
-- Предварительный парсер
 
parse :: String -> String -> [String]
parse "" acc = if null acc then [] else [acc]
parse (x:xs) acc | isPar x = if null acc then [x] : (parse xs "") else acc : (parse xs [x])
                 | isCap x = if null acc then parse xs [x] else acc : (parse xs [x])
                 | isLow x = if null acc then error "#1" else parse xs (acc++[x])
                 | isDig x = if null acc then error "#2" 
                                         else if (isDig (head acc)) then parse xs (acc++[x])
                                                                    else acc : (parse xs [x])                                         
                 | otherwise = parse xs (acc++[x])
 
-- "размножение" строки
   
smult :: String -> Int -> [String]
smult s 0 = []
smult s n = s : (smult s (n-1))
 
-- дать вершину стека или 1
 
u :: [Int] -> Int
u [] = 1
u (x:_)=x
 
-- Уничтожитель скобок
   
h :: [String] -> Int -> [Int] -> [String] 
h [] _ _ = []
h (x:xs) acc stack | isDig (head x) = h xs (read x) stack 
                   | x==")" || x=="]" = if null stack then h xs 1 (acc:stack) else h xs 1 ((acc*(u stack)):stack)
                   | x=="(" || x=="[" = h xs 1 (tail stack)
                   | otherwise = (smult x (acc*(u stack))) ++ (h xs 1 stack)  
 
-- Окончательное решение
                   
task :: String -> [(String,Int)]
task x = map (\z -> (head z,length z)) $ group $ sort $ h (reverse (parse x "")) 1 [] 
 
-- Проверка:
 
*Main Data.List> task "Al2(PO4)3"
[("Al",2),("O",12),("P",3)]
it :: [(String, Int)]
*Main Data.List> task "H2SO4"
[("H",2),("O",4),("S",1)]
it :: [(String, Int)]
*Main Data.List> task "K4[Fe(CN)6]"
[("C",6),("Fe",1),("K",4),("N",6)]
it :: [(String, Int)]
*Main Data.List> task "[Co(NH3)6]Cl2"
[("Cl",2),("Co",1),("H",18),("N",6)]
it :: [(String, Int)]
1
XRuZzz
Антикодер
1614 / 775 / 44
Регистрация: 15.09.2012
Сообщений: 2,883
06.05.2019, 16:59 19
Улучшил свой код разбора строки в дерево, но ещё не доконца... (в коде много лишнего)
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import Data.Char (isUpper, isLower, isLetter, isDigit)
import Data.List as L (elem, null)
import Debug.Trace (trace)
 
data Atom = EmptyAtom
          | H     | He
          | Li | Be | B | C | N | O | F | Ne
          | Na | Mg | Al | Si | P | S | Cl | Ar
          | K
  deriving (Enum, Eq, Ord, Read, Show)
 
data Node a = A' a | AA' a Int | N' [Node a] | NA' [Node a] Int 
  deriving (Eq, Read, Show)
 
parseAccElemToNodes :: String -> String -> [Node Atom]
parseAccElemToNodes [] [] = []
parseAccElemToNodes [x] []
  | isUpper x = [A' (read [x] :: Atom)]
  | otherwise = undefined
parseAccElemToNodes [x] [acc]
  | isUpper x && isUpper acc = [A' (read [acc] :: Atom), A' (read [x] :: Atom)]
  | isLower x && isUpper acc = [A' (read (acc: [x]) :: Atom)]
  | isDigit x && isUpper acc = [AA' (read [acc] :: Atom) (read [x] :: Int)]
  | otherwise = undefined
parseAccElemToNodes (x:xs) []
  | isUpper x = parseAccElemToNodes xs [x]
  | otherwise = undefined
parseAccElemToNodes (x:xs) acc
  | isUpper x =
      parseAccElemToNodes acc [] ++ parseAccElemToNodes xs [x]
  | isLower x = parseAccElemToNodes xs (acc++[x])
  | isDigit x =  parseAccElemToNodes xs (acc++[x])
  | otherwise = undefined
 
getPair '[' = ']'
getPair '(' = ')'
getPair '{' = '}'
 
parseToNodes :: String -> String -> String -> [Node Atom]
parseToNodes [] [] [] = []
parseToNodes [] [] accBr = []
parseToNodes [] acc [] = parseToNodes acc [] []
parseToNodes [] acc@(x:xs) accBr@(y:ys)
  | x `elem` ['{', '[', '('] = [NA' (parseToNodes acc [] []) 1]
parseToNodes [x] [] accBr
  | isUpper x = [A' (read [x] :: Atom)]
  | otherwise = undefined
parseToNodes [x] [acc] accBr
  | isUpper x && isUpper acc = [A' (read [acc] :: Atom), A' (read [x] :: Atom)]
  | isLower x && isUpper acc = [A' (read (acc: [x]) :: Atom)]
  | isDigit x && isUpper acc = [AA' (read [acc] :: Atom) (read [x] :: Int)]
  | otherwise = undefined
parseToNodes (x:xs) [] []
  | isUpper x = parseToNodes xs [x] [] 
  | x `elem` ['{', '[', '('] = parseToNodes xs [x] [getPair x] 
  | otherwise = undefined
parseToNodes (x:xs) [] accBr
  | isUpper x = parseToNodes xs [x] accBr
  | x `elem` ['{', '[', '('] = parseToNodes xs [] ((getPair x):accBr)
  | otherwise = undefined
parseToNodes (x:xs) acc []
  | isUpper x = parseToNodes acc [] [] ++ parseToNodes xs [x] []
  | isLower x || isDigit x = parseToNodes xs (acc ++ [x]) []
  | x `elem` ['{', '[', '('] = parseToNodes acc [] [] ++ parseToNodes xs [] [getPair x]
  | otherwise = undefined
parseToNodes (x:xs) acc@(y:ys) [z]
  | isUpper x || isDigit x = parseToNodes xs (acc ++ [x]) [z]
  | x == z = let
        ds = takeWhile isDigit xs
        tas = dropWhile isDigit xs
        newAccBufs = parseToNodes acc [] []
             in [(if ds == [] then N' newAccBufs else NA' newAccBufs (read ds :: Int))] ++ parseToNodes tas [] []
  | x `elem` ['{', '[', '('] = parseToNodes xs (acc++[x]) ([getPair x,z])
  | otherwise = undefined
parseToNodes (x:xs) acc@(y:ys) accBr@(z:zs)
  | isUpper x || isLower x || isDigit x = parseToNodes xs (acc ++ [x]) accBr
  | x `elem` ['{', '[', '('] = parseToNodes xs (acc ++ [x]) ((getPair x):accBr)
  | x == z = parseToNodes xs (acc ++ [x]) zs
  | otherwise = undefined

> parseToNodes "H" [] []
[A' H]
> parseToNodes "H2" [] []
[AA' H 2]
> parseToNodes "H2O" [] []
[AA' H 2,A' O]
> parseToNodes "K4[ON(SO3)2]2" [] []
[AA' K 4,NA' [A' O,A' N,NA' [A' S,AA' O 3] 2] 2]
4
loothood
88 / 70 / 11
Регистрация: 07.06.2015
Сообщений: 119
Записей в блоге: 12
07.05.2019, 12:08 20
Так и не дошли руки до этой задачи, но я списался с другом, с которым на кодварс познакомился, он кинул решение этой задачи на rust если интересно.
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#[derive(Debug)]
pub struct ParseError {}
 
#[macro_use]
extern crate lazy_static;
extern crate regex;
use regex::Regex;
extern crate itertools;
use itertools::{unfold, Itertools};
 
pub fn parse_molecule(s: &str) -> Result<Vec<(String, usize)>, ParseError> {
    Ok(unfold(vec![(s, 1)], |stack| {
        let (s, count) = stack.pop()?;
        Some(if s.is_empty() {
            None
        } else {
            lazy_static! {
                static ref RE: Regex = Regex::new(
                    r"^(H|O|Mg|K|N|S|Co|Cu|C|Fe|Be|B|Mo|Pd|P|As|\(.*?\)|\[.*?\]|\{.*?\})(\d*)"
                )
                .unwrap();
            }
            RE.captures(s).map_or(Some(Err(ParseError {})), |captures| {
                stack.push((&s[captures[0].len()..], count));
                let capture1 = captures.get(1).unwrap().as_str();
                let count = captures[2].parse::<usize>().unwrap_or(1) * count;
                match &capture1[0..1] {
                    "(" | "[" | "{" => {
                        stack.push((&capture1[1..capture1.len() - 1], count));
                        None
                    }
                    _ => Some(Ok((capture1, count))),
                }
            })
        })
    })
        .flatten()
        .collect::<Result<Vec<(&str, usize)>, ParseError>>()?
        .iter()
        .sorted_by_key(|(s, _)| s)
        .group_by(|(s, _)| s)
        .into_iter()
        .map(|(&s, group)| (String::from(s), group.map(|(_, count)| count).sum()))
        .collect())
}
3
07.05.2019, 12:08
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru