Kiedy zobaczyłem tytuł tego zamkniętego pytania , pomyślałem, że to wygląda na ciekawe wyzwanie w golfa. Pozwólcie, że przedstawię to w ten sposób:

Wyzwanie:

Napisz program, wyrażenie lub podprogram, który, biorąc pod uwagę wyrażenie arytmetyczne w notacji infiksowej , podobnie 1 + 2, wyprowadza to samo wyrażenie w notacji postfiksowej , tj 1 2 +.

(Uwaga: podobne wyzwanie zostało opublikowane wcześniej w styczniu. Wydaje mi się jednak, że dwa zadania są wystarczająco różne w szczegółach, aby uzasadnić to oddzielne wyzwanie. Zwróciłem też uwagę na inny wątek po wpisaniu wszystkiego poniżej i wolałbym nie tylko wyrzucaj to wszystko).

Wkład:

Sygnał wejściowy składa się z ważnym Infix wyrażenia arytmetycznego obejmującej liczb (nieujemne liczby całkowite reprezentowane sekwencji jednego lub więcej cyfr dziesiętnych), zrównoważonego nawiasach wskazuje zgrupowanego podwyrażenie i cztery binarne wrostek operatorów + , -, *i /. Każde z nich może być oddzielone (a całe wyrażenie otoczone) dowolną liczbą spacji, które należy zignorować. ¹

Dla tych, którzy lubią gramatyki formalne, oto prosta gramatyka podobna do BNF, która definiuje prawidłowe dane wejściowe. Dla zwięzłości i przejrzystości gramatyka nie obejmuje opcjonalnych spacji, które mogą wystąpić między dowolnymi dwoma znakami (innymi niż cyfry w obrębie liczby):

expression     := number | subexpression | expression operator expression
subexpression  := "(" expression ")"
operator       := "+" | "-" | "*" | "/"
number         := digit | digit number
digit          := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

_{¹ Jedynym przypadkiem, w którym obecność spacji może wpływać na parsowanie, jest rozdzielenie dwóch kolejnych liczb; jednak ponieważ dwie liczby nie oddzielone przez operatora nie mogą wystąpić w prawidłowym wyrażeniu infiksowym, taki przypadek nigdy nie może się zdarzyć przy prawidłowym wprowadzeniu.}

Wydajność:

Wynik powinien być wyrażeniem postfiksowym równoważnym z danymi wejściowymi. Wyrażenie wyjściowy powinien się składać wyłącznie z numerami i operatorów, z jednym znaku spacji pomiędzy każdą parą sąsiadujących ze sobą elementów, z, jak w poniższej gramatyki (który nie obejmuje miejsca) ² :

expression  := number | expression sp expression sp operator
operator    := "+" | "-" | "*" | "/"
number      := digit | digit number
digit       := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
sp          := " "

_{² Ponownie dla uproszczenia, numberprodukcja w tej gramatyce przyjmuje liczby z wiodącymi zerami, nawet jeśli są one zabronione w danych wyjściowych zgodnie z poniższymi regułami.}

Pierwszeństwo operatora:

W przypadku braku nawiasów obowiązują następujące zasady pierwszeństwa:

• Operatorzy *i /mają wyższy priorytet niż +i -.
• Operatorzy *i /mają takie same pierwszeństwo.
• Operatorzy +i -mają takie same pierwszeństwo.
• Wszyscy operatorzy są lewostronni.

Na przykład następujące dwa wyrażenia są równoważne:

1 + 2 / 3 * 4 - 5 + 6 * 7
((1 + ((2 / 3) * 4)) - 5) + (6 * 7)

i oba powinny dać następujące wyniki:

1 2 3 / 4 * + 5 - 6 7 * +

(Są to te same zasady pierwszeństwa, co w języku C i w większości języków z niego wywodzących się. Prawdopodobnie przypominają one zasady, których uczyłeś w szkole podstawowej, z wyjątkiem ewentualnie względnego pierwszeństwa *i /.)

Różne zasady:

