L'interruzione condizionale di un ciclo può essere riscritta per una comprensione più semplice?

2
while cond1
    ...
    if cond2
        ...
    else
        ...
        break

Il ciclo while sopra ha due condizioni di terminazione,

  • cond2 e !cond1
  • !cond2

Quando i comandi rappresentati da ... sono lunghi, Sento che il codice non è facile da capire. Le due condizioni di terminazione per lo stesso ciclo while sono molto distanti. Vedi quando l'interruzione è errata .

C'è un modo migliore per scrivere un codice di questo tipo per renderlo più comprensibile? Ad esempio, possiamo evitare di scrivere le due condizioni di terminazione in due punti separati?

La mia domanda deriva dalla lettura di un programma C ++, ma in realtà non è specifico per i linguaggi di programmazione. Prendi solo i consueti costrutti di controllo disponibili nei linguaggi di programmazione.

Un'implementazione non ricorsiva di attraversamento postorder di un albero binario, usando lo stack

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    const TreeNode *p = root, *q = nullptr;
    do {
        while (p != nullptr) { 
            s.push(p);
            p = p->left;
        }
        q = nullptr;

        // start of the example
        while (!s.empty()) {
            p = s.top();
            s.pop();
            if (p->right == q) {
                result.push_back(p->val);
                q = p;  
            } else {
                s.push(p);
                p = p->right;
                break;         //<=== exit inner loop
            }
         }   
        // end of example

    } while (!s.empty());  //end do..while
    return result;
}
    
posta Tim 05.11.2016 - 19:19
fonte

2 risposte

4

Il problema del flusso di controllo generale che esponi

Le cose non sono così semplici come ti presenti:

while cond1
    ...block1...
    if cond2
        ...block2...
    else
        ...block3...
        break

Quando cond1 è false alla prima iterazione, il ciclo non viene eseguito affatto. In tutti gli altri casi, viene eseguito block1 e potrebbe influire su cond2 .

Solo allora, se !cond2 il ciclo viene chiuso; ma solo dopo che viene eseguito block3 , essendo inteso che block3 potrebbe modificare sia cond1 che cond2 , senza cambiare il fatto che il ciclo deve essere chiuso.

Nota anche che puoi inserire il ciclo, eseguire block1 e block2 o solo block1 .

Può essere risolto facilmente senza riscrivere le diverse parti?

Si potrebbe provare a ingannare usando effetti collaterali, operatore di coma e connettori logici nelle condizioni:

while (cond1 && (block1 , !cond2) )  // ouch the awful coma operator
    block2  

Ma potrebbe diventare molto illeggibile! E devi ancora trovare un trucco che esegua block3 solo se il ciclo è stato eseguito almeno una volta e se il ciclo non è riuscito a causa di !cond2 .

Anche con una struttura ad anello simile ad ADA che consentirebbe di avere la condizione del ciclo nel mezzo , non potresti facilmente riscriverlo, almeno per il caso generale.

Potresti anche provare a introdurre alcuni indicatori booleani, e con uno stato iniziale intelligente e combinazioni di if e while riescono a ottenere tutte le condizioni di ciclo in un unico punto. Ma provalo: non sembrerà più semplice di quello che hai scritto inizialmente! Al contrario, i trucchi extra renderanno il tutto molto più difficile da leggere.

Quindi come risolverlo?

Il problema non è in realtà il flusso di controllo da solo: è infatti facile da capire e comprendere i casi speciali.

La vera sfida per la leggibilità, è quando i tuoi blocchi diventano grandi e alla fine troppo annidati.

In questo caso, segui i consigli Uncle Bob : mantieni le funzioni piccole facendo una cosa e ad un livello di astrazione. Se è troppo grande, stai facendo troppe cose. Quindi metti i blocchi in funzioni più piccole (passando per riferimento se sono necessari effetti collaterali) e dai nomi delle funzioni che rendono chiaro il tuo intento.

    
risposta data 06.11.2016 - 01:46
fonte
2

In primo luogo, probabilmente dovresti usare un algoritmo ricorsivo qui. Lo stack integrato sarà più veloce e più facile da usare, quindi verrà costruito manualmente qui. Lasciando da parte questo:

Trovo che una tecnica utile quando si tenta di eliminare le interruzioni a metà ciclo consiste nel duplicare temporaneamente il codice per evitarlo. Quindi provo a ripulire il codice risultante. Nel tuo caso, inizierei riscrivendo il tuo codice in questo modo:

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    const TreeNode *p = root, *q = nullptr;
    do {
        while (p != nullptr) { 
            s.push(p);
            p = p->left;
        }
        q = nullptr;

        while (!s.empty()) {
            p = s.top();
            s.pop();
            if (p->right == q) {
                result.push_back(p->val);
                q = p;  
            } else {
                s.push(p);
                p = p->right;
                while (p != nullptr) { 
                    s.push(p);
                    p = p->left;
                }
                q = nullptr;
            }
         }   
    } while (!s.empty());  //end do..while
    return result;
}

Fatto questo, possiamo vedere che il ciclo esterno è inutile. Non verrà mai eseguito perché il ciclo interno ora termina solo quando lo stack è vuoto. Quindi possiamo rimuoverlo:

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    for(TreeNode *p = root; p != nullptr;p = p->left) { 
        s.push(p);
    }

    TreeNode* q = nullptr;

    while (!s.empty()) {
        TreeNode * p = s.top();
        if (p->right == q) {
            result.push_back(p->val);
            s.pop();
            q = p;  
        } else {
            for(TreeNode *node = p->right; p != nullptr; p = p->left) {
                s.push(node);
            }
            q = nullptr;
        }
     }   

    return result;
}

Possiamo quindi aggiungere alcune pulizie generali: migliorare l'ambito delle variabili, evitare di scoppiare gli elementi dallo stack solo per spingerli di nuovo, ecc.

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    for(TreeNode *p = root; p != nullptr;p = p->left) { 
        s.push(p);
    }

    TreeNode* q = nullptr;

    while (!s.empty()) {
        TreeNode * p = s.top();
        if (p->right == q) {
            result.push_back(p->val);
            s.pop();
            q = p;  
        } else {
            for(TreeNode *node = p->right; p != nullptr; p = p->left) {
                s.push(node);
            }
            q = nullptr;
        }
     }   

    return result;
}

Il risultato è un codice che trasmette molto più chiaramente ciò che il tuo algoritmo sta facendo. Questo è un po 'di duplicazione spingendo gli oggetti a sinistra, e ti infastidisce, puoi estrarlo in una funzione.

    
risposta data 06.11.2016 - 01:58
fonte