Als ich den Titel dieser geschlossenen Frage sah , fand ich, dass es sich um eine interessante Code-Golf-Herausforderung handelte. Lassen Sie es mich als solches darstellen:

Herausforderung:

Ein Programm schreiben, Expression oder Unterprogramm , das, ein arithmetischer Ausdruck in gegebenem Infix - Schreibweise , wie 1 + 2gibt den gleichen Ausdruck in Postfix - Schreibweise , dh 1 2 +.

(Hinweis: Eine ähnliche Herausforderung wurde Anfang Januar veröffentlicht. Ich bin jedoch der Meinung, dass die beiden Aufgaben im Detail ausreichend unterschiedlich sind, um diese separate Herausforderung zu rechtfertigen. Außerdem habe ich den anderen Thread erst bemerkt, nachdem ich alles unten eingegeben habe, und ich würde es vorziehen nicht einfach alles wegwerfen.)

Eingang:

Die Eingabe besteht aus einem gültigen Infix arithmetischen Ausdruck , der aus Zahlen (nicht negative ganzen Zahlen als Sequenzen von einem oder mehreren Dezimalziffern dargestellt) ausgeglichen Klammern einen gruppierte Teilausdruck , um anzuzeigen, und die vier Infix binären Operatoren + , -, *und /. Jedes dieser Zeichen kann von einer beliebigen Anzahl von Leerzeichen getrennt (und der gesamte Ausdruck von einem Leerzeichen umgeben) werden, die ignoriert werden sollten. ¹

Für diejenigen, die formale Grammatiken mögen, ist hier eine einfache BNF-ähnliche Grammatik, die gültige Eingaben definiert. Der Kürze und Klarheit halber enthält die Grammatik keine optionalen Leerzeichen, die zwischen zwei beliebigen Token (außer Ziffern innerhalb einer Zahl) auftreten können:

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

_{¹ Der einzige Fall, in dem das Vorhandensein von Leerzeichen die Syntaxanalyse beeinflussen kann, besteht darin, dass zwei aufeinanderfolgende Zahlen voneinander getrennt werden. Da jedoch zwei nicht durch einen Operator getrennte Zahlen in einem gültigen Infix-Ausdruck nicht vorkommen können, kann dieser Fall bei einer gültigen Eingabe niemals auftreten.}

Ausgabe:

Die Ausgabe sollte ein Postfix-Ausdruck sein, der der Eingabe entspricht. Der Ausgang Ausdruck sollte nur aus Zahlen und Operatoren besteht, mit einem einzigen Leerzeichen zwischen jedem Paar von benachbartem Tokens, wie in der folgenden Grammatik (die nicht die Räume umfasst) ² :

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

_{² Wiederum der Einfachheit halber lässt die numberProduktion in dieser Grammatik Zahlen mit führenden Nullen zu, obwohl sie in der Ausgabe nach den folgenden Regeln verboten sind.}

Operator-Rangfolge:

In Abwesenheit von Klammern gelten die folgenden Vorrangregeln:

• Die Operatoren *und /haben eine höhere Priorität als +und -.
• Die Operatoren *und /haben untereinander den gleichen Vorrang.
• Die Operatoren +und -haben untereinander den gleichen Vorrang.
• Alle Operatoren sind linksassoziativ.

Die folgenden zwei Ausdrücke sind beispielsweise äquivalent:

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

und sie sollten beide die folgende Ausgabe ergeben:

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

(Dies sind die gleichen Prioritätsregeln wie in der C-Sprache und in den meisten davon abgeleiteten Sprachen. Sie ähneln wahrscheinlich den Regeln, die Sie in der Grundschule unterrichtet haben, außer möglicherweise der relativen Priorität von *und /.)

Verschiedene Regeln:

• Wenn die angegebene Lösung ein Ausdruck oder eine Unterroutine ist, sollte die Eingabe geliefert und die Ausgabe als einzelne Zeichenfolge zurückgegeben werden. Wenn die Lösung ein vollständiges Programm ist, sollte sie eine Zeile mit dem Infix-Ausdruck von der Standardeingabe lesen und eine Zeile mit der Postfix-Version in der Standardausgabe ausgeben.

• Zahlen in der Eingabe können führende Nullen enthalten. Zahlen in der Ausgabe dürfen keine führenden Nullen haben (mit Ausnahme der Zahl 0, die als ausgegeben werden soll 0).

• Es wird nicht erwartet, dass Sie den Ausdruck in irgendeiner Weise bewerten oder optimieren. Insbesondere sollten Sie nicht davon ausgehen, dass die Operatoren notwendigerweise assoziative, kommutative oder andere algebraische Identitäten erfüllen. Das heißt, Sie sollten nicht davon ausgehen, dass zB 1 + 2gleich 2 + 1oder 1 + (2 + 3)gleich ist (1 + 2) + 3.

• Sie können davon ausgehen, dass die Zahlen in der Eingabe 2 ³¹ - 1 = 2147483647 nicht überschreiten .

Diese Regeln sollen sicherstellen, dass die korrekte Ausgabe durch die Eingabe eindeutig definiert wird.

Beispiele:

Hier sind einige gültige Eingabeausdrücke und die entsprechenden Ausgaben, dargestellt in der Form "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 + * -"

(Zumindest hoffe ich, dass all dies richtig ist. Ich habe die Konvertierung von Hand durchgeführt, sodass sich Fehler eingeschlichen haben könnten.)

