Stack based recursive arithmetic expression parser

Question

I recently started to learn C++ and came across this problem in a book "Object Oriented Programming in C++" by Robert Lafore.

The author has a program in the book which creates a Parser. I found a problem with the original program in the book which breaks at one of the input expressions I am providing. Therefore I tried to make changes and made it recursive. It works fine with the inputs I am providing.

I am more concerned about correctness and programming style of the program I have written. I believe I have made many mistakes. Any comments would be very helpful.

#include <iostream>
using namespace std;

const char SIZE = 40;

class Stack
{
private:
    char array[SIZE];
    char top;
public:
    Stack():top(-1)
    {
    }
    void push(char v)
    {
        if (!is_full())
        {
            array[++top] = v;
        }
    }
    char pop()
    {
        if (!is_empty())
        {
            return array[top--];
        }
        throw "Stack is empty. Pop failed";
    }
    bool is_full()
    {
        return top >= SIZE ? true : false;
    }
    bool is_empty()
    {
        return top == -1;
    }
    char get_top()
    {
        return top;
    }
};

bool is_operator(char c)
{
    return (c == '*' || c == '/' || c == '+' || c == '-');
}

bool is_dm_operator(char c)
{
    return (c == '*' || c == '/');
}


bool is_value(char c)
{
    return (c >= '0' && c <= '9');
}

void resolve_op_recursively(Stack& e_stack, char in)
{
    if (e_stack.get_top() == 0) //stack has only 1 operand
    {
        e_stack.push(in);
    }
    else
    {
        char last_val = e_stack.pop();
        char last_op = e_stack.pop();
        if (is_dm_operator(in) && !is_dm_operator(last_op)) // 2 + 3 * 5 case only
        {
            e_stack.push(last_op);
            e_stack.push(last_val);
            e_stack.push(in);
        }
        else
        {
            char first_val = e_stack.pop();
            switch (last_op)
            {
                case '/':
                    e_stack.push(first_val / last_val);
                    break;
                case '*':
                    e_stack.push(first_val * last_val);
                    break;
                case '+':
                    e_stack.push(first_val + last_val);
                    break;
                case '-':
                    e_stack.push(first_val - last_val);
                    break;
                default:
                    break;
            }
            resolve_op_recursively(e_stack, in);
        }
    }
}

void parse_expression_using_stack(Stack& e_stack, const char * input)
{
    while (*input)
    {
        char in = *input;
        if (in != ' ')
        {
            if (is_value(in))
            {
                e_stack.push(in - '0');
            }
            else if (is_operator(in))
            {
                resolve_op_recursively(e_stack, in);
            }
            else
            {
                cout << "unknow expression" << endl;
            }
        }
        input++;
    }
}

void solve_expression_using_stack(Stack& e_stack)
{
    while(e_stack.get_top())
    {
        char second_operand = e_stack.pop();
        char operator_ = e_stack.pop();

        switch (operator_)
        {
            case '+':
                e_stack.push(e_stack.pop() + second_operand);
                break;
            case '-':
                e_stack.push(e_stack.pop() - second_operand);
                break;
            case '*':
                e_stack.push(e_stack.pop() * second_operand);
                break;
            case '/':
                e_stack.push(e_stack.pop() / second_operand);
                break;
            default:
                cout << "unkown operand " << operator_ << endl;
        }
    }
}

void solve_expression_and_match_result(const char * input, char expected_result)
{
    Stack e_stack;
    char result;

    cout << "Expression: " << input;

    parse_expression_using_stack(e_stack, input);
    solve_expression_using_stack(e_stack);

    result = e_stack.pop();
    cout << " Got solution: " << static_cast<int>(result) << " Expected Solution: " <<  static_cast<int>(expected_result) << " Test: ";

    if (result == expected_result)
    {
        cout << "\nPASSED" << endl;
    }
    else
    {
        cout << "\nFAILED" << endl;
    }
}

