Quylthulg to język autorstwa Chrisa Presseya, który próbuje rozwiązać problem notacji infix za pomocą tak zwanej panfix :
podobnie jak postfix, panfix nie wymaga wdrożenia tajemnych elementów, takich jak nawiasy, aby zastąpić domyślny priorytet operatora. Jednocześnie panfix pozwala na określenie terminów w tej samej kolejności i sposobie, co infix, co jest niewątpliwie naturalnym i intuicyjnym zapisem dla tych, którzy się przyzwyczaili.
Jak uzyskać wygodę notowania infix wraz z jednoznacznością przedrostka lub postfiksa? Oczywiście użyj wszystkich trzech!
=y=+*3*x*+1+=
Bardziej formalnie, bądźmy +
operatorem a
i b
wyrażeniami. Następnie (a+b)
jest poprawnym (nawiasowanym) wyrażeniem infiksowym, reprezentacja tego wyrażenia w panoramie to +a+b+
, gdzie zestawienie reprezentuje konkatenację.
Twoim celem jest pobranie ciągu panfix i przekonwertowanie go na w pełni nawiasową infix:
(y=((3*x)+1))
Dla uproszczenia wprowadzimy następujące zmiany:
- Operatory mogą składać się tylko z dwóch unikalnych postaci (możesz wybrać dowolną, ale tutaj użyję
*
i+
). - Jest tylko jeden literał, który składa się z innej wyraźnej postaci (możesz wybrać dowolną, ale tutaj użyję
_
). - Dane wejściowe będą poprawnie sformułowanym wyrażeniem panoramicznym.
Dla złożoności wprowadzimy następującą zmianę:
- Operatory mogą składać się z dowolnej dodatniej liczby znaków, a nie tylko jednej.
To sprawia, że wyzwanie jest trudniejsze, ponieważ niekoniecznie można określić, w jaki sposób dany podciąg znaków operatora jest dzielony na partycje, nie patrząc na resztę ciągu.
Oto referencyjna implementacja wyzwania, dzięki uprzejmości @ user202729.
Przypadki testowe
format: input -> output
+*+_*+_*+++_+*+_*+_*+++ -> ((_*+_)+(_+(_*+_)))
**++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -> ((((_+_)+_)*++*+***_)*(_*(_*_)))
***_**_***_* -> ((_**_)*_)
+_+_+ -> (_+_)
*+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -> (_*+*+++**+***+++++_)
*++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -> (((_*_)+*+(_++****+_))*+++_)
+**+_*+_*+*_*+*_*+*_+*_+**+ -> (((_*+_)*_)+(_*(_+*_)))
+**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -> (((_+++++_)*_)+*(_+(_+++++_)))
+*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -> (((_+*+_)*_)+(_*(_+*+_)))
**_**_**_*_****_* -> ((_*(_*(_*_)))*_)
Użyłem tego programu, aby wygenerować ciągi znaków poprawki dla tego wyzwania (konwersja do panfixu była trywialna, ale cofanie nie jest).
**_**_**_*_****_*
. Wszystkie odpowiedzi, które przetestowałem, zawiodły.(_ + _)
?Odpowiedzi:
Prolog (SWI) ,
194163 bajtówZaoszczędziłem aż 31 bajtów, używając tej wskazówki od 0 ' !
Operator
^
bierze za swój lewy argument ciąg zawierający wyrażenie panfix i ustawia swój prawy argument na ciąg zawierający odpowiednie wyrażenie w nawiasach. Używax
jako dosłownego zamiast_
.Wypróbuj online!
Wyjaśnienie
Ponieważ Prolog jest językiem deklaratywnym, musimy jedynie opisać relację między poprawką a wyrażeniem w nawiasach.
W objaśnieniu użyto tej nieco niestosowanej wersji:
Naszą główną produkcją jest
parenthesize
przyjmowanie wyrażenia panfixX
jako łańcucha i wysyłanie odpowiedniego wyrażenia nawiasowegoP
w postaci łańcucha. Służystring_chars
do konwersji ciągu wejściowego na listę znaków, a następnie po prostu przekazuje go doexpr
.expr
pobiera listę znakówL
, analizuje pierwsze wyrażenie panfix, w którym się znajdujeL
, i wysyła nawiasowy ekwiwalentX
oraz resztę listy znakówR
. Istnieją dwa możliwe rodzaje wyrażeń:L
jestx
, to wyrażenie jest,x
a reszta to wszystko pox
.O
(patrzoper
poniżej); przeanalizować wyrażenieY
;O
ponownie przeanalizuj ; przeanalizuj inne wyrażenieZ
; i przeanalizujO
po raz trzeci. Reszta to wszystko po trzeciej instancjiO
. Wyrażenie jest wynikiem łączeniaY
,O
iZ
, otoczone nawiasami, na sznurku.oper
pobiera listę znaków, w której znajduje się pierwszy znak,C
a resztaT
; analizuje operator (tj. ciąg jednego lub więcej znaków operatora) i wysyła operatoraO
oraz pozostałą część listy znakówR
. Aby utworzyć operator, znakC
musi być czymś innym niżx
; teżP
musi być analizowalnyT
, z resztąR
; w tym przypadkuO
jest połączeniemC
iP
; lub,O
jest pojedynczym znakiemC
; w tym przypadkuR
jest sprawiedliwyT
.Sprawdzony przykład
Weźmy na
+*+x+x++*x+*
przykład dane wejściowe .+*+x+x++*x+*
. To się nie zaczynax
, więc parsujemy operatora od samego początku.oper
przeanalizuje jak największego operatora, więc próbujemy+*+
.x+x++*x+*
. To musi byćx
.+*+
, z+x++*x+*
. Jednak to się nie udaje .+*
zamiast tego próbujemy parsować operatora .+x+x++*x+*
. To się nie zaczynax
, więc musimy przeanalizować operatora.+
.x+x++*x+*
. To musi byćx
.+
ponownie przeanalizuj z+x++*x+*
.x++*x+*
. To musi byćx
.+
ponownie od++*x+*
.(x+x)
.+*
ponownie analizujemy operatora+*x+*
.x+*
. To musi byćx
.+*
ponownie od+*
.((x+x)+*x)
.Ponieważ nie ma już więcej znaków, pomyślnie przetłumaczyliśmy wyrażenie.
źródło
Perl,
7860585750 bajtówObejmuje
+1
dlap
Zastosowań
1
dla+
i2
na*
(lub w zasadzie wszystkie prace cyfrowe dla każdego operatora)Dla wygodnego testowania w porównaniu z podanymi przykładami możesz użyć tego, który wykonuje dla ciebie tłumaczenia i usuwanie miejsca:
źródło
Czysty ,
200192189 bajtówWypróbuj online!
Definiuje funkcję
f
, przyjmowanieString
i zwracanie singletonu[String]
z wynikiem w środku.Kilka fajnych rzeczy:
_
źródło
Retina 0.8.2 , 138 bajtów
Wypróbuj online! Link zawiera szybsze przypadki testowe. Objaśnienie: Mechanizm wyrażeń regularnych używa śledzenia wstecznego, aby podzielić ciąg na tokeny, które są następnie wypychane lub wyskakiwane z
i
grupy równoważącej. Zawsze uruchamiany jest przynajmniej jeden operator wypychany na początku przed pierwszą zmienną. Po zmiennej pojawia się co najmniej jeden operator, w którym to momencie operator wypychany lub inna zmienna jest legalna. Operatorzy są wypychani do grupy w dwóch egzemplarzach, aby można je było poprawnie pop-up. Przykład:Niestety nie pomaga nam to uchwycić wyników w celu ich uzupełnienia, więc operator zewnętrzny jest dopasowywany ręcznie. Nawiasy są dodawane na zewnątrz, więc pierwszy etap otacza całe wyrażenie w nawiasy, a ostatni etap usuwa je teraz, gdy zostały przeniesione do zmiennych.
źródło
**_**_**_*_****_*
.Haskell ,
167166 bajtówWypróbuj online!Przykładowe użycie:
head.e "**_**_**_*_****_*"
daje((_*(_*(_*_)))*_)
. Wszystkie znaki oprócz_
interpretowane są jako operatory, co_
samo w sobie oznacza identyfikator.źródło
Python 3, 226 bajtów
Definiuje anonimową funkcję o nazwie
R
.Wypróbuj online!
źródło
_*+
; były to tylko te użyte w przykładzie. Możesz to wykorzystać do gry w wyrażenia regularne (np.\d
Zamiast[*+]
).