C++ evaluating an arithmetic expression in RPN format using ADT stack

C and C++ are two different languages. Since we're using <iostream> it's clear that this is C++ (although the Stack struct is created in a very C-like fashion).

#include <string.h> 

Since this is C++, if we want the C++ version of functions from the C standard library, we should include the <cstring> header. This header puts the contents into the std namespace.

Alternatively, we can use the C++ std::string class, which is in the <string> header.

using namespace std;

This is a bad habit to get into, even in small programs, as it can lead to name collisions. We should qualify names fully where we need to, e.g. std::cout.

struct Stack
{
    int top;
    unsigned cap;
    int* arr;
};

The push, pop, and peek functions all use chars, but the Stack contains an array of ints. We should probably use int consistently throughout.

Note that the C++ standard library already contains a stack class. So we don't need to write our own.

struct Stack* createStackFun(unsigned capacity)
{
    struct Stack* s = (struct Stack*) malloc(sizeof(struct Stack));
    if (!s) return NULL;
    s->top = -1;
    s->cap = capacity;
    s->arr = (int*)malloc(s->cap * sizeof(int));
    if (!s->arr) return NULL;
    return s;
}

C++ doesn't have a separate namespace for struct types, so we can just write Stack* instead of struct Stack*.

Since this is C++, we should be using new and delete[], not malloc and free. (Well... actually we shouldn't be doing manual memory management at all).

There's no need to create the Stack itself on the heap with malloc. We can use a simple local variable, and return it by value. Only the arr memory needs to be allocated on the heap.

The stack pointer we return from this function is never freed, and neither are its resources! We should have an equivalent destroyStack function to clean up when we don't need it any more.

Since this is C++, we should be using a constructor and destructor instead of free functions.

Stack(unsigned capacity):
    top(-1),
    cap(capacity),
    arr(new int[cap])
{
    
}

~Stack()
{
    delete[] arr;
}

new will throw an exception if allocation fails, so we don't need to manually check for a null value.

Note that we would also have to think about copy and move operations on the class. The easiest thing to do is tell the compiler not to allow them:

Stack(Stack const&) = delete; // no copy-construction
Stack& operator=(Stack const&) = delete; // no copy-assignment
Stack(Stack&&) = delete; // no move-construction
Stack& operator=(Stack&&) = delete; // no move-assignment

int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}

char peek(struct Stack* stack)
{
    return stack->arr[stack->top];
}

char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->arr[stack->top--];
    return '$';
}

void push(struct Stack* stack, char op)
{
    stack->arr[++stack->top] = op;
}

In C++, these can be member functions. The class pointer is passed implicitly as the this pointer. So we can write them as:

bool isEmpty() const
{
    return (top == -1);
}

void push(int op)
{
    arr[++top] = op;
}

Note that member functions that don't change the member variables of the class should be marked const to indicate this.

int postfixEvaluation(char* exp)

For C++, we should usually use a std::string rather than a raw char*. This stores the length of the string along with the data, so we don't have to use strlen, which iterates through the whole string to find the null character at the end:

int postfixEvaluation(std::string exp)
{
    Stack stack(exp.size());

int i;

We don't use this variable outside the for loop. So we should just do:

for (int i = 0; exp[i]; ++i)

    if (isdigit(exp[i])) ...

For C++, isdigit is in the std:: namespace and we should include the <cctype> header to use it. Unfortunately, we also have to cast the argument to unsigned char before using it:

    if (std::isdigit(static_cast<unsigned char>(exp[i]))) ...

    // If the scanned character is an operator, pop two elements from stack apply the operator
    else
    {
        char val1 = stack.pop();
        char val2 = stack.pop();
        switch (exp[i])
        {
        case '+': 
            stack.push(val2 + val1); 
            break;
        case '-': 
            stack.push(val2 - val1); 
            break;
        case '*': 
            stack.push(val2 * val1); 
            break;
        case '/': 
            stack.push(val2 / val1); 
            break;
        }
    }

It's possible that we were given an invalid RPN string (such as the one in the question!). Currently the program silently ignores invalid input, giving the user no indication that the answer they get out is incorrect. We definitely need to warn them!

So we need to do a couple of extra steps here:

• Check that there are actually two values in the stack to pop (we could add a getSize() member function to the stack class), warn the user if there aren't and stop the program.

• Check for an invalid character in the RPN string (we can add a default case to the switch statement to catch such characters), warn the user and stop the program.

One other thing to be careful of is if the user supplies an empty string. We can't pop a value off the stack in that case! So we should probably check for this at the top of postfixEvaluation and return 0.

#include <string.h>

It's better to include <cstring>, which declares all the identifiers in the std namespace. .... Unless you do this:

using namespace std;

which denies you all the advantages of namespaces. So don't do that.

    struct Stack* s = (struct Stack*) malloc(sizeof(struct Stack));

This looks like C code, assuming that std::malloc(), from <cstdlib>, is intended. Why are you not using new here - or better, on of C++'s smart pointers? The subsequent initialisation looks like it really belongs in Stack's constructor which would entirely remove the need for this factory function.

The corresponding free() seems to be entirely absent, meaning that this program leaks memory. And the capacity is never checked, meaning that it is vulnerable to overflow.

All in all, I see no reason not to use a std::stack here, rather than poorly implementing our own.

The earlier replies have already pointed out that this is C code, top to bottom, and is not at all the way you would write in C++.

Since there is already a std::stack in the standard library, I'll just go over the one function you actually had to write to implement your parser.

int postfixEvaluation(char* exp)

Your input is not modified, so use const. But really, don't pass as a char* at all, but use std::string_view.

    // Create a stack of capacity equal to expression size 
    struct Stack* stack = createStackFun(strlen(exp));

That becomes: std::stack<int> stack;
Note that you don't have to pre-define a capacity, and you don't use pointers; rather, the class instance is a local variable directly.

    // See if stack was created successfully 
    if (!stack) return -1;

It will be, or an exception will be thrown. With the std::stack constructor, if the code got here there is no error, period.

    int i;
    ...
    // Scan all characters one by one 
    for (i = 0; exp[i]; ++i)

First of all, you don't need to declare your variables at the top of the function. Even in C, that has not been necessary since C90. Don't!! Declare variables when you are ready to initialize them.

Here, you don't even need i at all, as we'll see next.

To scan the characters one by one, use a range-based for loop: for (const auto c : exp) then in the body of the loop you will get c set to the next char in turn, so use that instead of exp[i]. BTW, it is "not nice" that you repeated exp[i] all over the place instead of getting the value out of it once.

        // If the scanned character is an operand (number here), push it to the stack. 
        if (isdigit(exp[i]))
            push(stack, exp[i] - '0');

That's reasonable, given that you only allow single-digit numbers in your input. Likewise, the math part is reasonable, but needs to be converted to use the member function calls on std::stack.

So, your actual "real work" logic is fine. 😀