int main(int argc, const char * argv[])
{
    const char * expressions[20] =
                            {
                                static_cast<const char *>("5 / 5 + 3 - 6 * 2"), // why static_cast here? what is const_cast
                                static_cast<const char *>("3 * 7 - 1 + 5 / 3"),
                                static_cast<const char *>("3 * 5 - 4"),
                                static_cast<const char *>("3 + 5 - 4"),
                                static_cast<const char *>("2 / 6 * 3 / 2"),
                                static_cast<const char *>("3 + 6 * 9 / 3 - 7"),
                                static_cast<const char *>("9 - 5 / 5 * 2 + 6"),
                                static_cast<const char *>("7 + 3 * 4 / 2 - 5 * 6"),
                                static_cast<const char *>("4 * 5 + 3 - 4 / 2"),
                                static_cast<const char *>("4 / 2 * 5 + 3 - 4"),
                                static_cast<const char *>("5 + 3 * 4 / 2 - 3"),
                                static_cast<const char *>("5 - 3 + 4 / 2"),
                                static_cast<const char *>("5 * 3 / 2 - 2"),
                                static_cast<const char *>("5 * 2 / 4 + 9 - 2")
                            };

    char solutions[20] =
                        {
                            5 / 5 + 3 - 6 * 2,
                            3 * 7 - 1 + 5 / 3,
                            3 * 5 - 4,
                            3 + 5 - 4,
                            2 / 6 * 3 / 2,
                            3 + 6 * 9 / 3 - 7,
                            9 - 5 / 5 * 2 + 6,
                            7 + 3 * 4 / 2 - 5 * 6,
                            4 * 5 + 3 - 4 / 2,
                            4 / 2 * 5 + 3 - 4,
                            5 + 3 * 4 / 2 - 3,
                            5 - 3 + 4 / 2,
                            5 * 3 / 2 - 2,
                            5 * 2 / 4 + 9 - 2
                        };

    for (int i = 0; i < 20; ++i)
    {
        if (expressions[i])
        {
            solve_expression_and_match_result(expressions[i], solutions[i]);
        }
    }

    return 0;
}

Answer 1

1. Don't use using namespace std;

While that would work in your particular case, it's considered bad practice. Especially when you move out your code to separate header files.

See more details here please:

Why is “using namespace std;” considered bad practice?

2. Don't reinvent the wheel

You shouldn't write your own stack class, in preference of just using what the C++ standard library already provides.

There's already std::stack, that should work well for your needs.

3. Don't use raw arrays in C++

Your raw array

char array[SIZE];

should be a

std::array<char,SIZE> arr;

instead. std::array would cover all your needs, and gives you a more safe implementation.

Also the naming array might clash with the using namespace std; as mentioned.

4. Don't use throw with types not inherited from std::exception

 throw "Stack is empty. Pop failed";

This is a bad practice example of using a throw statement. While it can be caught in various ways like

catch(const char* e) {
    // handle exception
    std::cerr << e << std::endl;
    exit(1);
}

it shouldn't be done like this. You will loose any distinction about certain categories of exceptions that could occur (again: Don't reinvent the wheel. Get familiar with the C++ standard library instead).

The C++ exception hierarchy is based on std::exception, and what you actually have is a runtime failure. So you should rather use the standard exception class that indicates that:

throw std::runtime_error("Stack Class Error: Stack is empty. Pop failed";

The above exception could be caught transparently and reported using the what() function:

catch(const std::exception& e) {
    // handle exception
    std::cerr << e.what() << std::endl;
    exit(1);
}

5. Use the correct cast operations

static_cast<const char *>("5 / 5 + 3 - 6 * 2"), // why static_cast here? what is const_cast

Your guts were right about that. At least that even doesn't need a const_cast since the character literal "5 / 5 + 3 - 6 * 2" already decays to a const char[] / const char* anyways.

Answer 2

• char top

  Any decent compiler should issue a

  warning: array subscript is of type 'char' [-Wchar-subscripts]
  

  The reason is that signedness of char is implementation defined. If you happen to try your code on a platform where char is by default unsigned, the very first stack operation will access array[255].

• The responsibilities of parse_expression_using_stack and solve_expression_using_stack are badly intermingled. The parser should either interpret the input completely, or do not do any arithmetics at all.

• push into a full stack is silently ignored.