Evaluator Ekspresi Aritmatika

Question

Program ini mengambil input teks dan mengevaluasi ekspresi. Ini dimaksudkan sebagai latihan.

Saya menemukan kembali kelas tumpukan meskipun saya tahu C ++ menyediakan satu di perpustakaan standar tetapi itu tidak dimaksudkan untuk penggunaan produksi tetapi untuk memperkuat pengetahuan saya tentang struktur data daftar tertaut

Saya juga membuat konverter postfix infix yang mengubah 2 + 2 menjadi 22+ yang tampaknya lebih mudah untuk dievaluasi oleh komputer.

Perhatian utama saya adalah

1. Optimasi
2. Potensi jebakan
3. Praktik buruk umum
4. Keterbacaan
5. Kemudahan penggunaan

main.cc

#include <iostream>
#include <string>
#include <cassert>
#include <cmath>
#include "stack.hh"

/* function prototypes */
bool isOperator( const char c );
std::string strip( const std::string &s );
std::string parse( const std::string &A, const std::string &B, const char op );
double eval( const std::string &s);
int prec( const char c );
std::string postfix( const std::string &s );

/* main function */
int main() {
    std::string s;
    while ( true ) {
        try {
            std::cout << "Enter text evaluate ( press $ to end ): \n"; std::cout << "> "; std::getline( std::cin, s ); if ( s == "$" )
                break;
            std::cout << eval( s ) << "\n";
        } catch ( std::runtime_error &e ) {
            std::cout << "Invalid expression" << std::endl;
        }
    }
}

bool isOperator( const char c ) {
    const char op[] = "+*/-()^";
    static constexpr size_t size = sizeof( op ) / sizeof(op[0]);
    for( unsigned i = 0; i != size; ++i ) {
        if ( c == op[ i ] ) 
            return true;
    }
    return false;
}

std::string strip( const std::string &s ) {
    /* remove all invalid characters */
    std::string n;
    for( auto &c : s ) {
        if( isdigit( c ) || isOperator( c ) ) {
            n += c;
        }
    }
    return n;
}


int prec( const std::string &c ) {
    if ( c == "^" )
        return 3;
    if ( c == "*" || c == "/" )
        return 2;
    if ( c == "+" || c == "-" )
        return 1;
    return -1;
}

std::string postfix( const std::string &s ) {
    /* convert to postfix */
    emptyStack();
    push("N");
    int l = s.size();
    std::string ns, temp;
    for( int i = 0; i != l; ++i ) {
        temp = "";
        temp.push_back( s[ i ]);
        if( isdigit( s[i] ) )  {
            ns += temp;
        }
        else if( temp  == "(" ) {
            push("(");
        }

        else if( temp == ")" ) {
            // if closing parentheses is found, pop the stack till equivalent opening parentheses;
            while( peek() != "N" && peek() != "(" ) {
                std::string c = peek();
                pop();
                ns += c;
            }
            if( peek() == "(" ) {
                pop();
            }
        }
        else if( peek() == "(" ) {
            push( temp );
        }
        else {
            while( peek() != "N" && prec( temp ) <= prec( peek() ) ) {
                /* use precedence rule to compare operators */
                std::string  c = peek();
                pop();
                ns += c;
            }
            push( temp );
        }
    }
    while( peek() != "N" ) {
        // pop remaining element from the stack
        std::string c = peek();
        pop();
        ns += c;
    }
    return ns;
}

std::string parse( const std::string &A, const std::string &B, const char op ) {
    std::string result;
    switch (op) {
        case '^':
            result = std::to_string( std::pow( std::stod( A ), std::stod( B ) ) ) ;
            std::cout << result;
            break;
        case '*':
            result = std::to_string( std::stod( A ) * std::stod( B ) );
            break;
        case '/':
            result = std::to_string( std::stod( A ) / std::stod( B ) );
            break;
        case '+':
            result = std::to_string( std::stod( A ) + std::stod( B ) );
            break;
        case '-':
            result = std::to_string( std::stod( A ) - std::stod( B ) );
            break;
        default:
            throw std::invalid_argument("Invalid operator.");
            break;
    }
    return result;
}

double eval( const std::string &s) {
    std::string newStr = s;
    newStr = strip( newStr );
    newStr = postfix( newStr );

    emptyStack(); // deletes all contents in the stack and prepares stack for reuse

    std::string temp; // temp string to store each character for evaluation
    std::string result;
    size_t l = newStr.size();
    for( size_t i = 0; i != l; ++i ) {
        temp = ""; // reset the string temp for reuse in the next evaluation
        if( isdigit( newStr[i] ) ) {
            temp.push_back( newStr[ i ] );
            push( temp );
        }
        if( isOperator( newStr[ i ] ) ) {
            // If an operator is found, pop out 2 operands from the stack
            // and evaluate them 
            std::string A = peek();
            pop();
            std::string B = peek();
            pop();
            result = parse( B, A, newStr[ i ] );
            push(result);
        }
    }
    result = peek(); // The result is the top of the stack
    pop();
    return std::stod( result );
}

stack.hh

