6
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ What about simply using std::stack instead of rolling your own? \$\endgroup\$ – πάντα ῥεῖ May 5 '17 at 18:47
  • \$\begingroup\$ just for learning how stack works. \$\endgroup\$ – abs May 5 '17 at 18:50
  • 3
    \$\begingroup\$ Best of learning is to get familiar with what's already there. \$\endgroup\$ – πάντα ῥεῖ May 5 '17 at 18:53
  • 1
    \$\begingroup\$ There are lots of bad C++ books... be careful. This is a book well worth buying stroustrup.com/programming.html, written by the man himself. \$\endgroup\$ – Aluan Haddad May 5 '17 at 21:59
  • 2
    \$\begingroup\$ @AluanHaddad Rather stick to that one and the follow ups Ricard Bach, "Illusions". \$\endgroup\$ – πάντα ῥεῖ May 5 '17 at 23:09
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ Its a pity that I don't know/forgot the difference between char/unsigned char/signed char. Thanks a lot for pointing that out and other valuable suggestions. \$\endgroup\$ – abs May 8 '17 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.