• Jeśli podanym rozwiązaniem jest wyrażenie lub podprogram, dane wejściowe należy podać, a dane wyjściowe zwrócić jako pojedynczy ciąg. Jeśli rozwiązaniem jest kompletny program, powinien odczytać wiersz zawierający wyrażenie infix ze standardowego wejścia i wydrukować wiersz zawierający wersję Postfiksa na standardowe wyjście.

• Liczby na wejściu mogą zawierać początkowe zera. Liczby na wyjściu nie mogą mieć wiodących zer (z wyjątkiem liczby 0, która powinna być wyprowadzona jako 0).

• Nie należy oceniać ani optymalizować wyrażenia w żaden sposób. W szczególności nie należy zakładać, że operatory koniecznie spełniają wszelkie tożsamości asocjacyjne, przemienne lub inne algebraiczne. Oznacza to, że nie należy zakładać, że np. Jest 1 + 2równy 2 + 1lub że 1 + (2 + 3)jest równy (1 + 2) + 3.

• Można zakładać, że numery w wejściu nie przekracza 2 ³¹ - 1 = 2147483647.

Reguły te mają na celu zapewnienie, że prawidłowe dane wyjściowe są jednoznacznie zdefiniowane przez dane wejściowe.

Przykłady:

Oto niektóre prawidłowe wyrażenia wejściowe i odpowiadające im dane wyjściowe, przedstawione w formie "input" -> "output":

"1"                  ->  "1"
"1 + 2"              ->  "1 2 +"
" 001  +  02 "       ->  "1 2 +"
"(((((1))) + (2)))"  ->  "1 2 +"
"1+2"                ->  "1 2 +"
"1 + 2 + 3"          ->  "1 2 + 3 +"
"1 + (2 + 3)"        ->  "1 2 3 + +"
"1 + 2 * 3"          ->  "1 2 3 * +"
"1 / 2 * 3"          ->  "1 2 / 3 *"
"0102 + 0000"        ->  "102 0 +"
"0-1+(2-3)*4-5*(6-(7+8)/9+10)" -> "0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -"

(Przynajmniej mam nadzieję , że wszystkie są poprawne; dokonałem konwersji ręcznie, aby błędy mogły się wkraść).

Dla jasności wszystkie poniższe dane wejściowe są nieprawidłowe; nie ma znaczenia, co zrobi twoje rozwiązanie, jeśli je otrzymasz (chociaż oczywiście np. zwrócenie komunikatu o błędzie jest ładniejsze niż, powiedzmy, zużycie nieskończonej ilości pamięci):

""
"x"
"1 2"
"1 + + 2"
"-1"
"3.141592653589793"
"10,000,000,001"
"(1 + 2"
"(1 + 2)) * (3 / (4)"

Narzędzia do muszli - 60 znaków

bc -c|sed -re's/[@iK:Wr]+/ /g;s/[^0-9]/ &/g;s/ +/ /g;s/^ //'

