Ketika saya melihat judul pertanyaan tertutup ini , saya pikir itu tampak seperti tantangan kode golf yang menarik. Jadi izinkan saya menyajikannya sebagai berikut:

Tantangan:

Tulis sebuah program, ekspresi atau subrutin yang, diberi ekspresi aritmetika dalam notasi infiks , seperti 1 + 2, menghasilkan ekspresi yang sama dalam notasi postfix , yaitu 1 2 +.

(Catatan: Tantangan serupa telah diposting sebelumnya pada bulan Januari. Namun, saya merasa kedua tugas tersebut cukup berbeda secara detail untuk membenarkan tantangan terpisah ini. Juga, saya hanya melihat utas lainnya setelah mengetik semua yang di bawah ini, dan saya lebih suka tidak hanya membuang semuanya.)

Memasukkan:

Input terdiri dari infix ekspresi aritmatika yang valid terdiri dari angka (bilangan bulat non-negatif direpresentasikan sebagai urutan satu atau lebih desimal digit), seimbang kurung untuk menunjukkan subexpression dikelompokkan, dan empat infiks biner operator + , -, *dan /. Semua ini dapat dipisahkan (dan seluruh ekspresi dikelilingi) oleh sejumlah karakter spasi, yang harus diabaikan. ¹

Bagi mereka yang menyukai tata bahasa formal, inilah tata bahasa sederhana seperti BNF yang mendefinisikan input yang valid. Untuk singkatnya dan kejelasan, tata bahasa tidak termasuk spasi opsional, yang dapat terjadi antara dua token (selain dari digit dalam angka):

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

_{¹ Satu-satunya kasus di mana keberadaan spasi dapat mempengaruhi penguraian adalah ketika mereka memisahkan dua angka berurutan; Namun, karena dua angka yang tidak dipisahkan oleh operator tidak dapat terjadi dalam ekspresi infiks yang valid, kasus ini tidak akan pernah terjadi pada input yang valid.}

Keluaran:

Outputnya harus berupa ekspresi postfix yang setara dengan input. Ekspresi output hanya boleh terdiri dari angka dan operator, dengan karakter spasi tunggal antara setiap pasangan token yang berdekatan, seperti dalam tata bahasa berikut (yang tidak termasuk spasi) ² :

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

_{² Sekali lagi untuk kesederhanaan, numberproduksi dalam tata bahasa ini mengakui angka dengan nol di depan, meskipun mereka dilarang dalam output oleh aturan di bawah ini.}

Diutamakan operator:

Dengan tidak adanya tanda kurung, aturan diutamakan berikut ini berlaku:

• Operator *dan /memiliki prioritas lebih tinggi daripada +dan -.
• Operator *dan /memiliki prioritas yang sama satu sama lain.
• Operator +dan -memiliki prioritas yang sama satu sama lain.
• Semua operator bersifat asosiatif kiri.

Misalnya, dua ekspresi berikut ini setara:

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

dan keduanya harus menghasilkan output berikut:

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

(Ini adalah aturan presedensi yang sama seperti dalam bahasa C dan dalam sebagian besar bahasa yang berasal darinya. Mereka mungkin menyerupai aturan yang diajarkan pada Anda di sekolah dasar, kecuali mungkin untuk diutamakan relatif dari *dan /.)

Aturan lain-lain:

• Jika solusi yang diberikan adalah ekspresi atau subrutin, input harus diberikan dan output dikembalikan sebagai string tunggal. Jika solusinya adalah program yang lengkap, ia harus membaca baris yang berisi ekspresi infiks dari input standar dan mencetak baris yang berisi versi postfix ke output standar.

• Angka dalam input mungkin termasuk nol di depan. Angka dalam output tidak boleh memiliki nol di depannya (kecuali untuk angka 0, yang akan menjadi output sebagai 0).

• Anda tidak diharapkan untuk mengevaluasi atau mengoptimalkan ekspresi dengan cara apa pun. Secara khusus, Anda tidak boleh berasumsi bahwa operator harus memenuhi identitas aljabar, komutatif, atau lainnya. Artinya, Anda tidak boleh berasumsi bahwa eg 1 + 2sama dengan 2 + 1atau 1 + (2 + 3)sama dengan itu (1 + 2) + 3.

• Anda dapat berasumsi bahwa angka dalam input tidak melebihi 2 ³¹ - 1 = 2147483647.

Aturan-aturan ini dimaksudkan untuk memastikan bahwa output yang benar didefinisikan secara unik oleh input.

Contoh:

Berikut adalah beberapa ekspresi input yang valid dan output yang sesuai, yang disajikan dalam formulir "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 + * -"

(Setidaknya, saya harap semua ini benar; Saya melakukan pertobatan dengan tangan, sehingga kesalahan mungkin merayap masuk.)

Supaya jelas, input berikut semuanya tidak valid; itu tidak peduli apa solusi Anda tidak jika diberikan mereka (meskipun, tentu saja, misalnya kembali pesan kesalahan lebih bagus daripada, katakanlah, mengkonsumsi jumlah tak terbatas memori):

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

