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 ai bwyraż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).

Prolog (SWI) , 194 163 bajtów

^{Zaoszczędziłem aż 31 bajtów, używając tej wskazówki od 0 ' !}

[C|T]/O/R:-C\=x,(T/P/R,concat(C,P,O);O=C,R=T).
[x|R]-x-R.
L-X-R:-L/O/A,A-Y-B,B/O/C,C-Z-D,D/O/R,atomics_to_string(['(',Y,O,Z,')'],X).
X^P:-string_chars(X,L),L-P-[].

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żywa xjako 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:

oper([C|T],O,R) :- C\=x, oper(T,P,R), concat(C,P,O).
oper([C|T],C,T).

expr([x|R],x,R).
expr(L,X,R) :- oper(L,O,A), expr(A,Y,B), oper(B,O,C), expr(C,Z,D), oper(D,O,R),
               atomics_to_string(['(',Y,O,Z,')'],X).

parenthesize(X,P) :- string_chars(X,L), expr(L,P,[]).

Naszą główną produkcją jest parenthesizeprzyjmowanie wyrażenia panfix Xjako łańcucha i wysyłanie odpowiedniego wyrażenia nawiasowego Pw postaci łańcucha. Służy string_charsdo konwersji ciągu wejściowego na listę znaków, a następnie po prostu przekazuje go do expr.

exprpobiera listę znaków L, analizuje pierwsze wyrażenie panfix, w którym się znajduje L, i wysyła nawiasowy ekwiwalent Xoraz resztę listy znaków R. Istnieją dwa możliwe rodzaje wyrażeń:

• Jeśli pierwszym znakiem Ljest x, to wyrażenie jest, xa reszta to wszystko po x.
• W przeciwnym razie przeanalizuj operator O(patrz operponiżej); przeanalizować wyrażenie Y; Oponownie przeanalizuj ; przeanalizuj inne wyrażenie Z; i przeanalizuj Opo raz trzeci. Reszta to wszystko po trzeciej instancji O. Wyrażenie jest wynikiem łączenia Y, Oi Z, otoczone nawiasami, na sznurku.

operpobiera listę znaków, w której znajduje się pierwszy znak, Ca reszta T; analizuje operator (tj. ciąg jednego lub więcej znaków operatora) i wysyła operatora Ooraz pozostałą część listy znaków R. Aby utworzyć operator, znak Cmusi być czymś innym niż x; też

• operator Pmusi być analizowalny T, z resztą R; w tym przypadku Ojest połączeniem Ci P; lub,
• Ojest pojedynczym znakiem C; w tym przypadku Rjest sprawiedliwy T.

Sprawdzony przykład

Weźmy na +*+x+x++*x+*przykład dane wejściowe .

• Chcemy przeanalizować wyrażenie z +*+x+x++*x+*. To się nie zaczyna x, więc parsujemy operatora od samego początku.
• operprzeanalizuje jak największego operatora, więc próbujemy +*+.
  • Następnie analizujemy wyrażenie z x+x++*x+*. To musi być x.
  • Teraz próbujemy parsować tego samego operatora +*+, z +x++*x+*. Jednak to się nie udaje .
• Więc cofamy się i +*zamiast tego próbujemy parsować operatora .
  • Analizujemy wyrażenie z +x+x++*x+*. To się nie zaczyna x, więc musimy przeanalizować operatora.
  • Jedyną możliwością jest +.
  • Teraz przeanalizuj podwyrażenie z x+x++*x+*. To musi być x.
  • Teraz +ponownie przeanalizuj z +x++*x+*.
  • Teraz przeanalizuj kolejne podwyrażenie z x++*x+*. To musi być x.
  • Na koniec przeanalizuj +ponownie od ++*x+*.
  • Wyrażenie zostało pomyślnie przeanalizowane. Zwracamy ciąg (x+x).
• Wracając do poprzedniego poziomu rekurencji, +*ponownie analizujemy operatora +*x+*.
• Teraz przeanalizuj kolejne podwyrażenie z x+*. To musi być x.
• Na koniec przeanalizuj +*ponownie od +*.
• Wyrażenie zostało pomyślnie przeanalizowane. Zwracamy ciąg ((x+x)+*x).

Ponieważ nie ma już więcej znaków, pomyślnie przetłumaczyliśmy wyrażenie.

Perl, 78 60 58 57 50 bajtów

Obejmuje +1dlap

Zastosowań 1dla +i 2na *(lub w zasadzie wszystkie prace cyfrowe dla każdego operatora)

perl -pe 's/\b((\d+)((?1)|_)\2((?3))\2)\b/($3 $2 $4)/&&redo' <<< 22_22_22_2_2222_2

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:

perl -pe 'y/+*/12/;s/\b((\d+)((?1)|_)\2((?3))\2)\b/($3 $2 $4)/&&redo;y/ //d;y/12/+*/' <<< "**_**_**_*_****_*"

Czysty , 200 192 189 bajtów

import StdEnv,Text
f"_"=["_"]
f l=["("+a+p+b+")"\\p<-[l%(0,i)\\i<-[0..indexOf"_"l]|endsWith(l%(0,i))l],t<-[tl(init(split p l))],n<-indexList t,a<-f(join p(take n t))&b<-f(join p(drop n t))]

Wypróbuj online!

Definiuje funkcję f, przyjmowanie Stringi zwracanie singletonu [String]z wynikiem w środku.

Kilka fajnych rzeczy:

• Nie używa wyrażenia regularnego
• Działa z dowolnymi znakami dla operatorów oprócz_

Retina 0.8.2 , 138 bajtów

.+
($&)
+`\((\d+)(_|((?<i>(?<i>\d+))|_(?<-i>\k<i>)+)+(?(i)(?!)))\1(_|((?<i>(?<i>\d+))|_(?<-i>\k<i>)+)+(?(i)(?!)))\1\)
(($2)$1($4))
\(_\)
_

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 igrupy 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:

Input           Stack
Push *          * *
Push *++*+***   * * *++*+*** *++*+***
Push +          * * *++*+*** *++*+*** + +
Push +          * * *++*+*** *++*+*** + + + +
Variable _
Pop +           * * *++*+*** *++*+*** + + +
Variable _
Pop +           * * *++*+*** *++*+*** + +
Pop +           * * *++*+*** *++*+*** +
Variable _
Pop +           * * *++*+*** *++*+***
Pop *++*+***    * * *++*+***
Variable _
Pop *++*+***    * *
Pop *           *
Push *          * * *
Variable _
Pop *           * *
Push *          * * * *
Variable _
Pop *           * * *
Variable _
Pop *           * *
Pop *           *
Pop *

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.

Haskell , 167 166 bajtów

head.e
e('_':r)=["_",r]
e(x:r)=[x]%r
e _=[]
o%t@(c:r)|[x,u]<-e t,n<-length o,[y,v]<-e$drop n u,all((==o).take n)[u,v]=['(':x++o++y++")",drop n v]|p<-o++[c]=p%r
o%_=[]

Wypróbuj online!Przykładowe użycie: head.e "**_**_**_*_****_*"daje ((_*(_*(_*_)))*_). Wszystkie znaki oprócz _interpretowane są jako operatory, co _samo w sobie oznacza identyfikator.

Python 3, 226 bajtów

from re import*
P=r'([*+]+)'+r'(\(.+?\)|_)\1'*2;R=lambda i,J=lambda i,o:i[:o]+sub(P,lambda o:'('+o[2]+o[1]+o[3]+')',i[o:],1),s=search:s(P,i)and R([J(i,o)for o in range(len(i))if s(P,J(i,o))or J(i,o)[0]+J(i,o)[-1]=='()'][0])or i

Definiuje anonimową funkcję o nazwie R.

Wypróbuj online!