Naprawiono różne problemy, ale stało się to znacznie dłużej :(

C, 250 245 236 193 185 znaków

char*p,b[99];f(char*s){int t=0;for(;*p-32?
*p>47?printf("%d ",strtol(p,&p,10)):*p==40?f(p++),++p:
t&&s[t]%5==2|*p%5-2?printf("%c ",s[t--]):*p>41?s[++t]=*p++:0:++p;);}
main(){f(p=gets(b));}

Oto czytelna wersja niegolfowanego źródła, która wciąż odzwierciedla podstawową logikę. To właściwie dość prosty program. Jedyną prawdziwą pracą, jaką musi zrobić, jest wepchnięcie operatora o niskim asocjatywności na stos, gdy napotka operator o wysokim asocjatywności, a następnie odsunięcie go na „końcu” tego podwyrażenia.

#include <stdio.h>
#include <stdlib.h>

static char buf[256], stack[256];
static char *p = buf;

static char *fix(char *ops)
{
    int sp = 0;

    for ( ; *p && *p != '\n' && *p != ')' ; ++p) {
        if (*p == ' ') {
            continue;
        } else if (*p >= '0') {
            printf("%ld ", strtol(p, &p, 10));
            --p;
        } else if (*p == '(') {
            ++p;
            fix(ops + sp);
        } else {
            while (sp) {
                if ((ops[sp] == '+' || ops[sp] == '-') &&
                        (*p == '*' || *p == '/')) {
                    break;
                } else {
                    printf("%c ", ops[sp--]);
                }
            }
            ops[++sp] = *p;
        }
    }
    while (sp)
        printf("%c ", ops[sp--]);
    return p;
}

int main(void)
{
    fgets(buf, sizeof buf, stdin);
    fix(stack);
    return 0;
}

Bash w / Haskell w / Preprocesor C. sed, 180 195 198 275

echo 'CNumO+O-O*fromInteger=show
CFractionalO/
main=putStr$'$*|sed 's/C\([^O]*\)/instance \1 String where /g
s/O\(.\?\)/a\1b=unwords\[a,b,\"\1\"];/g'|runghc -XFlexibleInstances 2>w

Wreszcie nie jest już dłuższy niż rozwiązanie C. Kluczowa część Haskell jest prawie tak leniwa jak rozwiązanie BC ...

Pobiera dane wejściowe jako parametry wiersza polecenia. Plik wz niektórymi komunikatami ostrzegawczymi ghc zostanie utworzony, jeśli nie spodoba ci się ta zmiana na runghc 2>/dev/null.

Python 2, 290 272 268 250 243 238 bajtów

Teraz w końcu krótszy niż odpowiedź JS!

Jest to pełny program, który wykorzystuje podstawową implementację algorytmu manewrowego . Dane wejściowe są podawane jako ciąg cytowany, a wynik jest drukowany na STDOUT.

import re
O=[];B=[]
for t in re.findall('\d+|\S',input()):exec("O=[t]+O","i=O.index('(');B+=O[:i];O=O[i+1:]","while O and'('<O[0]and(t in'*/')<=(O[0]in'*/'):B+=O.pop(0)\nO=[t]+O","B+=`int(t)`,")[(t>'/')+(t>')')+(t>'(')]
print' '.join(B+O)

Wypróbuj online!

Wyjaśnienie:

Pierwszą rzeczą, którą musimy zrobić, jest konwersja danych wejściowych na tokeny. Robimy to za pomocą znalezienia wszystkich dopasowań wyrażenia regularnego \d+|\S, z grubsza przetłumaczonych na „dowolną grupę cyfr i dowolny znak spacji”. Usuwa to spacje, analizuje sąsiadujące cyfry jako pojedyncze tokeny i oddzielnie analizuje operatory.

W przypadku algorytmu stoczni manewrowej mamy do czynienia z 4 różnymi typami tokenów:

• ( - Lewy nawias
• ) - Właściwy nawias
• +-*/ - operatorzy
• 9876543210 - Literały liczbowe

Na szczęście wszystkie kody ASCII są pogrupowane w pokazanej kolejności, więc możemy użyć wyrażenia (t>'/')+(t>')')+(t>'(')do obliczenia typu tokena. Daje to 3 dla cyfr, 2 dla operatorów, 1 dla prawego nawiasu i 0 dla lewego nawiasu.

Korzystając z tych wartości, indeksujemy do dużej krotki po, execaby uzyskać odpowiedni fragment kodu do wykonania na podstawie typu tokena. Różni się to dla każdego tokena i jest podstawą algorytmu stoczni manewrowej. Używane są dwie listy (jako stosy): O(stos operacji) i B(bufor wyjściowy). Po uruchomieniu wszystkich tokenów pozostałe operatory na Ostosie są łączone z buforem wyjściowym, a wynik jest drukowany.

Prolog (SWI-Prolog) , 113 bajtów

c(Z,Q):-Z=..[A,B,C],c(B,S),c(C,T),concat_atom([S,T,A],' ',Q);term_to_atom(Z,Q).
p(X,Q):-term_to_atom(Z,X),c(Z,Q).

Wypróbuj online!

SWI Prolog ma do tego znacznie lepszy zestaw wbudowanych plików niż GNU Prolog, ale nadal jest nieco powstrzymywany przez gadatliwość składni Prologa.

Wyjaśnienie

term_to_atom, jeśli zostanie uruchomione wstecz, przeanalizuje wyrażenie notacji poprawkowej (przechowywane jako atom) w drzewie analizy (przestrzegając zwykłych reguł pierwszeństwa i usuwając zera i białe znaki). Następnie używamy predykatu pomocnika, caby wykonać rekurencję strukturalną nad drzewem analizy składniowej, przekształcając się w notację postfiksową w pierwszej kolejności.

JavaScript (ES6), 244 bajty

f=(s,o={'+':1,'-':1,'*':2,'/':2},a=[],p='',g=c=>o[l=a.pop()]>=o[c]?g(c,p+=l+' '):a.push(l||'',c))=>(s.match(/[)(+*/-]|\d+/g).map(c=>o[c]?g(c):(c==')'?eval(`for(;(i=a.pop())&&i!='(';)p+=i+' '`):c=='('?a.push(c):p+=+c+' ')),p+a.reverse().join` `)

Przykład:
Call: f('0-1+(2-3)*4-5*(6-(7+8)/9+10)')
Output: 0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -(ze spacją końcową)

Wyjaśnienie:

f=(s,                                                     //Input string
    o={'+':1,'-':1,'*':2,'/':2},                          //Object used to compare precedence between operators
    a=[],                                                 //Array used to stack operators
    p='',                                                 //String used to store the result
    g=c=>                                                 //Function to manage operator stack
        o[l=a.pop()]>=o[c]?                               //  If the last stacked operator has the same or higher precedence
            g(c,p+=l+' '):                                //  Then adds it to the result and call g(c) again
            a.push(l||'',c)                               //  Else restack the last operator and adds the current one, ends the recursion.
)=>                                                       
    (s.match(/[)(+*/-]|\d+/g)                             //Getting all operands and operators
    .map(c=>                                              //for each operands or operators
        o[c]?                                             //If it's an operator defined in the object o
            g(c)                                          //Then manage the stack
            :(c==')'?                                     //Else if it's a closing parenthese
                eval(`                                    //Then
                    for(;(i=a.pop())&&i!='(';)            //  Until it's an opening parenthese
                        p+=i+' '                          //  Adds the last operator to the result
                `)                                        
                :c=='('?                                  //Else if it's an opening parenthese
                    a.push(c)                             //Then push it on the stack
                    :p+=+c+' '                            //Else it's an operand: adds it to the result (+c removes the leading 0s)
        )                                                 
    )                                                     
    ,p+a.reverse().join` `)                               //Adds the last operators on the stack to get the final result

R, 142 bajty

R jest w stanie sam parsować, więc zamiast na nowo wynaleźć koło, po prostu uruchamiamy parser, który generuje notację prefiksu, i używamy funkcji rekurencyjnej, aby przełączyć ją na notację postfiksową.

f=function(x,p=1){
if(p)x=match.call()[[2]]
if((l=length(x))>1){
f(x[[2]],0)
if(l>2)f(x[[3]],0)
if((z=x[[1]])!="(")cat(z,"")
}else cat(x,"")
}

pArgument jest do uregulowania sposobu korzystania z niestandardowym oceny (zmorą programistów R wszędzie), i istnieje kilka dodatkowych ifs tam kontrolować wyprowadzania wsporników (który chcemy uniknąć).

Wkład: (0-1+(2-3)*4-5*(6-(7+8)/9+10))

Wydajność: 0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -

Wkład: (((((1))) + (2)))

Wydajność: 1 2 +

Jako bonus działa z dowolnymi symbolami i dowolnymi predefiniowanymi funkcjami z maksymalnie dwoma argumentami:

Tożsamość Eulera

Wkład: e^(i*pi)-1

Wydajność: e i pi * ^ 1 -

Dywidendy w wysokości 13 od 1 do 100

Wkład: which(1:100 %% 13 == 0)

Wydajność: 1 100 : 13 %% 0 == which

Liniowa regresja masy kurczaka u dziecka w funkcji czasu

Wkład: summary(lm(weight~Time, data=ChickWeight))

Wydajność: weight Time ~ ChickWeight lm summary

Ostatni przykład jest może trochę poza zakresem PO, ale korzysta z notacji postfiksowej, więc ...