#ifndef STACK__
#define STACK__

struct Stack{
    std::string data;
    Stack *link;
};

void push( std::string x );
void pop();
std::string peek();
void insertAtBottom( std::string x );
void reverse();
int size();
bool isEmpty();
void emptyStack();
void display();

#endif;

stack.cc

#include <iostream>
#include <string>
#include "stack.hh"

Stack *top = nullptr;

void push( std::string x ) {
    Stack *newNode = new Stack;
    newNode->data = x;
    newNode->link = top;
    top = newNode;
}

void pop() {
    if( top == nullptr ) {
        throw std::runtime_error("List is empty");
    }
    Stack *temp = top;
    top = top->link;
    delete temp;
}

std::string peek() {
    if( top == nullptr ) {
        throw std::runtime_error("List is empty");
    }
    Stack *temp = top;
    std::string x = temp->data;
    return x;
}

void insertAtBottom( std::string x ) {
    if ( top == nullptr )
        push( x );
    else {
        std::string a = peek( );
        pop( );
        insertAtBottom( x );
        push( a );
    }
}
void reverse() {
    if( top == nullptr )
        return;
    else {
        std::string a = peek();
        pop( );
        reverse( );
        
        insertAtBottom( a );
    }
}

int size() {
    Stack *temp = top;
    int count = 0;
    while( temp != nullptr ) {
        temp = temp->link;
        ++count;
    }
    return count;
}

bool isEmpty() { return ( top == nullptr ); }

void emptyStack() {
    while( isEmpty() == false ) {
        pop();
    }
}
void display() {
    Stack *temp = top;
    while( temp != nullptr ) {
        std::cout << temp->data << " ";
        temp = temp->link;
    }
}
```

Answer 1

Hindari deklarasi maju yang tidak perlu

Alih-alih mendeklarasikan prototipe fungsi, Anda bisa mengubah urutan mendefinisikan fungsi di main.cc. Ini berarti lebih sedikit duplikasi, dan lebih sedikit kemungkinan kesalahan.

Ketahuilah bahwa string literal berisi NUL-byte penghentian

Ketika Anda mencoba untuk mendapatkan panjang string opdi isOperator(), sizeakan menjadi 8, karena juga akan mencakup NUL-byte yang mengakhiri literal string yang "+*/-()^". Ternyata tidak berbahaya di sini, tetapi lebih baik hindari ini. Karena dalam kasus ini, optidak dimaksudkan sebagai string tunggal tetapi benar-benar array karakter individu, saya akan menginisialisasi seperti ini:

const char op[] = {'+', '*', ...};

Kemudian sizesecara otomatis juga akan benar.

Hindari pemakaian std::endl

Lebih suka menggunakan '"\ n" instead ofstd :: endl` . Yang terakhir setara dengan yang pertama, tetapi juga memaksa keluaran untuk dibilas, yang bisa berdampak buruk bagi kinerja.

Namun, Anda perlu secara eksplisit mengosongkan output jika Anda tidak mengakhiri baris dengan karakter baris baru, jika output berupa buffer baris. Begitu:

std::cout << "> " << std::flush;

Hindari konversi berlebihan ke dan dari string

Saat Anda mengevaluasi subekspresi, Anda mengembalikan hasilnya sebagai string lagi. Ini berarti CPU sebagian besar menghabiskan waktunya untuk mengubah nilai ke dan dari string. Akan jauh lebih efisien untuk mengurai seluruh ekspresi terlebih dahulu menjadi token , mengonversi bilangan apa pun menjadi doubles, dan kemudian melakukan evaluasi aktual pada token.

Anda perlu mencari cara untuk menyimpan token, yang bisa berupa nomor atau operator. Anda dapat menggunakan std::variantini jika Anda dapat menggunakan C ++ 17, jika tidak, Anda dapat menggunakan tag union.

Tentang implementasi tumpukan Anda

Ada beberapa hal yang dapat ditingkatkan dalam implementasi stack Anda, selain hanya menggunakan std::stacksaja:

Jadikan itu tepat class

Anda memiliki banyak fungsi global untuk memanipulasi satu contoh tumpukan. Namun, Anda dapat dengan mudah menjadikan fungsi ini sebagai fungsi anggota struct Stack.

Gunakan std::unique_ptruntuk mengatur memori untuk Anda

Saya tahu Anda ingin menerapkan penampung tumpukan dari awal, jadi mungkin Anda juga ingin melakukan alokasi memori dari awal. Namun, mudah untuk melakukan kesalahan ini. Pertimbangkan menggunakan std::unique_ptruntuk mengelola pointer untuk menumpuk elemen.

Pertimbangkan untuk membuatnya terlihat seperti wadah STL

Cobalah untuk membuat nama fungsi tumpukan (anggota) Anda mirip dengan yang digunakan oleh kontainer STL. Ini membuatnya lebih mudah untuk diingat, dan juga akan memudahkan untuk mengubah jenis penampung dalam program Anda tanpa harus mengubah semua situs yang memanggil fungsi anggota yang beroperasi pada variabel penampung. Jadi misalnya, alih-alih peek(), gunakan top().