Die folgenden Eingaben sind alle ungültig. Es spielt keine Rolle, was Ihre Lösung tut, wenn sie angegeben wird (obwohl es natürlich sinnvoller ist, z. B. eine Fehlermeldung zurückzugeben, als beispielsweise unendlich viel Speicherplatz zu verbrauchen):

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

Muschelutensilien - 60 Zeichen

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

Die verschiedenen Probleme wurden behoben, aber es wurde viel länger :(

C 250 245 236 193 185 Zeichen

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));}

Hier ist eine lesbare Version der Quelle ohne Golf, die immer noch die grundlegende Logik widerspiegelt. Es ist eigentlich ein ziemlich einfaches Programm. Die einzige wirkliche Aufgabe besteht darin, einen Operator mit niedriger Assoziativität auf einen Stapel zu verschieben, wenn ein Operator mit hoher Assoziativität angetroffen wird, und ihn dann am "Ende" dieses Unterausdrucks wieder zu entfernen.

#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 / C Präprozessor 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

Endlich ist es nicht mehr länger als die C-Lösung. Das entscheidende Haskell-Teil ist fast so faul wie die bc-Lösung ...

Übernimmt Eingaben als Befehlszeilenparameter. Eine Datei wmit einigen ghc-Warnmeldungen wird erstellt, wenn Sie diese Änderung nicht möchten runghc 2>/dev/null.

Python 2, 290 272 268 250 243 238 Bytes

Jetzt endlich kürzer als die JS Antwort!

Dies ist ein vollständiges Programm, das eine grundlegende Implementierung des Rangierbahnhof-Algorithmus verwendet . Die Eingabe erfolgt in Anführungszeichen und das Ergebnis wird an ausgegeben 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)

Probieren Sie es online!

Erläuterung:

Als erstes müssen wir die Eingabe in Token konvertieren. Wir verwenden dazu alle Übereinstimmungen des regulären Ausdrucks \d+|\S, die grob in "eine beliebige Gruppe von Ziffern und ein beliebiges Nicht-Leerzeichen" übersetzt wurden. Dadurch werden Leerzeichen entfernt, benachbarte Ziffern als einzelne Token analysiert und Operatoren separat analysiert.

Für den Rangierbahnhof-Algorithmus müssen vier verschiedene Tokentypen verarbeitet werden:

• ( - Linke Klammer
• ) - Rechte Klammer
• +-*/ - Betreiber
• 9876543210 - Numerische Literale

Zum Glück sind die ASCII-Codes in der angegebenen Reihenfolge gruppiert, sodass wir den Tokentyp (t>'/')+(t>')')+(t>'(')anhand des Ausdrucks berechnen können. Dies ergibt 3 für Ziffern, 2 für Operatoren, 1 für eine rechte Klammer und 0 für eine linke Klammer.

Mit diesen Werten indizieren wir das große Tupel after exec, um das entsprechende Snippet basierend auf dem Token-Typ auszuführen. Dies ist für jeden Token anders und das Rückgrat des Rangierbahnhof-Algorithmus. Es werden zwei Listen (als Stapel) verwendet: O(Operationsstapel) und B(Ausgabepuffer). Nachdem alle Token ausgeführt wurden, werden die verbleibenden Operatoren auf dem OStapel mit dem Ausgabepuffer verknüpft und das Ergebnis gedruckt.

Prolog (SWI-Prolog) , 113 Bytes

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).

Probieren Sie es online!

SWI Prolog verfügt über eine viel bessere Anzahl an integrierten Funktionen als GNU Prolog, wird jedoch durch die ausführliche Syntax von Prolog noch etwas zurückgehalten.

Erläuterung

term_to_atomWenn Sie rückwärts ablaufen, wird ein (als Atom gespeicherter) Infix-Notationsausdruck in einen Analysebaum geparst (unter Beachtung der üblichen Vorrangregeln und Löschen von führenden Nullen und Leerzeichen). Anschließend verwenden wir das Hilfsprädikat c, um eine strukturelle Rekursion über den Analysebaum durchzuführen und diese zunächst in die Postfix-Notation umzuwandeln.

Javascript (ES6), 244 Byte

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` `)

Beispiel:
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 + * -(mit einem Leerzeichen)

Erläuterung:

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 Bytes

R ist in der Lage, sich selbst zu analysieren. Statt das Rad neu zu erfinden, setzen wir den Parser einfach in Betrieb, der die Präfixnotation ausgibt, und verwenden eine rekursive Funktion, um auf die Postfixnotation umzuschalten.

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,"")
}

Das pArgument ist, die Verwendung von Nicht-Standard-Auswertungen zu kontrollieren (der Fluch von R-Programmierern überall), und es gibt ein paar Extras if, um die Ausgabe von Klammern zu kontrollieren (die wir vermeiden wollen).

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

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

Eingang: (((((1))) + (2)))

Ausgabe: 1 2 +

Als Bonus funktioniert es mit beliebigen Symbolen und beliebigen vordefinierten Funktionen mit bis zu zwei Argumenten:

Eulers Identität

Eingang: e^(i*pi)-1

Ausgabe: e i pi * ^ 1 -

Dividenden von 13 zwischen 1 und 100

Eingang: which(1:100 %% 13 == 0)

Ausgabe: 1 100 : 13 %% 0 == which

Lineare Regression des Gewichts von Hühnchen als Funktion der Zeit

Eingang: summary(lm(weight~Time, data=ChickWeight))

Ausgabe: weight Time ~ ChickWeight lm summary

Das letzte Beispiel liegt vielleicht etwas außerhalb des Anwendungsbereichs des OP, verwendet aber die Postfix-Notation, also ...