Utilitas shell - 60 karakter

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

Memperbaiki berbagai masalah, tapi itu menjadi lebih lama :(

C, 250 245 236 193 185 karakter

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

Ini adalah versi yang dapat dibaca dari sumber yang tidak dikenali, yang masih mencerminkan logika dasar. Ini sebenarnya program yang agak mudah. Satu-satunya pekerjaan nyata yang harus dilakukan adalah untuk mendorong operator asosiasi rendah ke tumpukan ketika operator asosiasi tinggi ditemukan, dan kemudian pop kembali di "ujung" dari subekspresi itu.

#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 dengan Haskell dengan C preprocessor 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

Akhirnya, ini tidak lebih lama dari solusi C lagi. Bagian penting Haskell hampir sama malasnya dengan solusi bc ...

Mengambil input sebagai parameter baris perintah. Filew dengan beberapa pesan peringatan ghc akan dibuat, jika Anda tidak suka perubahan ini runghc 2>/dev/null.

Python 2, 290 272 268 250 243 238 byte

Sekarang akhirnya lebih pendek dari jawaban JS!

Ini adalah program lengkap yang menggunakan implementasi dasar dari algoritma shunting yard . Input diberikan sebagai string yang dikutip, dan hasilnya dicetak ke 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)

Cobalah online!

Penjelasan:

Hal pertama yang perlu kita lakukan adalah mengubah input menjadi token. Kami melakukan ini dengan menggunakan semua kecocokan dari regex\d+|\S , yang diterjemahkan secara kasar ke "grup digit apa pun, dan karakter apa pun yang bukan spasi". Ini menghapus spasi putih, mem-parsing digit yang berdekatan sebagai token tunggal, dan mem-parsing operator secara terpisah.

Untuk algoritma halaman shunting, ada 4 jenis token berbeda yang perlu kita tangani:

• ( - Kurung kiri
• ) - Tanda kurung tepat
• +-*/ - Operator
• 9876543210 - Numerik literal

Untungnya, kode ASCII ini semuanya dikelompokkan dalam urutan yang ditunjukkan, sehingga kita dapat menggunakan ekspresi (t>'/')+(t>')')+(t>'(')untuk menghitung jenis token. Ini menghasilkan 3 untuk digit, 2 untuk operator, 1 untuk tanda kurung kanan dan 0 untuk tanda kurung kiri.

Dengan menggunakan nilai-nilai ini, kami mengindeks ke tuple besar setelah execuntuk mendapatkan potongan yang sesuai untuk dieksekusi, berdasarkan pada jenis token. Ini berbeda untuk setiap token dan merupakan tulang punggung dari algoritma halaman shunting. Dua daftar digunakan (sebagai tumpukan): O(tumpukan operasi) dan B(buffer output). Setelah semua token dijalankan, operator yang tersisa pada Ostack disatukan dengan buffer output, dan hasilnya dicetak.

Prolog (SWI-Prolog) , 113 byte

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

Cobalah online!

Prolog SWI memiliki set builtin yang jauh lebih baik untuk ini daripada Prolog GNU, tetapi itu masih agak terbendung oleh verbositas sintaks Prolog.

Penjelasan

term_to_atomakan, jika dijalankan mundur, mem-parse ekspresi infiks-notasi (disimpan sebagai atom) menjadi pohon parse (mematuhi aturan prioritas yang biasa, dan menghapus angka nol dan spasi yang memimpin). Kami kemudian menggunakan predikat helper cuntuk melakukan rekursi struktural di atas pohon parse, yang diubah menjadi notasi postfix dengan cara yang lebih dulu mendalam.

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

Contoh:
Panggilan: f('0-1+(2-3)*4-5*(6-(7+8)/9+10)')
Keluaran: 0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -(dengan spasi tambahan)

Penjelasan:

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 byte

R dapat menguraikan sendiri, jadi daripada menemukan kembali roda, kami hanya menempatkan pengurai untuk bekerja, yang menghasilkan notasi awalan, dan menggunakan fungsi rekursif untuk mengubahnya ke notasi postfix.

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

The pargumen adalah untuk mengontrol penggunaan evaluasi non-standar (kutukan programmer R di mana-mana), dan ada beberapa tambahan ifdalam sana untuk mengontrol keluaran kurung (yang kita ingin menghindari).

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

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

Memasukkan: (((((1))) + (2)))

Keluaran: 1 2 +

Sebagai bonus, ia bekerja dengan simbol sewenang-wenang, dan fungsi yang telah ditentukan sebelumnya hingga dua argumen:

Identitas Euler

Memasukkan: e^(i*pi)-1

Keluaran: e i pi * ^ 1 -

Dividen 13 antara 1 dan 100

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

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

Regresi linier berat bayi ayam sebagai fungsi waktu

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

Keluaran: weight Time ~ ChickWeight lm summary

Contoh terakhir mungkin sedikit di luar ruang lingkup OP, tetapi menggunakan notasi postfix, jadi ...