Apakah hanya setumpuk atau lebih dari itu?

Karena tumpukan Anda juga memiliki insertAtBottom()dan reverse(), itu bukan hanya tumpukan lagi, tetapi lebih seperti antrian yang dapat dibalik atau daftar tertaut. Namun, karena struktur data internal masih berupa tumpukan, operasi insertAtBottom()dan operasi reverse()sebenarnya cukup mahal. Terutama reverse(), yang terlihat \$\mathcal{O}(N^2)\$bagi saya: itu secara rekursif memanggil dirinya sendiri, tetapi kemudian juga memanggil insertAtBottom()yang juga secara rekursif memanggil dirinya sendiri.

Answer 2

Review Kode Stack

Mengapa ini tidak semuanya kelas?

---

Mengapa Anda tidak menggunakan namespace?

---

Garis bawah ganda pada pengenal dicadangkan untuk implementasi di semua situasi. Jangan lakukan ini:

#ifndef STACK__
#define STACK__

Catatan: Satu garis bawah bisa saja. Tapi saya biasanya menambahkan _Hdi bagian akhir (untuk membedakannya dari _TPPpenjaga).

Sementara kita berjaga. Saya dapat melihat pengenal STACKberpotensi kelebihan muatan. Saya akan menambahkan namespace untuk penjaga.

#ifndef THE_PROGRAMMER_STACK_H
#define THE_PROGRAMMER_STACK_H

namespace TheProgrammer
{
    // Stuff
}

---

Saya akan mengatakan ini adalah node dalam tumpukan.

struct Stack{
    std::string data;
    Stack *link;
};

Saya akan melakukan:

class Stack
{
     struct Node
     {
         std::string data;
         Node*       link;
     };
     Node*   root;
     
     public:

      // STUFF
};

---

Lewati string dengan referensi const:

void push( std::string x );

Di sini Anda melewatkan nilai dan dengan demikian Anda membuat salinan. Jika Anda ingin mahir, izinkan dorongan menggunakan nilai-r.

void push(std::string const&  x);  // Copy into stack
void push(std::string&&       x);  // Move into stack

---

Di sini saya akan mengembalikan referensi.

std::string peek();

Dengan cara itu Anda dapat mengambil salinannya jika Anda mau. Atau jika Anda tidak mau maka Anda bisa menggunakannya secara langsung. Anda ingin memiliki versi normal dan const sehingga Anda dapat menggunakan stack dalam konteks const.

std::string&        Stack::peek();
std::string const&  Stack::peek() const;

---

Tentu. Tetapi jika ini adalah anggota kelas, Anda ingin menandainya sebagai const.

int size();
bool isEmpty();

---

Tampilannya bagus. Tapi biasanya kita gunakan operator<<untuk mengalirkan objek ke aliran keluaran. Jadi saya akan menambahkan ini. Itu bisa digunakan secara display()internal.

void display();

Saya akan melakukan ini:

void Stack::display(std::ostream& = std::cout);
friend std::ostream& operator<<(std::ostream& str, Stack& stack)
{
    stack.display(str);
    return str;
}

---

void push( std::string x ) {
    Stack *newNode = new Stack;
    newNode->data = x;
    newNode->link = top;
    top = newNode;
}

Anda dapat menyederhanakan ini:

void push( std::string x ) {
    Stack *newNode = new Stack{x, top};
    top = newNode;
}

---

Biasanya saya tidak akan menambahkan tes ini.

void pop() {
    if( top == nullptr ) {
        throw std::runtime_error("List is empty");
    }

Kode pengguna harus sudah dengan menguji dengan isEmpty()sebelum memanggil ini. Jika tidak, itu perlu ditemukan selama pengujian. Jika Anda perlu diperiksa pop()kemudian tambahkan fungsi seprate.

---

Penyalinan berlebihan:

std::string peek() {
    Stack *temp = top;
    std::string x = temp->data;  // Copy into temp
    return x;                    // Copy back to caller
}

Saya akan menyederhanakan menjadi:

std::string& peek() {
    return temp->data;
}

---

Ini akhirnya berhasil.

void insertAtBottom( std::string x ) {
    if ( top == nullptr )
        push( x );
    else {
        std::string a = peek( );
        pop( );
        insertAtBottom( x );
        push( a );
    }
}

Tetapi tampaknya agak rumit (karena Anda memodifikasi semua tautan). Mengapa tidak mencari item terakhir lalu menambahkan item baru.

void insertAtBottom(std::string const& x)
{
    if ( top == nullptr ) {
        return push( x );
    }
    Stack* loop = top;
    for(;loop->link != nullptr; loop = loop->link) {}
    loop->link = new Stack{x, null};
}

---

Tentu. Tetapi jika Anda membuat Stackkelas, Anda dapat menyimpan jumlah item. Dengan cara ini Anda tidak perlu menghitungnya setiap saat.

int size() {
    Stack *temp = top;
    int count = 0;
    while( temp != nullptr ) {
        temp = temp->link;
        ++count;
    }
    return count;
}

---