Arithmetic Expression evaluator

Question

This program takes text input and evaluates the expression. This is meant to be an exercise.

I reinvented a stack class though I know C++ provides one in the standard library but it isn"t meant for production use but to solidify my knowledge on linked list data structure

I also made an infix postfix converter which converts 2 + 2 to 22+ which seems easier for a computer to evaluate.

My major concerns are

1. Optimization
2. Potential pitfalls
3. General bad practice
4. Readability
5. Ease of use

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

Avoid unnecessary forward declarations

Instead of forward-declaring function prototypes, you can change the order in which you define the functions in main.cc. This means less duplication, and less chance of errors.

Be aware that string literals contain a terminating NUL-byte

When you try to get the length of the string op in isOperator(), size will be 8, since it will also include the NUL-byte that terminates the string literal "+*/-()^". It turns out to be harmless here, but it is better to avoid this. Since in this case, op is not meant to be a single string but really an array of individual characters, I would initialize it like so:

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

Then size will also automatically be correct.

Avoid using std::endl

Prefer using '"\n"instead ofstd::endl`. The latter is equivalent to the former, but it also forces the output to be flushed, which can be bad for performance.

However, you do need to explictly flush the output if you don't end a line with a newline character, in case the output is line-buffered. So:

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

Avoid excessive conversions to and from strings

When you evaluate a subexpression, you return the result as a string again. This means that the CPU is mostly spending its time converting values to and from strings. It would be much more efficient to parse the whole expression first into tokens, converting any numbers into doubles, and then do the actual evaluation on the tokens.

You would need to find some way to store a token, which can be either a number or an operator. You could use std::variant for this if you can use C++17, otherwise you could use a tagged union.

About your stack implementation

There are several things that could be improved in your implementation of a stack, apart from just using std::stack of course:

Make it a proper class

You have a lot of global functions to manipulate the single instance of the stack. However, you could easily make these functions member functions of struct Stack.

Use std::unique_ptr to manage memory for you

I know you wanted to implement a stack container from scratch, so maybe you also wanted to do the memory allocation from scratch. However, it is easy to get this wrong. Consider using std::unique_ptr to manage pointers to stack elements.

Consider making it look like a STL container

Try to make the names of your stack (member) functions similar to those used by STL containers. This makes them easier to remember, and will also make it easier to change container types in your program without having to modify all the sites calling member functions operating on container variables. So for example, instead of peek(), use top().

Is it just a stack or more than that?

Since your stack also has insertAtBottom() and reverse(), it is not really just a stack anymore, but more like a reversible queue or linked list. However, since the internal data structure is still that of a stack, the operations insertAtBottom() and reverse() are actually quite expensive operations. Especially reverse(), which looks \$\mathcal{O}(N^2)\$ to me: it recursively calls itself, but then also calls insertAtBottom() which also recursively calls itself.

Answer 2

Code Review of Stack

Why is this not all a class?

---

Why are you not using a namespace?

---

Double underscore on an identifier is reserved for the implementation in all situations. Don't do this:

#ifndef STACK__
#define STACK__

Note: A single trailing underscore is fine. But I usually add the _H at the end (to distinguish it from _TPP guards).

While we are on guards. I can see the identifier STACK potentially being overloaded. I would add a namespace to the guard.

#ifndef THE_PROGRAMMER_STACK_H
#define THE_PROGRAMMER_STACK_H

namespace TheProgrammer
{
    // Stuff
}

---

I would say this is a node in a stack.

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

I would have done:

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

      // STUFF
};

---

Pass strings by const reference:

void push( std::string x );

Here you are passing by value and as such you are making a copy. If you want to be advanced allow a push using an r-value.

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

---

Here I would return a reference.

std::string peek();

That way you can take a copy if you want to. Or if you don't want to then you can use it directly. You want to have a normal and a const version so you can use the stack in const context.

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

---

Sure. But if these are a member of a class you want to mark them as const.

int size();
bool isEmpty();

---

Display is great. But usually we use operator<< to stream an object to an output stream. So I would add this. It can use display() internally.

void display();

I would do this:

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

You can simplify this:

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

---

Normally I would not add this test.

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

The user code should alsready by testing with isEmpty() before calling this. If they are not that needs to be found during testing. If you need a checked pop() then add a seprate function.

---

Excessive copying:

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

I would simplify to:

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

---

This ultimately works.

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

But seems a bit complex (as you are modifying all the links). Why not simply find the last item then add the new item.

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

---

Sure. But if you make Stack a class you can store the number of items. This way you don't have to calculate it each time.

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

---